Controlling the Inductive Bias of Wide Neural Networks by Modifying the Kernel’s Spectrum
Authors: Amnon Geifman
Daniel Barzilai
Ronen Basri
Meirav Galun
Venue: Accepted by TMLR ()

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.

Published in Transactions on Machine Learning Research (02/2024)
Controlling the Inductive Bias of Wide Neural Networks by Modifying the Kernel's Spectrum
Amnon Geifmann"
amann.ethnamm&@eeemmmm...cc
Weizmann Institute of Science
Daniel Barzilai'
damicc.aarzlaa@@@nimmma..ccm
Weizmann Institute of Science
Ronen Basri
ronen.barriuueimmmm....
Weizmann Institute of Science Meta Al
Mcirav Galun
Weizmann Instätule of Science
Reviewed on OpenReview: https: // openreview. net/ forum? id= aDDEnytnEK
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 great need for methods that can modify this blas according to the task at hand. To that end, we introduce Modified Spectrum Kernels (MSKs), 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 preconditioned gradient descent mothod, which alters the trajectory GD. As a result, this allows for a polynomial and, in some cases, exponential training speedup without changing the final solution. Our method both computationally efficient and simple implement.
1 Introduction
Recent years have seen remarkable advances understanding the inductive bias of neural networks. Deep neural networks are biased toward learning certain types of functions. On the one hand, this bias may have a positive effect by indueing implicit form of regularization. But the other hand, it also implies that networks may perform poorly when the target function is not well aligned with this bias.
A scries of works showed that when the width of neural network tends to infinity (and with a certain initialization and small learning rate), training a netw with GD converges to a kernel regression solution with a kernel called the Neural Tangent Kernel (NTK) (Jacot et al.) 2018 Lee et al. 2019 Allen-Zhu et al, 2019: Chizat et al.) 2019). Subsequent work showed that the inductive bias of wide neural networks can be characterized by the spectral decomposition of NTK (Arora et al.) 2019a] Basri et al. 2019 Yang & will use the term spectral bias of neural networks to refer to the inductive bias induced by their corresponding NTK spectrum. Specifically, it has been observed both thcoretically and empirically that for wide neural network, learning an cigen-direction of the NTK with
Salman 2019). Following this characterization,
GD requires a number of iterations that is inversely proportional to the corresponding eigenvalue (Bowman & Montufar 2022 Fridovich-Keil et al.) 2021 Xu et al.) 2022). Thus, if this spectral bias can be modified, it could lead to accelerated network training certain target functions. Typically, the eigenvalue of NTK
FEqual Contribution

---

Published in Transactions on Machine Learning Research (02/2024)
decays at least at polynomial rate, implying that many cigen-directions cannot be learned in polynomial time with gradient descent (Ma & Belkin 2017). As such, modifying the spectral bias of a neural network is necessary to enable feasible learning time, allowing learning target functions that are not well aligned with the top cigen-directions of NTK. This prompts the following motivating question:
Is it possible to manipulate the spectral bias of neural networks?
The spectrum of'a a kernel also determines the prediction function when using kernel ridge regression. Therefore, we introduce family of kernel manipulations that enables generating wide range of new kernels with nearly arbitrary speetra. These manipulations do not require explicitly working in feature space and are, therefore, computationally efficient. We leverage this technique to design kernel-based preconditioner that significantly modifies the linear training dynamics of wide neural networks with GD. This preconditioner modifies the spectral bias of the network so that the convergence speed is no longer tied to the NTK but rather to a kernel our choice. This yields a polynomial or even exponential speedup (depending on the decay rate of the spectrum of the NTK) the convergence time of GD. We subsequently show that the proposed accelerated convergence does not alter the network's prediction at convergence on test points.
In sum, our main contributions
1.
We introduce Modified Spectrum Kernels (MSK's), which enable approximating the kernel matrix for many kernels for which closed form is unknown (Section 3
We introduce preconditioned gradient descent and prove its convergence for wide neural networks (Section 4.1
We prove that our method is consistent, meaning that the preconditioning does not change the final network prediction on test points (Section 4.2).
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 &o X' X defined over compact metric space X' endowed with a finite Borel measure μ. Given such k its corresponding (linear) integral operator Lç (x) + L (X) defined as
(x)))) is
(x(f)xx== J k(x, ())))))(
This is a compact, positive self-adjoint operator that therefore has an cigen-decomposition of the form
[x( = Σ Xrl,, 1.),,
$20
where the inner product (:), is with respect to (2)(),, and X b are the eigenvalues and eigenfunctions of the integral operator satisfying
Ll( X,
According Mercer's Theorem, can be written using the cigen-decomposition of the integral operator as
k(x, 2) = Σ (x)0(1)))))))) x,
(1)
Furthermore, each such kernel is associatod with a unique Reproducing Kernel Hilbert Space (RKHS) Hr C (2)) (which denote by H when the kernel is clear by context), consisting of functions of the
2

---

Published in Transactions on Machine Learning Research (02/2024)
< <0. 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 Ag. For any positive definite kernel there exists feature map Φ : X - H s.t
form [(x) Eier az (x) whose RKHS norm is finite, i.e., I1/ := Exer ai X.
k(x, z) (())). As such, may occasionally call the RKHS H the feature space of k.
Given training data X = (xi,,.,xa)) X; E X corresponding labels (vi yi E R. and rogularization parameter 7 > 0, the problem of Kernel Ridge Regression (KRR) is formulated as
min SEH
E(f(x)) v.)² + 11fflx
(2)
The solution satisfies f(x) = (K + + yy where the entries of kx E R are n kxx,,,;;, K is the n x n
kernel matrix with Kij 1. (x,,,,,)) and y (y1..... vr)
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. The novel kernels constructed by directly manipulating the kernel matrix of existing kernels, which are easy to compute. 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 l(x, 2) == E (x) be Mercer kernel with eigenvalues A; and eigenfunction (.(-) and IR + IR a function which is non non-negative and L-Lipschitz. The Modified Spectrum Kernel (w.r.t. k) is defined as (x, = = (Axx (x) (x)
The MSK has the same eigenfunctions as the source kernel k, while its eigenvalues are modified by g. Clearly, constructing a closed-form solution to the modified kernel is rarely possible. However, is possible to approximate the modified kernel efficiently under certain conditions, given the values of the original kernel k; as proved Theorem 3.2
Theorem 3.2. Let g, k, be as in Def. 3.1 and assume that Vx E X, (x)( S M. Let K, Kg be the corresponding kernel matrices on i.i.d samples X1. Xn X. Define the kernel matriz K2 VDVV where V (V1...,Va) with v, the i'th eigenvector of K and is a diagonal matriz with Dús = g(As) where Å is the i'th eigenvalue of K. Then, for +
[R Kglly "$ 0,
where a.s. stands for almost surely.
We next provide proof sketch. The full proof is given in Appendix C For an eigenfunction of k(x, z), we let ((X)= == (b(x;),.... ((x,,))* E R" be the evaluation of the cigenfunctions on the data. By the definition of the kernels it can be shown that K == = A& (X xx and similarly, K2 =x== ((>s) (x (x)))))(())))X)))))) (X)". Since K2 is composed of the eigenvectors of K with the eigenvalues g(Ax), we would like to show that the eigenvalues of K, are close to ((x)) and that the eigenvectors of K are close to those of K,- 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. p0100; and as such, we know that the eigenvalues of K, should be close those of Kg. The challenge is that the cigenvectors Vy do not have be close to (X)), the evaluations of the eigenfunctions means that the eigenvectors of K, can be very different from those of Kg. We work around this by showing that for large the cigenvectors of K corresponding to an eigenvalue 2 are related to an cigenfunction 4; as
the data (for example when there is an eigenvalue of multiplicity greater than 1). This
if 4 an eigenfunction of A m {o
Σ (vT2((X))²
else
v:Kv=AvV
This allows us to show that the norm between the eigenspaces of Kg and Kg tends to 0.
3

---

Published in Transactions on Machine Learning Research (02/2024)
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 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 lonescu et al. 2017 Nevertheless, there are still many kernels for which a closed form unknown.
MSKs allow extending existing RKHS theory by computing new kernels with predetermined Mercer de- composition even when closed form is unknown and, specifically, solve KRR. with these kernels. Suppose we would like to solve the problem of KRR as defined in 2 Let x(x,z)= = = (x)x(x))xx() and (x, z) -k= (()a)(((( (x) be two Mercer kernels where ((x, z) has a known closed form, whereas ko (x, Z) does not. Assuming we obtain i.i.d. samples of training points X1y Xn and a test point x, we can build Kg (as in Theorem 3.2 using the n + 1 points X1... X. Then, by a contimuity argument, Theorem 3.2 guarantees that the predictor (x) = [ Mgg+1.1mm ([K,
converges to the KRR prediction with the kernel kg, where I., corresponds to the sub-matrix induced by the specified indices.
1m..1 im + + (
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 the NTK, overcoming the spectral bias of neural networks. We begin by explaining how the convergence rate of neural nerks related to the spectrum of the NTK. Then, we introduce preconditioning scheme for wide neural networks and prove that it attains global optimmun. 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 minimizer.
We consider fully connected neural network paramcterized as follows:
(x)
(x) = w(gg + +b²) E ER", 1=
g.) (x) p (x)) E Rd, 1= f(x, w) (()+ w((+1)
+b(4)))
where w E RP is the set of all the network parameters. We select a simple architecture and note that our results can casily be extended to many other architectures. We denote by m the width of the network and assume that d1 d2 = .. dp m. The activation function is denoted by P and the following quantities (p(0),, IIl'l and sup l (z) o' l//))/// x'I should be finite. The initialization follows the standard NTK parametrization (Lee et al. 2020a (see more details in Appendix A).
We denote the vector of labels for all the data points (B1...., Vn. by y E R" and the vector of network predictions f(x;, w) by f(X, w) E IR". The residual at time i is r, = S(X, we) -y. Letting L be the squared error loss, ((w)) 2 ||rall? a gradient descent iteration for optimizing w E Rp is given by
W++1 W. = - = -
(X,
(3)
where 7) is the learning rate, and V w.) E Ra is the Jacobian of the network.
The empirical NTK matrix at time t, K, E Raxx, and the NTK matrix, K E R=x"" are defined as
K2
m W. (X,
(4)
K =limm Ko.
(5)
We assume that Amm (K) 0. A simple case where this condition is satisfied is whenever X' gd-1 and p grows non-polynomially (e.g ReLU) Jacot et al. (2018), and also various other settings given by Oymak &
4

---

Published in Transactions on Machine Learning Research (02/2024)
Soltanolkotabi
2020 Wang & Zhu 2021 Nguyen et al. 2021 Montanari & Zhong 2022
Barzilai &
Shamir (2023)
Arora et al. 2019a showed that for a wide neural network with ReLU activation, small initialization, and a small learning rate, holds that for every e O, the residual at time t evolves with the following linear dynamics
n
|rell nk)))
= +C=
Σ (1
(6)
where (Aelizz and {vi) respectively are the eigenvalues and eigenvectors of the NTK matrix K.
Eq. 16 reveals the relation between the inductive bias of neural networks and the spectrum of the NTK matrix [Basri et al., (2200b). Specifically, learn an cigen-diraction v, of a target function within accuracy 8 0, it is required that (1 1---)h -)):)' 5 + e. When the learning rate sufficiently small to imply convergence,
0 2, the number of iterations needed is
A
+ 1og((8+))/1 =)/nd; =0 A1
(
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. (2020a)). ) In the case of a fully connected network with ReLU activation and with data points distributed uniformly on the sphere Sd-1, the cigenvectors are discrotizations of the spherical harmonics and the eigenvalues asymptotically decay as A R k-d where k is the frequency (Basii et al., 2020bb Bietti Bach 2020). In this scenario, learning high-frequency eigenvector with gradient descent is computationally prohibitive, even for 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.
4.1 Preconditioned Gradient Descent
To accelerate the convergence of standard gradient descent (PGD). The update rule of our PGD is given by
3 propose preconditioned gradient descent
W Wr V f(X, w.) Sr.,
where E Ruxn is a preconditioning matrix that satisfies S >
Standard preconditioning techniques multiply the network's gradient from the left by a p p matrix (where p is the number of parameters in the network, usually huge). In contrast, our preconditioner multiplies the matrix, reducing the cost per iteration from p² to n?. This is
network's gradient from the right by significant since in the over-parameterriee case & p-
We next derive the linear dynamics of the form of (6) for PGD. One of the key properties of PGD, is that carefully choosing S allows modifying the dynamics of gradient descent almost arbitrarily.
Theorem 4.1. Suppose assumptions 4 are satisfied. Let nu. 6,, > O, S E x such that $ > and Then, there erists N N such that for every m 2 N, the following holds with probability at least - 60 over random initialization when applying preconditioned GD with learning rate = no/ /mm
To < (KK)
re = (1- (K)
where |1El12 S.
Recall that we assume K > 0 and S > 0, so while KS is not necessarily positive definite symmetric, it has positive real eigenvalues. As such, the term (K3)))ma==(33) is positive and defines the maximal feasible
learning rate. The formal proof of Theorem 4.1
given in Appendix A and here give some key points
5

---

Published in Transactions on Machine Learning Research (02/2024)
of the proof. The proof relies on Lemma 4.2 which shows that PGD finds global minimum in which the weights are close to their initial values. In particular, for any iteration 4, K,S R KnS & K.S. Based on the results of Lemma
4.2 Theorem 4.1 carefully bounds the distance E(t) between r and the linear dynamics
(I - "/o Ksyy.
> no and S such that S > O, there exist C> 0, N E and 1, such that for every 2 N, the following holds with probability at least 1 -0 60 over random initialization. When applying preconditioned gradient descent as in (7) with learning rate nu/m
Lemma 4.2. Suppose assumptions
4 are satisfied. For 80 > O,
1. ||rell2 5 (1 Ndduun)) )'c
2. Σj=1 [[; wi-1ll2 S
3xC mmm Amin
C m 1/2 Amin sup, [1(Kg - K,)S(lF S
where Amin is the minimal eigenvalue of KS.
The full proof of Lemma 1 is given in Appendix A
Theorem 4.1 implies that the dynamics preconditioned gradient descent are characterized by KS instead of K. In particular, KS is symmetric, PGD follows the dynamics
|r||| ||(I nKS)
Σ
(1- (1-mA (
(8)
where now, in contrast to 60, A v; are the eigenvalues and eigenvectors of KS. The role of the preconditioner S is to reduce the condition number of K, i.e., improving the worst-case convergence rate. Moreover, it can be chosen to accelerate the convergence rate in directions corresponding to any eigenvector of the NTK matrix.
The results of Zhhnn et al. (0099 and Cai et al. 2019)) can be viewed as a special case of S Specifically, these works characterize the convergence an approximate second-order method (Gauss-Newton) when applied to a wide, two-layer network. In this case, the update rule of the form
Wi+1 w; = -w)((w)) -V.
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,- For sufficiently wide networks, K, is very close to K (in spectral norm). Thus, taking S = K suffices for achicving the same convergence rates as S = K- Furthermore, our method requires computing the preconditioning matrix only once and is therefore more efficient. In fact, Figure demonstrates that taking S=K-1 leads an even faster convergence.
We show in Sec. 4.3 how S can be chosen to reduce by 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, (vTy) 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 suffer significantly from the slow convergence rate in the directions corresponding to small eigenvalues (Wang
et al. 2022
4.2
Convergence Analysis
In this section, we characterize the resulting prediction function of the network on unseen test points and show that PGD generates consistent ion function in the following sense. At convergence, the prediction

---

Published in Transactions on Machine Learning Research (02/2024)
function of network trained with PGD is close to the prediction function of network trained with standard
GD.
We start by defining a preconditioned loss, [s(f.w) which modifies the standard MSE loss Ls(s, w) = - (J -)))
(9)
where S > is the preconditioning matrix. An iteration of standard GD w.r.t Cs(S, w) yields
W++1 - W. = -n w.) = VX, Sr
(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 wo E I2, , d(x) == Vx(x, wo) and h(x, w') = (w', (x))) For simplicity, we denote h(X, w') (h(x1, w')...., h(x,, w w))² R".
The minimizer of the kernel ridge regression objective with respect to the preconditioned loss defined as
1 |1/2( w/) w)]l 2 |l
arg min W'RR"
(11)
2
and the minimizer of a kernel ridge regression with respect to the standard MSE loss is defined
arg min w'ERY
2 [[(((X w') s) 2" /w'l2.
(12)
We denote by w and w** the limits of w and w respectively, when y O. In Lemma 4.3 we show that the two minimizers equal, which means that the preconditioned loss does not change the prediction function in kernel regression.
For a given learning rate and loss Ls, h can be optimized through gradient descent with respect to the loss Ls via the iterations
w/6 -
W441 w/ - Lshh,, w!).
(13)
We show in Lemma 4.3 that this itcrative procedure yiclds prodiction function that remains close to the neural network prediction throughout PGD.
Lemma 4.3.
1. Let wa Rp and Φ(x) == ff(x, wo), it holds that w =w*.
Let 60 0, O, test point x Rd and T > number of iteration. Under the conditions of Theorem 4.1 EN N s.t Vm > N, it holds with probability at least 1 5y that
[k(x, w/)) - f(x, wT)] Se,
where w' 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) proved by deriving w in closed form,
i.., w = Σ a (xx,, with
a² = (Ko -
This serves as 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 + 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(,, wr) at test point is very close to h[1, w/)). We note that as Ls convex, l((x, w/) approaches h((x, 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 the network itself (Lee et. al. 2019

---

Published in Transactions on Machine Learning Research (02/2024)
Algorithm 1 Preconditioned Gradient descent
Require: y. w), K, (K,))))), wo
Decompose K +- DVDV
DV
dc iil (1 (1- g(de) v.v!
Define S - I -
6-0
while |Ir/|| do
W++1 <- Wt 17 V w f wi)
1 + 1+1
end while
4.3 An Algorithm for Modifying the Spectral Bias
Tn 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
First, given the NTK matrix of size n n, we construct a pro-conditioner from K by applying a spectral decomposition, obtaining the top & + eigenvalues and eigenvectors. We denote the lop k + eigenvalues by À ... A 2 Ak+1 0, and their corresponding eigenvectors by Vi,..,, V&, Va+1- The proposed pre-conditioner is of the form
(1-
g(Ai)
S Σ 2=1 d
v.v."
(14)
It can be readily observed that S and K share the same eigenvectors, and as long as g(Ar) > 0 then S > 0 and its eigenvalues given in descending order are:
g(*x)
g(An)
A A
Since and K share the same eigenvectors, holds that the eigenvalues of KS are
[o(Ar), (aa))....gg()))))) g(Ax), A4t1, Axt2,.., An]-
The connection between the proposed preconditioner and Theorem 3.2 can now be clcarly seen, as the product KS yields a MSK matrix, and therefore approximates a kernel that shares the same eigenfunctions & and its eigenvalues are modified by g (where for À 2 A8+1 we let g(A) = A). Together with Theorem 4.1 the dynamics of the neural network are controlled by this modified kernel, and as such we obtaín way to alter the spectral bias of neural networks. From Eq. { we obtain the following corollary, stating that the top k eigenvectors V; of K be learnt in O(1) time.
Corollary 4.4. Let g(Ac) Au+1, isisk k, and S be given by 14] (making the top + 1 eigenvalues of KS equal to each other). Under the conditions of Theorem 4.1 by picking the learning rate 1 Ax+1+>o AN E N s.t Vm > N, it holds with probabiläty at least 1 - 80 that for every S k + 1, Vi can be learnt (up to error) in O(1) time (numaber of iterations).
This starkly contrasts the typical spectral bias of neural networks, under which for large i, learning V; may be infeasible in polynomial time. For example, when the activation function p is tanh, Murray et al. 2022) showed that A O 1d+1/ vT) Applying (6), vanilla GD requires O (1d+1/2 12411/2 iterations to converge, exponentially slower in & compared to PGD.
Another natural choice for g, is given some ? > 0, to let g(A) := X+ and k = n, implying that KS K +ĀI. Thus, we obtain direct correspondence between PGD with such choice of g. and regularized kernel regression. Such a choice of & may help prevent overfitting, even without early stopping. This is demonstratod in Figure
8

---

Published in Transactions on Machine Learning Research (02/2024)
Number of ittrations
10000
5000
Frequency
1400
1567
4001 2000
1000
600
1700
2000
1001
Figure 1: Numerical validation. Top: The number of iterations required to learn different Fourier components as function of frequency. Standard SGD is shown in blue, and (stochastic) PGD with preconditioner derived from the NTK matrix K and the empirical NTK Ke respectively are shown in green and orange. Bottom: Training curves with four different frequencies (k 7, 12). The graphi show the MSE loss as function iteration number with stochastic GD and PGD.
The NTK matrix may be ill-conditioned with the smallest eigenvalues very close to 0. This issue magnified by the fact that some approximation may be needed when computing the NTK for arbitrary architectures Novak et al. 2022); Mohamadi al. (2023). However, small can help avoid numerical instabilities in the preconditioner by only modifying sufficiently large eigenvalues. Furthermore, since only the top h eigenvalues and eigenvectors need to be calculated, choosing small & allows for a more efficient calculation of S. By contrast, choosing k implies that S = K-1 We leave the choice of k, the mumber of modified eigenvalues, to the practitioners, but in general, one should think of k as providing trade-off between the worst-case rate of convergence, and computational stability and efficiency.
A Atthouhh our method involves computing the preconditioner, still results more efficient optimization the over-vvvannaeee preaeerraeteriiee regime. To see this, we note that for L > 2, if the width m of every layer at least n for some q 0, then the number of parameters of fully-connected network is A(n21). This implics that the worst-case number of operations for GD to converge is w (K3 where Amin (K) is the minimal eigenvalue of K. For a fully connected ReLU network, upper bounds on Amin(K) decay polynomially in n Barzilai & Shamir 2023). implying that the complexity is w(n2++1). Under the most general assumptions, Song & Yangl (2019) achieved g = 4. In this case, we have a clear computational advantage since inverting K or calculating its cigenvalues costs O(n²). Nevertheless, under stricter assumptions, smaller widths than q= may suffice, but our method is still more efficient even for linear width (g = 1). Our method is also significantly more efficient than standard preconditioner matrix whose size is quadratic in the number of parameters. Furthermore, our preconditioner needs to be computed only once, so its computational complexity is unrelated to the number of iterations needed to converge, which as already discussed, can be exponential. Lastly, in practice, one may choose k, the number of eigenvalues to modily, 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 uniform distribution the circle,
9

---

Published in Transactions on Machine Learning Research (02/2024)
Variance of MSKs with Laplace Kemel
0.0
org
0.7
+
g(A) VA
0.4
0.3
0.2
1500
2000
2500
Samples
Figure 2: The effect of various MSKs on overfitting to noise. Choosing an MSK with a slower eigenvalue docay helps prevent overfitting Starting from Laplace kernel, for each choice of g, we perform unregularized kernel regression (with y 0) using an MSK as defined in 3.1 The target function identically O, with i.i.d Gaussian noise added to the training set (y (N, 1)). The axis denotes the number of samples, and y axis the MSE the test set (for which the target is 0).
X2 ~ U. With each input we associated a target value Yi by taking a Fourier component of frequency k (we repeated this experiment with different values of k); i.e., x; = (cos(O), sin()))),nnn)))))))))))))))))))) (0))² then y/ = sin(k0), 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 al. 2019). We then trained 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 T, (no preconditioning), K-1 (inverse NTK matrix), or K, (inverse empirical NTK matrix). Figure shows that without preconditioning, the number of standard GD iterations roughly quadratic in the frequency the target function and quickly reaches the ileration limit. In contrast, using preconditioners based on either K or K, boosts the convergence, yielding a near-constant number of iterations, irrespective of the frequency of the target function. 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 K2 boosts the convergence, yielding near constant number of iterations, irrespective of the frequency of the target function. The lower panel in Figure also shows convergence plot for few different functions.
Furthermore, we analyze the variance of kernel regression under different choices of MSKs in Figure 2 The error of kernel regression is often decomposed into a bias and variance term, where the variance the error when training on labels given by a constant 0 target function with noise added to the training set (Tsigler & Bartlett 2023). In our experiment, starting from Laplace kernel, for each choice of g, perform unregularized kernel regression (with
0) using an MSK as defined in 3.1 We take inputs drawn uniformly from $2 and ~ NN(0,)) 1). The axis depicts the MSE over a test set of 1000 samples (where the test set target labels are 0), averaged over 25 trials. Various works suggest that a slower eigenvalue decay helps induce an implicit regularization in the kernel, helping it to avoid overfitting (Mallinar et al. 2022 Tsigler & Bartlett 2023). We can observe this phenomenon in Figure 2 where the MSKs with slower eigenvalue decay achieve smaller variance.
5 Related Works
A long string of works established the connection between kernel regression and neural networks. Early works considered Bayesian inference setting for neural networks, showing that randomly initialized networks
are equivalent to Gaussian processes (Williams) 1997 Neal 2012). Tn this direction, Cho & Saul (2009)
10

---

Published in Transactions on Machine Learning Research (02/2024)
introduced the Arc-cosine kernel, while Daniely et al. (016) 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. 2019b). 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 works (Huang et al. 2020). convolutional
networks (Arora et al. 2019b Li et al. 2019), and other standard architectures (angg 2020
Subsoquent work used the NTK theory to characterize the spectral bias of neural networks. Bach 2017
Basri al. 2019); Cao et al.
2019 [ietti & 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 higgeeyfrequency ones. [asri et al. (2020a) further derived
the eigenfunctions of NTK with non-uniform data distribution. Yang & Salman (2019); Misiakiewicz &
Mei (2021) analyzed the eigenvalues of NTK over the Boolcan cube. More recent studies investigated this bias with other network architectures, including fully-connocted ResNets (Belfer ct al. 2021 Tirer et al.,
2022), convolutional networks (Geifman et al. 2022: Cagnelta el. al. 2022 Xiao 2022 and convolutional
ResNets (Barzilai et al. 2022). (Murray et al. 2022 characterized the spectrum of NTK using its power
scries expansion.
Preconditioning is a widely used approach to accelerating convex optimization problems. preconditioner is typically constructed using the inverse of the Hessian or its approximation (Nocedal & Wright 1999) to improve the condition number of the problem. Recent works tried to improve the condition number kernel ridge regression. Ma & 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.
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 precondtioiners use layer-wing adaptive learning rates (You et al. 2017 2019). In this line of work, it is worth mentioning (Lee et al. (0000)), who used the convergence results of Arora et al. (2019b) to incorporate leverage score sampling into training neural networks. Amari et al. (2020) studied the generalization of overparamelerized ridgeless regression under a general class of preconditioners via the bias-variance trade-off.
Past studics 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. Sinddwaani el al. (2005) studied a wide class of kernel modifications conditioned on the training data and explored their RKHS. Lonescu
ett 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 new family of kernels for 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 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.
Acknowledgments
Research at the Weizmann Institute was partially supported by the Isracl Science Foundation, grant No. 1639/19, by the Israeli Council for Higher Education (CHE) via the Weizmann Data Science Research Center,
11

---

Published in Transactions on Machine Learning Research (02/2024)
by the MBZUAI-WIS Joint Program for Artificial Intelligence Research and by research grants from the Estates of Tully and Michele Plesser and the Anita James Rosen and Harry Schutzman Foundations.
References
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via. over- parameterization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 242 242-252, 2019.
Shun-ichi Amari, Jimmy Ba, Roger Grosse, Xuechen Li, Atsushi Nitanda, Tajji Suzuki, Denny Wu, and Ji Xu. When does preconditioning help or hurt generalization? arXiv preprint arXiv:2006.10732, 2020.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322 332. PMLR, 2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint arXiv: 11955, 2019b.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-688 681, 2017.
Daniel Barzilai and Ohad Shamir. Generalization in kernel regression under realistic assumptions. arXiv preprint ar 2iv: 15995, 2023.
Daniel Barzilai, Amnon Geifman, Meirav Galun, and Ronen Basri. A kernel perspective of skip connections in convolutional networks arXiv preprint or 1t::2211.14100 2022.
Ronen Basri, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural networks for learned functions of different frequencies. In Advances in Neural Information Processing Systems, pp- 4763-4772, 2019.
Ronen Basri, Meirav Galun, Amnon Geifman, David Jacobs, Yoni Kasten, and Shira Kritchman. Frequency bias in neural networks for input of non-uniform density, In International Conference Machine Learning, 2020a.
Ronen Basri, Meirav Galun, Amnon Geifman, David Jacobs, Yoni Kasten, and Shira Kritchman. Frequency bias in neural networks for imput of non-unifen con-uniform density. In International Conference on Machine Learning, pp. 685-694. PMLR, 2020b.
Yuval Belfer, Amnon Geifman, Meirav Galun, and Ronen Basri. Spectral analysis of the neural tangent. kernel for deep residual networks. arXiv preprint 2xXt::204400099 2021.
Alberto Bietti and Francis Bach. Deep equals shallow for relu networks in kernel regimes. arXiv preprint arXiv:2009. 140027 2020.
Benjamin Bowman and Guido Montufar. Spectral bias outside the training set for deep networks in the kernel regime. arXiv preprint wxXiv:220600099 2022.
Mikio Ludwig Braun. Spectral properties of the kernel motrir and their relation to kernel methods in machine learning. PhD thesis, Universitäts- und Landesbibliothek Bonn, 2005.
Francesco Cagnetta, Alessandro Favero, and Matthieu Wyart. How wide convolutional neural networks learn hierarchical tasks. arXiv preprint arXiv:2208.0 01003, 2022.
Tianle Cai, Ruiqi Gao, Jikai Hou, Siyu Chen, Dong Wang, Di He, Zhihua Zhang, and Liwci Wang. Gram- gauss-newton method: Learning overparameterized neural networks for regression problems. orXiv preprint 1rXi::190..1165, 2019.
12

---

Published in Transactions on Machine Learning Research (02/2024)
Yuan Cao, Zhiying Fang, Yue Wu, Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. Xiv preprint or arXiv:2009.01 198, 2019.
David E Carlson, Edo Collins, Ya- Ya-Ping Hsich, Lawrence Carin, and Volkan Cevher. Preconditioned spectral descent for deep learning. Advances in neural information processing systems, 28, 2015.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in neural information processing systems, 32, 2019.
Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Culotta (eds.), Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward doeper understanding of neural networks: The power of initialization and dual view on expressivity. In Advances In Neural Information Processing Systems, pp. 2253-2261, 2016.
Sara Fridovich-Keil Raphael Gontijo-Lopes, and Rebecca Roelofs. Spectral bias in practice: The role of function frequency in generalization. arXiv preprint arXiv:2110.024.0 2021.
Amnon Geifman, Meirav Galm,, David Jacobs, and Ronen Basri. On the spectral bias of convolutional neural tangent and gaussian process kernels. arXiv preprint XrXi:2203300255, 2022.
Kaixuan Huang, Yuqing Wang, Molei Tao, and Tho Zhao. Why do deep residual networks generalize better than deep feedforward networks? a neural tangent kernel perspective. Advances in neural information processing systems, 33:2698- 2709, 2020.
Catalin Ionescu, Alin Popa, and Cristian Sminchisescu. Large-scale data-dependent kernel approximation. In Artificial Intelligence and Statistics, pp. 19-27. PMLR, 2017.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Rodney A Kennedy, Parastoo Sadeghi, Zubair Khalid, and Jason D McEwen. Classification and construction of closed-form kernels for signal representation on the 2-sphere. In Wavelets and sparsity XV, volume 8858, pp. 169-183. SPIE, 2013.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- DicksDicks,nin, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
Jaehoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. Advances in Neural Information Processing Systems, 33:15156-15172, 2020a.
Jason D Lee, Ruoqi Shen, Zhao Song, Mengdi Wang, el al. Generalized leverage score sampling for neural networks. Advances in Neural Information Processing Systems, 14-10755-10788 2020b.
Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora. Enhanced convolutional neural tangent kernels. Xi preprint arXiv:1911.00809, 2019.
Siyuan Ma and Mikhail Belkin, Diving into the shallows: a computational perspective on large-scale shallow learning. Advances in neural information processing systems, 30, 2017.
Siyuan Ma, Racf Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern werrpaaraetrrized learning. In International Conference Machine Learning, pp- 3825-33344 PMLR, 2018
Neil Mallinar, James B Simon, Amirhesam Abedsoltan, Parthe Pandit, Mikhail Belkin, and Preetum Nakkiran. Benign, tempered, catastrophic: A taxonomy of overfitting. Xixiv preprint brXiv:2207.0656) 2022.
13

---

Published in Transactions on Machine Learning Research (02/2024)
Theodor Misiakiewicz and Song Mei. Learning with convolution and pooling operations in kernel methods. arXiv preprint arXim:21 11 108308, 2021.
Mohamad Amin Mohamadi, Wonho Bae, and Danica J Sutherland. A fast, well-founded approximation to the empirical neural tangent kernel. International Conference on Machine Learning, pp. 25061 25081. PMLR, 2023.
Andrea Montanari and Yiqiao Zhong. The interpolation phase transition in neural networks: Memorization and generalization under lazy training. The Annals of Slatistics, 50(5):2816 22-2217672777 2022.
Michael Murray, Hui Jin, Benjamin Bowman, and Guido Montufar. Characterizing the spectrum of the ntk via a power series expansion. arXiv preprint wrXiv:2211.07844, 2022.
Radford M Neal. Bayesian learning for neural networks, volume 118. Springer Science & Business Media, 2012.
Quynh Nguyen, Marco Mondelli, and Guido F Montufar. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks. Tn International Conference on Machine Learning, pp- 5119-8129, PMLR, 2021.
Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 1999.
Roman Novak, Jascha Sohl-Dickstein, and Samuel S Schoenholz. Fast finite width neural tangent kernel. In International Conference on Machine Learning, pp. 17018 17044. PMLR, 2022.
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparancterization Global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, (1):84-105, 2020.
Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito. On learning with integral operators. Journal of Machine Learning Research, 11(2), 2010.
Saburou Saitoh and Yoshihiro Sawano. Theory of reproducing kernels and applications. Springer, 2016.
Bernhard Schölkopf, Ralf Herbrich, and Alex J Smola. A generalized representer theorem. In International conference on computational learning theory, pp. 416-426. Springer, 2001.
James B Simon. On kernel regression with data-dependent kernels. arXiv preprint arXiv:2209.010: 2022.
Vikas Sindhwani, Partha Niyogi, and Mikhail Belkin. Beyond the point cloud: from transductive to semi- supervised learning. In Proceedings of the 22nd international conference on Machine learning, pp. 824-831, 2005.
Zhao Song and Xin Yang. Quadratic suffices for paer-aaraanliiization via matrix chernoff bound. arXiv preprint ar Xix::1900 03599,, 2019.
Ingo Steinwart and Clint Scovel. Mercer's theorem on general domains: On the interaction between measures, kernels, and rkhss. Constructive Approzimation, 35:363-411 2012.
Matthew Tancik, Pratul Srinivasan, Ben Mildenhall, Sara Fridovich-Keil Nithin Raghavan, Utkarsh Singhal, Ravi Ramamoorthi, Jonathan Barron, and Ren Ng. Fourier features let networks learn high frequency functions in low dimensional domains. Advances in Neural Information Processing Systems, 33:7537-775 2020.
Tom Tirer, Joan Bruna, and Raja Giryes. Kernel-based smoothness analysis of residual networks. In Mathematical and Scientific Machine Learning, pp. 921-954. PMLR, 2022.
Alexander Tsigler and Peter Bartlett. Benign overfitting in ridge regression. J. Mach. Learn. Res., 24: 123 2023.
14

---

Published in Transactions on Machine Learning Research (02/2024)
Sifan Wang, Xinling Yu, and Paris Perdikaris. When and why pinns fail to train: A neural tangent kernel perspective. Journal of Compulational Physics, 449:110768, 2022.
Zhichao Wang and Yizhe Zhu. Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks. arXiv preprint or Xix:21009. 200.00909,99 2021.
Christopher KT Williams. Computing with infinite networks. In Advances in neural information processing systems, pp. 295 301, 1997.
Lechao Xiao. Eigenspace restructuring principle of space and frequency in neural networks. In Conference on Learning Theory, pp. 4888 4944. PMLR, 2022.
Zhi-Qin John Xu, Yaoyu Zhang, Tao Luo, Yanyang Xiao, and Zheng Ma. Frequency principle: Fourier analysis sheds light deep neural networks. arXiv preprint arXfc:1911.06523, 2019.
Zhi-Qin John Xu, Yaoyu Zhang, and Tao Luo. Overview frequency principle/spectrall bias deep learning. arXiv preprinl Xrx::22001. 0.3395, 2022.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural langent kernel derivation. orXiv preprinl 1902 2019.
Greg Yang. Tensor programs ti: Neural tangent kernel for any architecture. arXiv preprint arXiv:200611554. 2020.
Greg Yang and Hadi Salman. A fine-grained spectral perspective on neural networks. ar preprint arXiv:1907.10599, 2019.
Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks. arXiv preprint arv: 03888, 2017.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsich. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv preprint arXiv: 00962,, 2019.
Guodong Zhang, James Martens, and Roger B Grosse. Fast convergence of natural gradient descent for over-parameterized neural networks. Advances in Neural Information Processing Systems, 32, 2019.
15

---

Published in Transactions on Machine Learning Research (02/2024)
A Convergence of PGD
In this section we prove Theorem 4.1 We begin with assumptions and notations for the proof. The assumptions follows those of Lee el al. (0019)
1. The width of the hidden layers are identical and equal to
The analytic NTK K is full rank with Amin (K) O.
3. The training set (x, 36 is contained in some compact set.
4. The activation function P satisfies
|e(0),, I supazz(ld(s)) -
//(2)///1= <
The network parametrization is as follows
xx)
(() (x) WOgg (()))((() + D E ER", 1=
(x) (x) [(x, w) (((-1) w(L+1), (o(ltt).g(()p gg())()) + ((L+1)
g
p (F(((x)) E ERR 1= I=
The network parameters w include W(++1) W(O, ..... W(I,, where W Rdxx 1, b(t) EA w((+)) e I Rixdı, b((+1) RR, is the activation function. The network parameters are initialized with N(0, a) for except for the biases (b("..... "i......(,),,, b(T++)), which are initialized with (0,
Cp 1/ (E.=Woon))p(
We further set at the last layer Cp for small constant
For the ease of notation the following short-hands:
f(w.) f(X, w.) E R
(15)
f(X, - Y E R
(16)
J(w.) = VS(X, wx) E "xp
(17)
The empirical and analytical NTK is defined as
K; == J(w)) m
K = limm
Since f(X, wo) converge in distribution to gaussian process with zero mean, we denote by Ro the constant such that with probability at least (1- - 66) over the random initialization
||Te|| S Ro
(18)
Likewise we have that with the same probability |[[X, woll s nCo for a constant Co. Finally, our PGD updates are
WA+1 w. ww) Sr.
TSr
(19)
We let Amiin := Amin (KS). Our proofs are carried out for fixed preconditioner S which does not depend on 6. However, the same proofs would hold for S, which changes with t, if one makes the additional assumption that ||S&]] is uniformly bounded for all t. Of course, if S is fixed, then ||S]] is finite and thus trivially bounded. This used Lemma A.1 and we will make its use clear.
The bounded dataset of Assumption used for simplicity in two places and can in both cases, be weakened. The assumption is first used to ensure that the kernel has Mercer decomposition, in Eq. ① Weaker
16

---

Published in Transactions on Machine Learning Research (02/2024)
assumptions (which are slightly complicated) can be used in this case (Steinwart & Scovel 2012). For example, one has a Mercer decomposition if X is Hausdorff space (any metric space suffices). the kernel function is contimuous, μe is a probabiity measure, and the function h(x) := k(z x) has finite L2 norm. The boundedness assumption also used to bound f at initialization. However, even for many unbounded dist / can be bounded with high probability. As such, both requirements are satisfied by many unbounded distributions, such as Gaussians, and our statements can thus be naturally extended many such unbounded distributions.
Lemma A.1. There is a R. > 0 such that for every C O, with high probobility over random imitialization the following holds Vw, w B(wo, Cm-1/2):
vm (w) ((w)) S / w
[J(w) K
mm
Proof. Using sub-multiplicatiiity of the Frobenius norm,
[[([(w) - J(W))SllF
[I([(w) J(W))ll ||5||
Vm
< (2) || |w w|| =: ||w w|
where (1) is given by Lemma (1) of Lee et al. (2019) and == ||اا which is constant since ||||| is bounded. The second part of the theorem can be shown using the same two arguments.
Lemma A.2. (Lemma 4.2 from the poper) For 8p > O, Amar (KS)) Amx+ (K3) lo and S such that S > 0, there crist C 0, N E N and k > dn over random initialization. When applying preconditioned gradient descent as in (7) with learning rale no/m
such that for every 2 N, the following holds with probability at least
||rell2 S (1- Mdmmn )'c
Σj=1 |[W; -ij-lll 5
3xC -1/2 Amin
3. sup, |I(Ko - K.)S1l <
C Aman m 1/2
where Amin is the minimal eigenvalue of KS.
Proof. We begin by proving parts (1) and (2) in the theorem with x defined by Lemma A.1 induction where the base case for = 0 is clear. For >> O we have that
We do that by
W well snllJ(w))S 11rel2 5 (1- (1- Amain
Rosmom 11/2
3
Implying that
Σ |w wyll & Rornom -1/2
1/2
Σ
Aa
1 3xHo 1/22
Xmin
Which concludes part (2) of the theorem.
17

---

Published in Transactions on Machine Learning Research (02/2024)
For part (1) use the mean value theorem get that
||r+1 = || - re + rell
[J(w)) - we) + rell (t,
Sr, rell
< [ ().( $112 ||re|l
< (w.( S112 (1 Mu
Ro
where W, is some point on the line between We+1 and W,. It remains to show that with probability at least (1 20/2) holds that
mo-mm
| - ([.:)
3
We show that by observing that S doesn't change the convergence in probability so KoS - KS as in Yang 2219 therefore we can choose large enough m such that
|KS - KoSlpp S Am
3
Therefore we get
|| (W. (w:)² "F 8112
< ||/ mK - no [I( - Ko)S112 + -
< (1 Ammn + D0dmin + 2n) 3o m 112 <
700mmn
3
Amiin
which concludes part (1).
For part (3) we verify that using Lemma A.1
1
[Koo K.)S1I [(J(wo)J[wo)) - -J(w.)](w:)""))
(20)
< m
(IIJ(wo))lls [(wo)² J(w.) + + [l](w,) - [(wo)llal]](w: (()F))
(21)
6x Ro 1/2
< 2x² |wo well2
(22)
Amin
0
Next prove the preconditioned dynamics given in 4.1
Theorem A.3. (Theorem 4.1 from the paper) Let d0 > 0, (K) > To E> 0 and S such that
S 0. Then, there erists N E N such that for every m 2 N, the sollowing holds with probobitity al least
1 - do over random initialization when applying preconditioned gradient descent with learning rate n no/ m
= (I - K
where ||El12 I E.
Proof. By using the mean value theorem we have that
I(1 T(+1 +I: ri J(W)((((1 wt) +r,
(I) (w: Sr, +r, = (w: S) m([(W) -J(W:))((w)) Sr
(2) no S)r, mo((K:-K)s)t - (w: Sr.
18

---

Published in Transactions on Machine Learning Research (02/2024)
where (1) is by the gradient descent definition and (2) is by K, definition.
Now applying the theorem inductively we get
T++1 = (1- Σ
(1 mKK i)
((T)
Next we bound the norm of c(t) = "To(Ki K)Sr, n[((w) - J(wa)) Sr.. For term A we have
Ilo((K, (0)-K,1)r I no(]((K, - Ko))llop + l1(Ko K)S) op) ||r|12
10 6x²h Ro m -1/2 + Amine
6x Ro
-1/2 emmin
n0
Ro
m
Amin
20
Amin
2
where (1) follows from Lemma
4.2 and the fact that KoS KS probability Yang (219). (1) holds
when is sufficiently large.
For term B we have that
[[w(](W) J(w.)))(w.)"
710
m [[((] J(we)llo [[(e,))r
71o [[( J(w))llop [w( (ww.
||rell2 5(1) non² 2 w well Ro
m
22)) no (W-1-- - Ro S 16 Rd
(33)
mm
where (1) is by Lemma A.1 and (2) it by Lemma 4.2
Therefore we have
= (1 - nKS) +((t)
where
1
[[{())]
Σ (1
f(X, wo)
Σ (I KS)
nhx² Rgg
6x Ro
+
edmin!l0
-||[[= sXX,)
m
Amin vm
2
Gx Ro
Edmin 710
dmm JC
Vm
Amin v m
2
x2 R2
3
edmin
+ (1
m' 'vo
mm
Amin vm
2
no R3
6K Ro
c/2 +
+ - 1--oommmn
Vm
Amin m
So by choosing m to be large enough and
conclude the theorem.
3Cg
B Convergence Analysis
Under the settings Sec. 4.2 we here prove the following lemma.
Lemma B. (Lemma 4.3 from the puper)
1. Let Wo E TRP and 6(x)= vf(x, wo), it holds that w w*
19

---

Published in Transactions on Machine Learning Research (02/2024)
2. Let 6u > O, nu < such that S O. Then there ewists N N such that for every m 2 N, the following holds with probability at least 1 - d0 over rondom initialization of wo when applying preconditioned gradient descent to both J and h with learning rale lt 7//m
(KS) O, E be test point, T 0 number of iterations and
11(x, w/) f(x, wT)l S..
where w' is as in
Proof. For point (1), applying lemma B.2 yields h(,, w*) Ei= of (o(x), o(x.) with
with the kernel k(x,2) (6(x), o(x)) (and kernel matrix Ko)
(Ko -5-11) y:
which uniquely determines that w Ei= a (x,).
When 7 - 0 this becomes the same minimizer as of the standard kernel ridge regression problem with [[w)= [|](X, w) >112 (or equivalently, substituting S T).
Point (2) is proved in lemma B.3
Lemma B.2. Let k(x, z) - (o(x), ((z)) be any kernel and [K]i k xxj be its kernel matria. Given S 0, O, let Ls(f) = 1 { - y) + Ilfll (where 7 > 0 is some regularization term). Then the unique minimizer fr = arg minw I(w) takes the from (*) = -/= of (Ø(x), ((x))) with
a = (K + +
Proof. The Representer Theorem (Schölkopf et al., 2001 states that any minimizer the kernel ridge regression problem f = arg min Ls(f) is of the form f*(x) E of (6(x). ((x:))
Then (X) can be written as Ka* and || 1/44 a² T Ka" So we can equivalently solve for:
a" = min _ ack 2
s - o Ka,
where Kij = min min TT - SKa+yy
Now opening up the norm we gel:
a" arg Then K, S are symmetrie, and Sy doesn't 't depend the above simplifies to:
2 la Ka.
Kaa
a TTTTT KT SKa - KTT Sy + Y a Ka TKo
a" = arg min min
2
2
1 a (KSK a K
arg min
Now deriving with respect to and setting to we obtain:
(KSK+ + +K)a KSy KS ((K + a y)
As K > and S > 0 it must hold that:
0 = (K + 7 yy
Since the loss is convex, a² (K + ----11111 y is the unique minimizer.
20

---

Published in Transactions on Machine Learning Research (02/2024)
Lemma B.3. For du O, Aman (ma)) (KS) nu , , Rd be test point, T 0 number of iterations and S such that > 0, there erists N E such that for every m Z N, the following holds with probability at least - bu over random initialization of wo when applying preconditioned gradient descent to both and h with learning rale 1//m
x
Kw'r, (x( f(x, f(x,W)))
where w'
13
Proof. Let x, be some data point and its label, which are not necessarily in the train set. Denote by F. f(x, w.) y, and J((w) (x(, w). We define lincarized model (x, w') = f(x, wo) J(wo)w' where w/ is as in 13 In partieular, note that flim(x, w6) f(x, wo).
Let h(x, w) = (w, Vx(x,, wo)). By the triangle inequality,
I1(x, w/) - f(x, wT)l S [xl" w/) f(x, wT)l + [f(x, wo)l
The weights of the last layer are initialized (V, with some constant which may choose. Thus, by taking small enough v, [f wo)l with the desired probability. Notice that F f. fui (x, w/) f(x, w.) and such, it remains to show that F4 FT
2c 3
By the mean value theorem, there exists some w s.t
Fet1 - f; = J(W) we)
= (1) [nnnj[(w)J( T -nn
([((W) (ww)) Sr. (2) - (x X) - ()((((((xxX) Kolx, X)) - [-][([]])) - ((w)))
<(x.t)
where (1) is by the gradient descent definition and (2) is by K2 definition.
Thus, taking a telescopic series we get that for every t.
T
iT = ro + Σ F441 - r, = To
110
Σ
(Ko(x, + =((x,))
2=0
==0
Now for the linear model, by definition of our PGD updates we have
w 2+1 G = (ww") Srlin = =-nJ(wo)" Sr
and by definition of the linearized model,
plan (x, w(11) (xx w() =f(x, wo) + J [(wo)(W(+z) (ʃ(x, wo) + J[wo =i(ww) - w/) = =m]())))(www)) Sr!
- (X, X)
And so
p/in = -o (iooxxx)).t Sr
1+1
Thus, taking telescopic scries get that for every t,
plin i!/nn
110
Ko(x,X)St
Now we can compare
between the linearized and non linearized versions. Since F/in = Po we have
plin F, Kxx
Σ
iin
Σ
E(xx,)
r
i=0
1=0
21

---

Published in Transactions on Machine Learning Research (02/2024)
Notice that r/im (I - Soro Theorem 4.1 combined with choosing sufficiently small, states that
r; (T KS)ro + E() with I&&ll - 0. Analogousl, one could also show (7 - -oooo + {(i) by
replacing K in the proof with Ko- As such, for every < T, || rell [|(())] with ||&ll| - 0. Now by Cauchey Shwartz and the triangle inequality get:
T-1
pin T Fr| S 1o X)SI|
kn r:ll
+
Σ 1
{xx,
i)
- =1110Ko(x, X)SI|
||(()]
+
Σ
<(x, i)
==
< ()x
[|(())] +
max USiST-1
E(x,
0SiST-1
Now each E(i) tends to 0 as m tends to infinity. So there exists some No E N s.t for all m No. m [|E())]l Kotxx)) so that the entire left hand side is at most 3.
It remains to bound |maxosigt-1 i)l. Fix some to be the argmax. Recalling the definition of e(x, t) and using the fact that r, is bounded by Lemma 4.2 it suffices to bound (Ko(x,X) - K2(x, X)S and (J(w) - (w.)))
((o((, - -)
-xx,x = [[((w)))(wo)) (())
m [I(((w)) -wwo))(wi)) (J(wo)J(w:)) -( -
(I|((wo)]la (l(
+ - "s
J(
6r² Ro Amén
$ 2x² |wo- ww-llll2 S
m 1/2
where the last inequality holds since Lemma
A.1 holds analogously for . and using Lemma 4.2 for [[o wellg-
(J(w) ((w))) can be similarly be bound by applying by Lemma A.1 there is some N1 s.t the entire right hand side is at most 5.
analogously to 23 As such
Taking N max completes the proof.
C Consistency of Spectral Engineering
Theorem C.I. (Theorem 3.2 from the paper) Let k(x,z) Ez_ (x) and kzy(x,
Ii (x) be two Mercer kernels with non-zero eigenvalues {)r), (9(Ai)} and eigenfunctions (o:) such that Vx X, (x(x)) S M. Assuming g is L Lipehilz. Let K, Kg be the corresponding kernel
matrices on i.idd samples X1, Xn. E X. Define the kernel matriz Kg = VDVT where V = (V1,.., vn) with the i'th eigenvector of K and is diagonal matria with Dic = g(3x) where &n is the i'th eigenvalue of K. Then, for
[Kg Kgllr 23 0,
where a.s. stands for almost surely.
Proof. From the Mercer decomposition of k, we have that
K Σ g(Ax) (x)
22

---

Published in Transactions on Machine Learning Research (02/2024)
where (x( t (0)(x)), ((,(2))).,,((((( E R..
We also define
R {
Kg :
(X)x
k=
K>R = Σ
k=R
Let V1,.., Vn be the cigenvectors of K (and therefore of Kg) and fix R > 0. Then we have
n
|| Kg - -Kyll s 11, k5 + || = || F +
Σ 1=1
(Kgg - K2 yr Jv,
= =| F +
Σ Lo(igly - KS v, -K5
=1 =|| R
(0(2))2-20)) 20(4,)V,, + (Kz Mr KJ Kv
F
=||K3 R
Σ (VF (XX ))
n -(0))²-20(A)) 20(A,) Σ oz
Since L1, D2, are orthonormal, and (x1x),.., (xx) are ii.d, by the law of large numbers it holds that ox(X) (xx - Ed = ōig, therefore, the last term converges a.8 to
R Σ (08))-29(0) Σ (x))) + E ))
R
|| || F +
Next use Braun 2005
Theorem 4.10 and Equation 4.15) to get that
1 if 4 is an eigenfunction of A
(vF
(x))2
0 else
==1
Which implies that
R g(Ax): (v]))(X))) (A,
Therefore we get that
R
Σ (( + ||
[R, - Kolle S 11 K5R + +||3R
Σ
(o(2g)) - ((A,))
-
1=1
(2100) (Propasition 10) we get (o(()) - g(2,))² < L2 DEh (ag -2,3² so by applying Rosasco et al.
Finally, from the Lipchitzness,
n Σ - o(21))2 Σ Eo(2) || - || +
R=R
1=
Observing that || 1| + (i + 0 give us the desired result.
23


Reviews:
[{"review_id": "7ClsYTn93j", "reviewer": "Reviewer_UzTC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The constructed kernels have potential applications in studying neural networks. The realization of the potential could be strengthened for some concrete settings.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors introduce modified spectrum kernels which can approximate kernels with desired eigenvalues and be used for studying gradient descent methods for training parameters of neural networks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Some references should be updated.", "broader_impact_concerns": "The concerns in the previous round have been addressed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hcplfaVERd", "reviewer": "Reviewer_VKSy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Upsides: ##\nThis paper is technically solid, focusing on a very well-defined problem for infinite-width or very wide NNs. The written quality of this paper is good. I am able to understand the main point well and the method of proof itself is reasonable and classical. The experiments match the theoretical results of this paper.\n\n\n## Downsides: ##\n1. Modified Spectrum Kernels (MSKs) rely on the spectral decomposition of the neural tangent kernel (NTK) and PGD may rely on the inverse of the NTK, e.g. experiments in Figure 1. However, computing NTK or the empirical NTK for a large sample size is computationally hard. Sometimes, we may need some approximation methods to approximate NTK, like [1-3] below. I think the authors should provide some discussion for the computational issue of the MSK method and what the benefit of this method is for practice. \n\n2. Poor written quality in the proof in the Appendix. I checked the proofs in the Appendix and there are many typos therein (see below as well). Some notions are not clarified at the beginning. For instance, in the Appendix, some norms $\\\\|\\cdot\\\\|$ are not clarified as operator norm or Frobenius norm at all. \n\n3. The MSK method relies on function $g(\\cdot)$, initialization of the training parameters and truncation index $k$. The authors did not provide enough details for how the choose these parameters in practice. The authors should provide more discussions in Section 4.3 and provide more experiments with different $g(\\cdot)$, initialization of the training parameters, and truncation index $k$ to present the advantages and limitations of this method.\n\n4. The main theorems should be stated in more detail. In Theorem 4.1 and Lemma 4.2, so far, I do not know how to ensure $\\lambda_{\\min}(K)>0$ and how this convergence rate for PGD relies on the training sample size $n$ and input feature dimension $d_0$. There are many previous results that proved these properties for GD training, e.g. [4-8]. The authors should include some discussions related to the conditions 1-4 on page 14.\n\n=======================================================================================================\n\n[1] Novak, et al. \"Fast finite width neural tangent kernel.\"  \n\n[2] Mohamadi, et al. \"A fast, well-founded approximation to the empirical neural tangent kernel.\"  \n\n[3] Engel, Andrew, et al. \"Robust Explanations for Deep Neural Networks via Pseudo Neural Tangent Kernel Surrogate Models.\"\n\n[4] Nguyen, et al. \"Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks.\"  \n\n[5] Montanari and Zhong. \"The interpolation phase transition in neural networks: Memorization and generalization under lazy training.\"  \n\n[6] Wang and Zhu. \"Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks.\"  \n\n[7] Oymak and Soltanolkotabi. \"Toward moderate overparameterization: Global convergence guarantees for training shallow neural networks.\" \n\n[8] Wang, et al. \"Spectral evolution and invariance in linear-width neural networks.\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considered a preconditioned gradient descent (PGD) for wide neural networks (NNS) to accelerate the speed of convergence rate of PD in each eigenspace of the NTK. The authors proved the convergence rate of this PGD and showed that the predictor of GD training is approximately equivalent to the PGD training when the width is sufficiently large. Inspired by the spectral bias of NNs, the authors provided a new algorithm for PGD to control the spectral bias and gain a faster convergence rate for NNs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. What would be the dataset assumptions in Theorem 4.1 and Lemma 4.2? Can you go beyond compactly supported datasets and consider datasets like isotropic Gaussian datasets? What is the random initialization of NN in Theorem 4.1 and Lemma 4.2? There should be some discussion in the Section 4.1.\n2. In Theorem 3.2, $(3.1)$ should be change to Definition 3.1.\n3. On Page 3 above Kernel Construction with MSKs, the equation related to $\\sum_{i=l}^d(v_i^\\top \\Phi(X))^2$ should be double-checked. What is $l$ here?\n4. On Page 6, when discussing the second-order method with the Fisher information matrix, why can we consider $S=K_t^{-1}$? Does that mean we can consider preconditioning $S$ changing over the time $t$? This requires more discussion. Why PGD method in this paper can cover this method?\n5. The second paragraph on Page 6 is repeated with the first paragraph. Please rewrite this part.\n6. In the proof of Lemma A.1, how do you ensure $\\\\|S\\\\|_F$ is bounded which is not clear to me? Please provide more details for this proof or if there is some assumption on $S$. \n7. What is $\\bar \\lambda_{\\min}$ in the proof of Lemma A.2?\n8. The first sentence on Page 17 needs to be revised.\n9. Typos in Lemma B.2.\n10. On Page 19, in the proof of Lemma B.3, why can you use Lemma 4.2 to conclude that $\\\\|\\xi_i\\\\|\\to 0$ as $m\\to \\infty$? This convergence is in which sense? There should be more explanations.\n11. On Page 21, in the equation of $\\sum_{i=1}^d(v_i^\\top \\Phi(X))^2$, why it will converge to 1 if $\\Phi$ is an eigenfunction of $\\lambda_k$?", "broader_impact_concerns": "Not very applicable here.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "myGODjLqnL", "reviewer": "Reviewer_wmuT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n- In general, the paper is well-written. Background information and relevant literature are adequately covered. Technical developments of the work are rigorous, intuitive, and well-founded from existing works.\n- The paper introduces several major technical contributions to the problem of interest, including:\n    - using MSKs to manipulate the spectrum of existing kernels\n    - using preconditioned gradient descent method to alter the trajectory of gradient descent toward the modified kernels (and thus control the spectral bias of wide neural networks)\n    \n    The proposed approaches would be of broad interest in the machine-learning community from both theoretical and algorithmic viewpoints.\n    \n- The mathematical quality of the work is high. Proofs seem to be rigorous and correct.\n- The manuscript also obtained several results with interesting implications:\n    - The example in Section 4.3 (making the top k + 1 eigenvalues equal to each other) leads to an exponential improvement over vanilla gradient descent (in learning the same eigenfunction).\n    - While the results of Theorem 4.1 seem to be of the same spirit as the main results of (Arora 2019), they utilize the framework of (Lee et al 2019) for deep networks and the coverage of the result is much broader.\n\n### Weaknesses\n\n- No weakness was noted. One minor point is that I feel the result of Section 4.3 (which would be one with the greatest practical implications) is quite underwhelming in comparison to prior developments. Little information/discussion is provided on the required properties and the effects of the control function $g$ beyond the given example.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The manuscript studies the problem of controlling the inductive bias of wide neural networks by modifying the NTK kernel’s spectrum. This is done through the introduction of Modified Spectrum Kernels (MSKs), a family of constructed kernels that can be used to approximate kernels with desired eigenvalues for which a closed form is unknown. The approach then proposes a preconditioned gradient descent method, which alters the trajectory of gradient descent, yielding significant convergence speedups for training wide neural networks without changing the final solution.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- There is a duplicate sentence on Page 6\n- [Optional] I suggest making the example (making the top k + 1 eigenvalues equal to each other) in Section 4.3 an indexed result (i.e., a Remark/Corrolary).", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors have already made several improvements and all reviewers vote for either Accept or Leaning Accept. One reviewer mentions 
"..., I am not convinced by the author's explanation of computing efficiency. They claim their method still results in more efficient optimization in the over-parameterized regime by comparing with the NTK results from (Song & Yang, 2019) and showing that inverting K or calculating its eigenvalues is cheaper than computing the gradient. But Song & Yang did not obtain the optimal width for NTK theory. I do not think this is a convincing evidence."
I suggest a minor revision, where the authors either provide more evidence for their claim, or appropriately qualify their claim (e.g. an improved sentence or paragraph along the lines of "our method results in more efficient optimization in the over-parameterized regime comparing with known methodology relying on the NTK (Song & Yang, 2019), however we note that Song & Yang were not able to obtain the optimal width, ..."
Decision: Accept (poster)