A Fine-Grained Spectral Perspective on Neural Networks
Authors: Greg Yang
Hadi Salman
Venue:  (2020)
Keywords: Neural Tangent Kernel
Neural Network Gaussian Process
Spectral theory
Eigenvalues
Harmonic analysis

Abstract: Are neural networks biased toward simple functions?
Does depth always help learn more complex features?
Is training the last layer of a network as good as training all layers?
These questions seem unrelated at face value, but in this work we give all of them a common treatment from the spectral perspective.
We will study the spectra of the *Conjugate Kernel, CK,* (also called the *Neural Network-Gaussian Process Kernel*), and the *Neural Tangent Kernel, NTK*.
Roughly, the CK and the NTK tell us respectively ``"what a network looks like at initialization" and "``what a network looks like during and after training."
Their spectra then encode valuable information about the initial distribution and the training and generalization properties of neural networks.
By analyzing the eigenvalues, we lend novel insights into the questions put forth at the beginning, and we verify these insights by extensive experiments of neural networks.
We believe the computational tools we develop here for analyzing the spectra of CK and NTK serve as a solid foundation for future studies of deep neural networks.
We have open-sourced the code for it and for generating the plots in this paper at github.com/jxVmnLgedVwv6mNcGCBy/NNspectra.

Under review as a conference paper at ICLR 2020
A FINE-GRAINED SPECTRAL PERSPECTIVE ON NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Are neural networks biased toward simple functions? Does depth always help learn more complex features? Is training the last layer of a network as good as training all layers? How to set the range for learning rate tuning? These questions seem unrelated at face value, but in this work we give all them a common treatment from the spectral perspective. We will study the spectra of the Conjugate Kernel, CK, (also called the Neural Tangent Kernel, NTK. Roughly, the CK and the NTK tell us respectively "what network looks like initialization" and "what a network looks like during and after training." Their spectra then encode valuable information about the initial distribution and the training and generalization properties of neural networks. By analyzing the eigenvalues, we lend novel insights into the questions put forth at the beginning, and we verify these insights by extensive experiments of neural networks. We believe the computational tools we develop here for analyzing the spectra of CK and NTK serve as a solid foundation for future studies of deep neural networks. We have open-suurced the code for it and for generating the plots in this paper at g titb.b..... com wttp////m/////////t/////m///mmpt XXV.nLggddv 6mNcGCBy NNspect.
Gausssann Process Kemnel. and the Neural
INTRODUCTION
Understanding the behavior of neural networks and why they generalize has been central pursuit of the theoretical deep learning community. Recently. Valle-Pérez et al. (2018) observed that neural networks have a certain "simplicity bias" and proposed this as a solution to the generalization question. One of the ways with which they argued that this bias exists the following experiment: they drew a large sample of boolean functions by randomly initializing neural networks and thresholding the output. They observed that there is a bias toward some "simple" functions which get sampled disproportionately more often. However, their experiments were only done for relu networks. Can one expect this "simplicity bias" to hold universally, for any architecture?
A priori, this seems difficult, as the nonlinear nature seems to present an obstacle in reasoning about the distribution of random networks. However, this question turns out to be more easily treated if we allow the width go to infinity. A long line of works starting with Neal (1995) and extended recently by Lee et al. (2018); & Novak et al. (2018); Yang (2019) have shown that randomly initialized, -nfittte-width networks
distributed Gaussian processes. These Gaussian processes also describe finite width random networks well (Valle Pérez et al. 2018). We will refer to the corresponding kernels the Conjugate Kernels (CK), following the terminology of Danicly et al. (016). Given the CK K, the simplicity bias of a wide neural network can be read off quickly from the spectrum of K: If the largest eigenvalue of K accounts for most of tr K, then a typical random network looks like a function from the top eigenspace of K.
In this paper, we will use this spectral perspective to probe not only the simplicity bias, but more generally, questions regarding how hyperparameters affect the generalization of neural networks.
Via the usual connection between Gaussian processes and linear models with features, the CK can be thought of as the kernel matrix associated to training only the last layer of wide randomly initialized network. It is a remarkable recent advance (Jacot et al. 2018 Allen-Zhu et al. 2018a Du et al. 2018) that, under certain regime, a wide neural network of any depth evolves like linear model even when training all parameters. The associated kernel is call the Neural Tangent Kernel. which is typically different from CK. While its theory was initially derived in the infinite width setting, Lee al. (2019) confirmed with extensive experiment that this limit predictive of finite width neural networks as well. Thus, just as the CK reveals information about what a network looks like at

---

Under review as a conference paper at ICLR 2020
initialization, NTK reveals information about what network looks like after training. As such, if we can understand how hyperparameters change the NTK, we can also hope to understand how they affect the performance of the corresponding finite-width network.
Our Contributions In this paper, in addition to showing that the simplicity bias is not universal, we will attempt first step at understanding the effects of the hyperparameters on generalization from a spectral perspective.
At the foundation is spectral theory of the CK and the NTK the boolean cube. In Section 3
show that these kernels, as integral operators on functions over the boolean cube, are diagonalized by the natural Fourier basis, echoing similar results for over the sphere (Smola et al. [200]. We also partially diagonalize the kernels over standard Gaussian, and show that, as expected, the kernels over the different distributions (boolean cube, sphere, standard Gaussian) behave very similarly in high dimensions. However, the spectrum is much casier to compute over the boolean cube: while the sphere and Gaussian eigenvalues would require integration against a kind of polynomials known as the Gegenbauer polynomials, the boolean ones only require calculating a linear combination of small number of terms. For this reason, in the rest of the paper we focus on analyzing the cigenvalues over the boolean cube.
Just as the usual Fourier basis over R has a notion of frequency that can be interpreted as a measure of complexity, so does the boolean Fourier basis (this is just the degree; see (Section 3.T. While not perfect, we adopt this natural notion of complexity in this work; "simple" function is then one that is well approximated by "low frequencies."
This spectral perspective immediately yields that the simplicity bias is not universal (Section 4). In partieular, while it seems to hold more or less for relu networks, for sigmoidal networks, the simplicity bias can be made arbitrarily weak by changing the weight variance and the depth. In the extreme case, the random function obtained from sampling a deep erf network with large weights is distributed like a "white noise." However, there is very weak sense in which the simplicity bias does hold: the eigenvalues of more "complex" eigenspaces cannot be bigger than those of less "complex" eigenspaces (Thm 4.J).
Next, we examine how hyperparameters affect the performance of neural networks through the lens of NTK and its spectrum. To do so, we first need to understand the simpler question of how a kernel affects the accuracy of the function learned by kernel regression. A coarse- grriineg theory, concerned with big-O asymptotics, exists from classical kernel literature YYao et al. 2007| Raskutti et al. 2013; Wei et al.) Lin and Rosasco, Schölkopf and Smola 2002). However, the fine-grained details, required for discerning the effect of hyperparameters, have been much less studied. We tfaactticc
make a first attempt at a heuristic, fractional variance (i.e. what fraction of the trace of the kernel does eigenspace contribute), for understanding how minute change in kernel effects change in performance. Intuitively, if an eigenspace has very large fractional variance, so that it accounts for most of the trace, then ground truth function from this eigenspace should be very easy to learn.
Using this heuristic, we make two predictions about neural networks, motivated by observations in the spectra of NTK and CK, and verify them with extensive experiments.
Deeper networks learn more complex features, but excess depth can be detrimental as well. Spectrally, depth can increase fractional variance of an eigenspace, but past an optimal depth, it will also decrease it. (Section 5) Thus, deeper is not always better.
Training all layers better than training just the last layer when it comes to more complex features, but the opposite is true for simpler features. Spectrally. fractional variances of more "complex" eigenspaces for the NTK are larger than the correponding quantities of the CK. (Section 6)
Finally, we use our spectral theory to predict the maximal nondiverging learning rate ("max learning rate") of SGD (Section 7).
In general, we will not only verify our theory with experiments on the theoretically interesting distributions. i.c. uniform measures over the boolean cube and the sphere, or the standard Gaussian, but also confirm these findings real data like MNIST and CIFARIO
'The code for computing the eigenvalues and for reproducing the plots of this paper is available at hithib com/ /tr/jjvvmmmm htw.m/mm..gedwwww///eeeeyy.y//y/ wwwp://wwwwccyyeeeeetteeee WNspectraaaapaaaaaaooooammaaaaaa which will he open sourced upon publication.
2

---

Under review as a conference paper at ICLR 2020
For space concerns, we review relevant literature along the flow of the main text, and relegate more complete discussion of the related research landscape in Appendix A
KERNELS ASSOCIATED TO NEURAL NETWORKS
As mentioned in the introduction, we now know several kernels associated to infinite width, randomly initialized neural networks. The most prominent of these are the neural langeni kernel (NTK) (Jacol et al. 2018) )) and the conjugate kernel (CK) (Daniely et al. 2016), which is also called the NNGP kernel (eee al. 2018). We briefly review them below. First we introduce the following notation that we will repeatedly use.
Definition 2.1. For Φ : R + R, write V for the function that takes PSD (positive semidefinite) kernel function to a PSD kernel of the same domain by the formula
E (o(K)(r,x')= (~))(.)))
of (((=))))((())
Conjugate Kernel Neural networks commonly thought of as learning high-quality embedding of inputs to the latent space represented by the network's 's last hidden layer, and then using its final linear layer to read out a classification given the embedding. The conjugate kernel is just the kernel associated to the embedding induced by a random initialization of the neural network. Consider an MLP with widths (n') Jt weight matrices {Wi E R= xx" xn'""" }1. and biases {b' E R" }. = 1.... L. For simplicity of exposition, in this paper, we will only consider scalar output n² 1. Suppose parametrized by the NTK parametrization, i.e. its computation is given recursively as
1o (x))
Tu
Whx oabb and 11(x) = Vn!
W
+ obbl
(MIP)
Vno
with some hyperparameters Tw, 0% that are fixed throughout training At initialization time, suppose W I/_ NO, 1) for each E [n'), 3 E [n' It can be shown that, for each a E [n'].. ]. A is
Gaussian process with zero mean and kernel function E' the limit as all hidden layers become infinitely wide (n' 00,1 1...., L 1), where E' is defined inductively on l as
Σ (x, def (n)) (x, x²) + oz.
D def o 2 Vo
(CK)
The kernel E corresponding the the last layer L is the network's conjugate kernel, and the associated Gaussian process limit is the reason for its alternative name Neural In short, if we were to train linear model with features given by the embedding + (xx when the network parameters are randomly sampled as above, then the CK the kernel of this linear model. See Daniely et al. 22166; Lee et al. (2018) and Anppeddxx F for more details.
process kernel.
Neural Tangent Kernel On the other hand, the NTK corresponds to training the entire model instead of just the last layer. Intuitively, we let be the entire set of parameters (W"} U {b'} of Eq. (MLP) then for 0 close to its initialized value dg we expect
*x; 0) - 1 (z; 0n) R (Voh" (x; 0o),0 - -00)
via a naive first-order Taylor expansion. In other words, h=; 0) h (x; 6o) behaves like linear model with feature of x given by the gradient taken w.r.t. the initial network, Voh~(z (x; 0g). and the weights of this linear model are the deviation 0 0g of from its initial value. turns out that, in the limit all hidden layer widths tend to infinity, this intuition is correct (Jacot et al., 2018 Lee et al. 2018 Yang 2019), and the following inductive formula computes the corresponding infinite-wide width kernel of this linear model:
def
e 0x x²) def ('x,aa') + 0 (x. Var (V'- (x,,
(NTK)
Computing CK and NTK While in general, computing Vo and Var requires evaluating multi- variate Gaussian expectation, in specific cases, such when & = relu erf, there exists explicit, efficient formulas that only require pointwise evaluation of some simple functions (see Facts F. and F22). This allows us to evaluate CK and NTK set X' of inputs in only time =
PSDD with learning rate in this parametrization is roughly equivalent to SGD with learning rate a/ widdh in the standard parametrization with Glorot initialization; see I.ee et al. (018)
3

---

Under review as a conference paper at ICLR 2020
What Do the Spectra of CK and NTK Tell Us? In summary, the CK governs the distribution of a randomly initialized neural network and also the properties of training only the last layer of network, while the NTK governs the dynamics of training (all parameters of) a neural network. A study of their spectra thus informs us of the "implicit prior" of randomly initialized neural network as well as the "implicit bias" of GD in the context of training neural networks.
In regards to the implicit prior at initialization, we know from Lee al. (2018) that randomly initialized network as in Eq. (MLP) is distributed as a Gaussian process N (0, K). where K the corresponding CK, in the infinite- width limit. If we have the eigendecomposition
K
Σ Xuu @ uq
with eigenvalues A; in decreasing order and corresponding eigenfunctions u, then each sample from this GP can be obtained as
E Vawas ~ NO,
If, for example, \1 >> Eise A,. then a typical sample function is just very small perturbation of u1- We will see that for relu, this is indeed the case (Section 4), and this explains the "simplicity bias" in relu networks found by VVlle-Pérez et al. (2018).
Training the last layer of a randomly initialized network via full batch gradient descent for an infinite amount of time corresponds to Gaussian process inference with kernel K (Lee al., 2018 8 2019).
similar intuition holds for NTK: training all parameters of the network (Eg. (MLP) for an infinite amount of time yields the mean prediction of the GP (0 NTK) in expectation; see Lee al. (2019) and Appendix F.4 for more discussion.
Thus, the more the GP prior (governed by the CK or the NTK) is consistent with the ground truth function f", the more we expect the Gaussian process inference and GD training to generalize well. We can measure this consistency in the "alignment" between the eigenvalues A; and the squared coefficients a of f* expansion in the {ur}. J basis. The former can be interpreted as the expected magnitude (squared) of the u, u.-component of a sample f ~ >N(0, K). and the latter can be interpreted the actual magnitude squared of such component of f In this paper, will investigate an cleaner setting where f = ny is an eigenfunction. Thus we would hope to use a kernel whose ith eigenvalue X, is as large possible.
Neural Kernels From the forms of the equation Eqs. (CK) and [NTK) and the fact that Vo (x))) x only depends on K (xx, ) K (2r, x²), and K (x' x²), we see that CK or NTK of MI.s takes the form
K(I, y) = (z. v)
||||| 1
(2)
d d
for some function $ 3 R. We will refer to this kind of kernel Neural Kernel in this paper.
Kernels as Integral Operators We will consider input spaces of various forms C Rd equipped with some probability measure. Then a kernel function K acts as an integral operator on functions (2) by
Kf(x) = (K)())
E K(x, ()(y)) v~X
We will use the "juxtaposition syntax" KS to denote this application of the integral operator. Under certain assumptions, it then makes sense to speak of the eigenvalues and eigenfunctions of the integral operator K. While we will appeal and eigenfunctions in the main text below, we include a more formal discussion of Hilbert-Schmiae operators and their spectral theory in Appenddx for completeness. In the next section, investigate the cigendecompasition of neural kernels as integral operators over different distributions.
an intuitive understanding of eigenvalues
'In cases when X' is finite, K can be also thought of as a big matrix and f as vector but do not confuse f with their multiplication! If we use to denote matrix multiplication, then the operator application K is the same the matrix multiplication K D where D is the diagonal matrix encoding the probability values of each point in X.
4

---

Under review as a conference paper at ICLR 2020
3
THE SPECTRA OF NEURAL KERNELS
3.1 BOOLEAN CUBE
We first consider a neural kernel on the boolean cube A' = / = . equipped with the uniform measure. In this case, since each x A' has the same norm, ((x, y) +
/de
(r.av) |||]| I ||=|||||| d
effectively only depends on (zr, y), so will treat as a single variate function in this section, ((c)= = ( 1,
Brief review of basic Fourier analysis on the boolean cube O'Donnell 2014)). The space of real functions on T forms a 2 2'-dimensional space. Any such function has a unique expansion into multilinear polynomial (polynomials whose monomials do not contain 2i 2 2, of any variable x;). For example, the majority function over 3 bits has the following unique multilinear expansion
1 2 (21 22 23 2222))))
majg
maig( 03)
In the language of Fourier analysis, the 2d multilinear monomial functions
(s(x)
Ji iES
for each S S [d]
form Fourier basis of the function space ('( = (f 0 + R}, in the sense that their inner products satisfy
E xs(r)xr(z) = I(S T))
Thus, any function f: 1
can be always written as
f(z) Σ f(5)xx())
SCId
for unique set of coefficients (f(S)) sC14-
It turns out that K is always diagonalized by this Fourier basis {xs
Theorem 3.1. On the d-dimensional boolean cube Thd for every S C [d], xs is eigenfunction of K with eigenvalue
HIS
def
E ZETU
E DECT
S
Exs/d
(4)
where 1 (1. E T This definition of Pisd does not depend on the choice S, only on the cardinality of S. These are all of the eigenfunctions of K by dimensionality considerations
Define Ta to be the shift operator on functions over [-1, that sends o(-) to o(- - A). Then we can re-express the eigenvalue as follows.
Lemma 3.2. With μld as in Thm 3.1
#4 = 2- DI Ta) + Ta) (1)))
(5)
= 2 Σ Cdl k ((2 -r) -r)) A
(d
(6)
r=0
where
Cd. cd-k,k def
(-1jrts - k ( k
(
Eq. (5) will be important for computational purposes, and we will come back to discuss this more in Section 3.5 It also turns out μı affords pretty expression via the Fourier series coefficients of t.
As this is not essential to the main text, we relegate its exposition to Appendix H.]
"Readers familiar with boolean Fourier analysis may be reminded of the noise operator Tp < O D'onnell
2014 Defn 2.46). In the language of this work, T, a neural kernel with eigenvalues 14
5

---

Under review as a conference paper at ICLR 2020
3.2 SPHERE
Now let's consider the case when X' vddd-1 is the radius- V sphere in IR equipped with the uniform measure. Again, because x A' all have the same norm, we will treat as a univariate function with (x, y) 4 ( (a. y) /
o (z. v) /d). As is long known (Schoenberg. 1942] Gneiting 2013 Xu and Cheney 1992 Smola et al. 200T), K is diagonalized by spherical harmonics, and the eigenvalues are given by the coefficients of + against a system of orthogonal polynomials called Gegenbuaer polynomials. We relegate complete review of this topic to Appendixx H.2
3.3
ISOTROPIC GAUSSIAN
Now let's consider X' I& equipped with standard isotropic Gaussian Mo0, I), so that K behaves like
(x. y) ||
||:|| l1y12) f(v)
Kf(x)) = y-N110.1)
(( v)f(()
E
(o,))
d d
for any (O, I)). In contrast to the previous two sections, K will essentially depend on the effect of the norms ||-||| and ||y/| on +.
Nevertheless, because an isotropic Gaussian vector can be obtained by sampling its direction uni- formly from the sphere and its magnitude from a chi distribution, can still be partially diagonalized into a sum of products between spherical harmonics and kernels on E equipped with a chi distribution (Thm H.14). In certain cases, we can obtain complete cigendecompositioss for example when 4 is positive homogeneous. See (Appendixx H.3 for more details.
3.4 KERNEL IS SAME OVER BOOLEAN CUBE, SPHERE, OR GAUSSIAN WHEN >>>> 1
The reason we have curtailed detailed discussion of neural kernels on the sphere and on the standard Gaussian is because, in high dimension, the kernel behaves the same under these distributions as under uniform distribution over the boolean cube. Indeed, by intuition along the lines of the central limit theorem, we expect that uniform distribution over a high dimension boolean cube should approximate high dimensional standard Gaussian. Similarly, by concentration of measure, most of the mass of Gaussian is concentrated around thin shell of radius vd. Thus, morally, expect the same kernel function K induces approximately the same integral operator on these three distributions in high dimension, and as such, their cigenvalues should also approximately coincide. We verify empirically and thcoretically this is indeed the case in Appendix H.4
3.5 COMPUTING THE EIGENVALUES
As the eigenvalues of K over the different distributions are very close, will focus in the of this paper on eigenvalues over the boolean cube. This has the additional benefit of being much easier to compute.
Each eigenvalue over the sphere and the standard Gaussian requires an integration of + against a Gegenbauer polynomial. In high dimension d, these Gegenbauer polynomials varies wildly in sinusoidal fashion, and blows up toward the boundary (see Fig. 15 in the Appendix). As such, is difficult to obtain a numerically stable estimate of this integral in an efficient manner when d is large.
In contrast, have multiple ways of computing boolean eube eigenvalues, via via[Eqq. and (6) In
and
either case, we just take some linear combination of the values of at a grid of points on 11,
spaced apart by A = 2/d. While the coefficients C Cd-k,k (defined in Eq. (7) are relatively efficient compute, the change in the sign of Cdd makes this procedure numerically unstable for large d.
Instead, we use Eq. (5) isolate the alternating part to evaluate in a numerically stable way: Since
14k = [+TA -(LTT>)
Ta ((1,, we can evaluate $ def (-Ta) + via finite differences, and then
2
compute
d-k
1-k d
++ Ta
$(1)
Σ
$ (1-
(8)
2
k

---

Under review as a conference paper at ICLR 2020
pribiiility ork
(=1)
onfeweeee lese
1611
41
HBU 2112
oet 0
Lo11
20-1
26-1
110
eet 216
ur] 418
10-
(a)
(b)
Figure 1: The "simplicity bias" is not so simple. (a) Following Valle-Pérez et al. (2018), we sample 10a boolean functions {=137 [+1] as follows: for each combination of nonlinearity, weight variance T and bias variance og (as used in Eq. (MLP)). we randomly initialize network of 2 hidden layers, 40 neurons each. Then we threshold the function output to boolean output, and obtain a boolean function sample. We repeat this for 10a random seeds to obtain all samples. Then we sort the samples according to their empirical probability (this is the x-axis, rank), and plot their empirical probability (this is the y-axis, probability). The high values at the left of the relu curve indicates that a few functions get sampled repeatedly, while this is less true for erf. For erf b o %b and depth, we study the eigenvalues of the corresponding CK. Each CK has different
and = 4, no function got sampled more than once. (b) For different combination of nonlinearity,
eigenvalues Po..... f4 corresponding to homogeneous polynomials of degree O,..., 7. We plot them in log scale against the degree. Note that for erf and σi = O, the even degree μi vanish. See main text for explanations.
When & arises from the CK or the NTK of an MLP, all derivatives of & at 0 are nonnegative (Thm 1.3) Thus intuitively, the finite difference should be also all nonnegative, and this sum can be evaluated without worry about floating point errors from cancellation of large terms.
A slightly more clever way improve the numerical stability when 2k- S d is note that
(T + Ta)* - (T - TA)* (1) = (T + TA) d (T - (3) (1) = (T + Ta) Taadd d-22 (T T (11).
So an improved al algorithm is first compute the kth finite difference (I T2a)* )a with the larger step size 2A, then compute the sum (1 + TT) dd-2 as in
Eq. (8)
4 CLARIFYING THE "SIMPLICITY BIAS" OF RANDOM NEURAL NETWORKS
As mentioned in the introduction. Valle- Pérle-ééezzeeee et al. 2018) claims that neural networks are biased toward simple functions. We show that this phenomenon depends crucially on the nonlinearity, the sampling variances, and the depth of the network. In Fig. Tja), we have repeated their experiment for 10 random functions obtained by sampling relu neural networks with 2 hidden layers, 40 neurons cach, following Valle-Pérez et al. (2018)'s architectural choice: We also do the same for erf networks of the same depth and width, varying well the sampling variances of the weights and biases, as shown the legend. As discussed in Valle- et al. (2018). for relu, there indeed this bias, where single function gets sampled more than 10% of the time. However, for erf, as we increase oi we see this bias disappear, and every function in the sample gets sampled only once.
This phenomenon can be explained by looking at the eigendecomposstion of the CK, which is the Gaussian process kernel of the distribution of the random networks their hidden widths tend infinity. In Fig. 1(), plot the normalized eigenvalues (uu/ E (2) for the CKs corresponding to the networks sampled in Fig. aa). Immediately, we see that for relu and o2 of = 2, the degree 0 eigenspace, corresponding to constant functions, accounts for more than 80% of the variance. This means that a typical infinite-widnh relu network of 2 layers is expected to be almost constant, and this should be even more true after we threshold the network to be a boolean function. On the other hand, for erf and d = 0. the even degree f4, all vanish, and most of the variance comes from degree components (i.e. linear functions). This concentration in degree I also lessens as o² increases. But because this variance is spread across a dimension 7 eigenspace, we don't see duplicate function samples nearly as much as in the relu case. As a.,, increases, we also see the eigenvalues become more equally distributed, which corresponds to the flattening of
Valle-Pérez et al. (2018) actually performed their experiments over the (0, 1)" cube, not the (+1)² cube we are using here. This does not affect our conclusion. See AApendixx ]for more discussion
7

---

Under review as a conference paper at ICLR 2020
rell Icernel optimal depths
ert kernel opt mai deptits
1911 1K.
#11 18. 1. =
-0.07
-0.20
opemoll doath
15
0.00
180
-0175
50
-0122
M
20
-0.3
0.02
10
0075
0.00
0.01
0.00
0.002
(a)
(b)
(c)
(d)
The depth maximizing degree k fractional variance increases with &: for both relu and erf. For relu (a) and erf (b), we plot for each degree k the depth such that there exists some combination of other hyperparameters (such as oj or oi.)) that maximizes the degree k fractional variance. For both relu, of in the odd degrees (see Appendix D), fractional variance of various degrees versus depth for relu (c) and erf (d) NTK, with bright colors representing high variance. Clearly, we see the brightest region of each column, corresponding to fixed degree, moves up as we increase the degree, barring for the even/odd degree alternating pattern for erf NTK. The pattern for CKs are similar and their plots are omitted.
Figure 2:
maximizes fractional variance in general, and same holds for erf
take closer look at this slice by plotting heatmaps of
the probability -vr-rkkk curve in Fig. Ia). Finally, we observe that a 32-layer erf network with o has all its nonzero eigenvalues (associated to odd degrees) all equal (sce points marked by in Fig. I()).. This means that distribution is a "white noise" on the space of odd functions, and the distribution of boolean functions obtained by thresholding the Gaussian process samples is the uniform distribution on odd functions. This is the complete lack of simplicity bias modulo the oddness constraint.
However, from the spectral perspective, there is weak sense in which simplicity bias holds for all neural network-induced CKs and NTKs.
Theorem 4.1 (Weak Spectral Simplicity Bias). Let K be the CK or NTK of MLP on a boolean cube T Then the eigenvalues pa, k 0, ......,. , d, satisfy
No 2 112 N. ... 2 122 2 ... P1 P3 2... 122+1
Even though it's true that the fraction of variance contributed by the degree & eigenspace is decreasing with k, the eigenvalue themselves will be in a nonincreasing pattern across even and odd degrees. In fact, if fix l and let co, then can show that (Thm 1.6)
P Od
Of course, as we have seen, this is a very weak sense of simplicity bias, as doesn't 't prevent "white noise" behavior as in the case of erf CK with large of and large depth.
5 DEEPER NETWORKS LEARN MORE COMPLEX FEATURES
In the rest of this work, we compute the eigenvalues μ4 over the 28-dimensional boolean cube ( with d 128) for large number of different hyperparameters, and analyze how the latter affect the former. We vary the degree & E [0, 8). the nonlinearity between relu and erf, the depth (number of hidden layers) from to 128, and o E [0, 4]. We fix of.
for relu kernels, but additionally vary 03 [1,5] for erf kernels. Comprehensive contour plots of how these hyperparameters affect the kernels are included [Appendix D but in the main text we summarize several trends we see.
We will primarily measure the change in the spectrum by the degree k fractional variance, which is just
degree fractional variance def (9UR
Dg (9
This terminology comes from the fact that, if we were to sample function f from a Gaussian process with kernel K, then we expect that r% of the total variance of comes from degree k components of f. where r% is the degree fractional variance. If we were to try learn homogeneous degree-k:
8

---

Under review as a conference paper at ICLR 2020
Verttying best depths and NTK complestty biss, verying degree ground trath
deprh
enining bottlager mraiiin aaoee
1.8
2.8
(3
dep
P
66
(a)
(b)
(c)
Figure 3: (a) We train relu networks of different depths against a ground truth polynomial on @r:28 of different degrees k. We either train only the last layer (marked "ck") or all layers (marked "ntk"), and plot the degree fractional variance of the corresponding kernel against the best validation loss over the course of training. We see that the best validation loss is in general inversely correlated with fraction variance, expected. However, their precise relationship seems to change depending on the degree, or whether training all layers or just the last. See (Appendix E for experimental details. (b) Same experimental setting (a), with slightly different hyperparameters, and plotting depth against best validation loss (solid curves), as well as the corresponding kernel's (1 fractional variance) (dashed curves). We see that the loss-minmmzzing depth increases with the degree, as predicted by Fig. 2 Note that we do not expect the dashed and solid curves to match up, just that they are positively correlated as shown by (a). In higher degrees, the losses are high across all depths, and the variance is large, so we omit them. See Appenddx E for experimental details. (c) Similar experimental setting as (a), but with more hyperparameters, and now comparing training last layer vs training all layers. The color of each dot indicates the degree of the ground truth polynomial. Below the identity line, training all layers is better than training last layer. We see that the only nontrivial case where this not true is when learning degree 0 polynomials, i.e. constant functions. See See (ppenndxx E for experimental details. We also replicate (b) for MNIST and CIFAR1O, and moreover both (b) and (c) over the imput distributions of standard Gaussian and the uniform measure over the sphere. See Figs.
polynomial using a kernel K, intuitively we should try to choose K such that its μ4 is maximized, relative to other eigenvalues. Fig. 3)a) shows that this indeed the case even with neural networks: over a large number of different hyperparameter settings, degree k fractional variance is inversely related to the validation loss incurred when learning a degree k polynomial. However, this plot also shows that there does not seem like a precise, clean relationship between fractional variance and validation loss. Obtaining better measure for predicting generalization is left for future work.
Before we continue, we remark that the fractional variance of a fixed degree k converges to a fixed value as the input dimension d + oc:
Theorem 5.1 (Asymptotic Fractional Variance). Let K be the CK or NTK of an MLP on a boolean cube T. Then K can be expressed as K(x, y) = ((xx, () some analytic function Tb : .R- + R. If we fix k and let the input dimension d + co, then the fractional variance of degree k converges to
= (k1) 1 (k) (0)
-120 16)))
where (k)) denotes the kth derivative of db.
For the fractional variances we compute in this paper, their values at d = 128 are already very close to their d + oo limit, so we focus on the d = 128 case experimentally.
If K were to be the CK or NTK of a relu or erf MLP, then we find that for higher k. the depth of the network helps increase the degree k fractional variance. In Fig. 2/a) and (b), we plot, for each degree k; the depth that (with some combination of other hyperparameters like of) achieves this maximum, for respectively relu and erf kernels. Clearly, the maximizing depths are increasing with for relu, and also for erf when considering either odd A even & only. The slightly differing behavior between even and odd is expected, as seen in the form of Thm 4.1 Note the different seales of y-axes for relu and erf- the depth effect is much stronger for erf than relu.
For relu NTK and CK, of 0 maximizes fractional variance in general, and the same holds for erf NTK and CK in the odd degrees (see Appendix D). In Fig. 2)() and [ 2(d) we give a more fine-grained look at the of 0 slice, via heatmaps of fractional variance against degree and depth.
9

---

Under review as a conference paper at ICLR 2020
nik favors higher
IdL charpp CD
of champlis
Teccion "ppasatere saterro where
12"
42-
Mest-| of
10-1
0igch 1g.
md
10
112 03
11:03
62
10-a
(a)
(b)
(C)
degres
degres 50
degree
Figure 4: Across nonlinearities and hyperparameters, NTK tends to have higher fraction of variance attributed to higher degrees than CK. In (a), we give several examples of the fractional variance curves for relu CK and NTK across several representative hyperparameters. In (b), we do the same for erf CK and NTK. In both cases, clearly see that, while for degree 0 or 1, the fractional variance is typically higher for CK, the reverse is true for larger degrees. In (c), for each degree k. we plot the fraction of hyperparameters where the degree k fractional variance of NTK is greater than that of CK. Consistent with previous observations, this fraction increases with the degree.
Brighter color indicates higher variance, and we see the optimal depth for each degree i clearly increases with l for relu NTK, and likewise for odd degrees of erf NTK. However, note that as increases, the difference between the maximal fractional variance and those slightly suboptimal becomes smaller and smaller, reflected by suppressed range of color moving to the right. The heatmaps for relu and erf CKs look similar and are omitted.
We verify this increase of optimal depth with degree in Fig. 3jb. There we have trained relu networks of varying depth against a ground truth multilinear polynomial of varying degree. We clearly that the optimal depth is increasing with degree. We also verify this phenomenon when the input distribution changes to the standard Gaussian or the uniform distribution over the sphere vdsá-1; see Fig. 6
Note that implicit in our results here is a highly nontrivial observation: Past some point (the optimal depth), high depth can be detrimental to the performance of the network, beyond just the difficulty to train, and this detriment can already be seen in the corresponding NTK or CK. In particular, it's nor true that the optimal depth is infinite. We confirm the existence of such an optimal depth even in real distributions like MNIST and CIFARTO: see Fig. 7. This adds significant nuance the folk wisdom that "depth increases expressivity and allows neural networks to learn more complex features."
NTK FAVORS MORE COMPLEX FEATURES THAN CK
We generally find the degree k fractional variance of NTK to be higher than that of CK when l is large. and vice versa when & small, shown in Fig. 4 This means that, if we train only the last layer of a neural network (i.e. CK dynamics), we intuitively should expect to learn simpler features better, while, if train all parameters of the network (i.e. NTK dynamics), we should expect to learn more complex features better. Similarly, if we were to sample a function from a Gaussian process with the CK as kernel (recall this is just the distribution of randomly initialized infinite width MLPs (Lee et al., 2018), this function more likely to be accurately approximated by low degree polynomials than the same with the NTK.
We verify this intuition by training a large number of neural networks against ground truth functions of various homogeneous polynomials of different degrees, and show a scatterplot of how training the last layer only measures against training all layers (Fig. 3()). This phenomenon remains true over the standard Gaussian or the uniform distribution on the sphere (Fig. 8). Consistent with our theory, the only place training the last layer works meaningfully better than training all layers is when the ground truth is a constant function. However, we reiterate that fractional variance is an imperfect indicator of performance. Even though for erf neural networks and k 2 1, degree k fractional variance of NTK is not always greater than that of the CK. we do not see any instance where training the last layer of an erf network is better than training all layers. We leave an investigation of this discrepancy to future work.
10

---

Under review as a conference paper at ICLR 2020
7 PREDICTING THE MAXIMUM LEARNING RATE
In any setup that tries to push deep learning benchmarks, learning rate tuning is a painful but indispensable part. In this section, show that spectral theory can accurately predict the maximal nondiverging learning rate over real datasets as well as toy input distributions, which would help set the correct upper limit for a learning rate search.
By Jacot et al. 2018), in the limit of large width and infinite data, the function g : X I represented by our neural network evolves like
g++l = 2o
1 0,
(10)
when trained under full batch GD (with the entire population) with L.2 loss L(f.g)= -x-x g(z))², ground truth g" and learning rate a, starting from randomly initialization. If we train only the last layer, then K is the CK: if we train all layers, then K is the NTK. Given an eigendecomposition >; agu; is the decomposition of go in the eigenbasis {u, his then one
of K as in Eq. (1) if g
can easily deduce that
g' 9'-9"
g"
Σ
a, 2..
Consequently, we must have a < (max; Aa) Aa1 in order for Eq. (10) to converge
When the input distribution is the uniform distribution over X the maximum learning rate is max(μo, f1) by Thm 4.1 By Thm 5.1 long the & function corresonding to K has ( * 0. when d is large, we expect (40 R ((0) but μl ~ d=1 (0) & Hoo. Therefore, we should predict 400 for the maximal learning rate when training the boolean cube. However, as FFgg. shows, this prediction is accurate not only for the boolean cube, but also over the sphere, the standard Gaussian, and even MNIST and CIFARIO!
8 CONCLUSION
In this work, we have taken a first step at studying how hyperparameters change the initial distribution and the generalization properties of neural networks through the lens of neural kernels and their spectra. We obtained interesting insights by computing kernel eigenvalues over the boolean cube and relating them to generalization through the fractional variance heuristic. While it inspired valid predictions that are backed up by experiments, fractional variance clearly just rough indicator. We hope future work can refine on this idea to produce a much more precise prediction of test loss. Nevertheless, helieve the spectral perspective is the right line of research that will not only shed light on mysteries deep learning but also inform design choices in practice.
REFERENCES
Joshua Achiam, Ethan Knight, and Pieter Abbeel. Towards Characterizing Divergence in Deep Q-Learning, arXiv: 08899 [cs], March 2019.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers. arXiv:181 1.04918 [cs, math, star], November 2018a.
Zeyuan Allen-Zhu Yuanzhi Li, and Zhao Song. On the Convergence Rate of Training Recurrent Neural Networks. arXiv:1810. 120. [cs, math, stat], October 2018b.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A Convergence Theory for Deep Learning via Over-Parameterizatton. we..iv/8111.00 0.3962 [cs, math, stat), November 2018c.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On Exact Computation with an Infinitely Wide Neural Net. a9Xiv: 1955 [cs, stat], April 2019a.
Sanjeev Arora, Simon S. Du. Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks. January 2019b.
'Note that this is the max learning rate the infinite-width neural network evolving in NTK regime, but not necessarily the max learning rate of the finite-wdith neural network, as a larger learning rate just means that the network no longer evolves in the NTK regime.
11

---

Under review as a conference paper at ICLR 2020
Beolean cube theory predicts max learning rate for real datasets
max Ir: training the last layer (CK)
max training all yors (MTO)
max tritraining all layers (NTK)
16a
10t
101
dist
dist
tcpith
Mhiit
MNNI
CBFA8110
CIFAKLO
theoredicl max
Coursdan
thaoredical max
Gaunsiin
theoredeal
10-3
10-2
10-1
(a)
10-2
10-1
(b)
(c)
10-
30-1
101
101
empirical max
empirical maxir
emortiaal max
Figure 5: Spectral theory of CK and NTK over boolean cube predicts max learning rate for SGD over real datasets MNIST and CIFAR10 as well as over boolean cube cg the sphere V1285128-1 and the standard Gaussian (0, 112)). In all three plots, for different depth, nonlin- earity, o of of the MLP, we obtain its maximal nondiverging learning rate ("max learning rate") via binary search. We center and normalize each image of MNIST and CIFARIO to the dds sphere, where 28 784 for MNIST and
x 32" = 3072 for CIFARIO. See E.2 for more details. (a) We empirically find max learning rate for training only the last layer of MLP. Theoretically, we predict 1 (0) where & corresponds the CK of the MLP. We see that our theoretical prediction is highly accurate. Note that the Gaussian and Sphere points in the scatter plot coincide with and hide behind the BoolCube points. (b) and (c) We empirically find max learning rate for training all layers. Theoretically, we predict (0) where & corresponds to the NTK of the MLP. The points
identical between (b) and (c), but the color coding is different. Note that the Gaussian points in the scatter plots coincide with and hide behind the Sphere points. In (b) we see that our theoretical prediction when training all layers is not accurate when we train only the last layer, but it still highly correlated with the empirical max learning rate. general underpredicts, so that half of the theoretical learning rate should always have SGD converge. This is expected, since the NTK limit of training dynamics is only exact the large width limit, and larger learning rate just means the training dynamics diverges from the NTK regime, but not necessarily that the training diverges. In (c), theoretical prediction. If we were to preprocess MNIST and CIFAR 10 differently, then our theory is less accurate at predicting the max learning rate; see Fig. 9 for more details.
that deeper networks tend accept higher learning rate than
12

---

Under review as a conference paper at ICLR 2020
A. R. Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Trunsactions on Information Theory, 39(3)930-945, May 1993. ISSN 0018-9448. doi: 10. 10.1 18,256500.
Ronen Basri, David Jacobs, Yoni Kasten, and Shira Kritchman. The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies. 1xXiv:1906.00425 [cs, eess, stat], June 2019.
Agata Bezubik, Agata Dabrowska, and Aleksander Strasburger. On spherical expansions of zonal functions on Euclidean spheres. Archiv der Mathematik, 90(1):70-81, January 2008. ISSN 0003-889X, 1420-8938. doi: 10.1007/500013-007-23000
Alberto Bietti and Julien Mairal. On the Inductive Bias of Neural Tangent Kernels. arXiv:1905.1211 [cs, stat), May 2019.
Kenneth Blomqvist, Samuel Kaski, and Markus Heinonen. Deep convolutional Gaussian processes. arXiv preprint arXiv:1810.03000 2018.
Anastasia Borovykh. A gaussian process perspective on convolutional neural networks. arXiv preprint arXiv: 2018
John Bradshaw, Alexander G de G Matthews, and Zoubin Ghahramani. Adversarial examples, uncertainty, and transfer testing robustness in gaussian process hybrid deep networks. arXiv preprint 10X.ii::007.0222 2017.
Emmanuel J. Candès. Harmonic Analysis of Neural Networks. Applied and Computational Harmonic Analysis, 6(2):197-218) March 1999. ISSN 1063-5203. doi: 10.1006/acha.19900
Minmin Chen, Jeffrey Pennington, and Samuel Schoenholz. Dynamical Isometry and a Mean Field Theory of RNNs: Gating Enables Signal Propagation in Recurrent Neural Networks. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 873-882, Stockholmsmässan, Stockholm Sweden, July 2018. PMLR.
Youngmin Cho and Lawrence K. Saul. Kernel methods for deep learning. In Advances in Neural Information Processing Systems, pages 342-350, 2009.
Andreas Damianou and Neil Lawrence. Deep gaussian processes. In Artificial Intelligence and Statistics, pages 207-215, 2013.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward Deeper Understanding of Neural Networks: The Power of Initialization and Dual View on Expressivity. arXiv: 1602,05997 [es, stat), February 2016.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient Descent Provably Optimizes Over-parameterized Neural Networks. arXiv:1810.0206 [cs, math, stat], October 2018.
Ronen Eldan and Ohad Shamir. The Power of Depth for Feedforward Neural Networks. In Conference Learning Theory, pages 907-940, June 2016.
Adrià Garriga-Alonso, Laurence Aitchison, and Carl Edward Rasmussen. Deep Convolutional Networks as shallow Gaussian Processes. arXiv: 180.00588 [cs, stat], August 2018.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. arXiv: /2 [cs, math, stat), April 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Yee Whye Teh and Mike Titterington, editors, Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pages 249-256 Chia Laguna Resort, Sardinia, Italy, May 2010. PMLR. 02661..
Tilmann Gneiting. Strictly and non-strictly positive definite functions on spheres. Bernoulli, 19(4): 1327-1349, September 2013. ISSN 1350-7265. doi: 1
13

---

Under review as a conference paper at ICLR 2020
Boris Hanin. Which Neural Net Architectures Give Rise To Exploding and Vanishing Gradients? January 2018.
Boris Hanin and David Rolnick. How to Start Training: The Effect of Initialization and Architecture. arXiv:1803.01719 [cs, stat], March 2018.
Soufiane Hayou, Amaud Doucet, and Judith Rousseau. On the Selection of Initialization and Activation Function for Deep Neural Networks. arXiv: [cs, stat], May 2018.
Tamir Hazan and Tommi Jaakkola. Steps Toward Deep Kernel Methods from Infinite Neural Networks. arXiv:1508.00 050333333 [cs), August 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE International Conference Computer Vision, pages 1026-1034, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. arXiv: [cs, math, stat], June 2018. 00000.
Ryo Karakida, Shotaro Akaho, and Shun-ichi Amari. Universal Statistics of Fisher Information in Deep Neural Networks: Mean Field Approach. arXiv:/806.013 16 [cond-mat, stat), June 2018.
Yitzhak Katznelson. An Introduction to Harmonic Analysis. Cambridge Mathematical Library. Cambridge University Press, Cambridge, UK ; New York, 3rd ed edition, 2004. ISBN 978-0-521- 83829-0 978-0-521-54459-0
Vinayak Kumar, Vaibhav Singh, PK Srijith, and Andreas Damianou. Deep Gaussian Processes with Convolutional Kernels. arXiv preprint arXiv: 01655, 2018.
Neil D Lawrence and Andrew Moore. Hicrarchical Gaussian process latent variable models. In Proceedings of the 24th International Conference on Machine Learning, pages 481-488. ACM, 2007.
Nicolas Le Roux and Yoshua Bengio. Continuous neural networks. In Artificial Intelligence and Statistics, pages 404-411, 2007.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Sam Schoenholz, Jeffrey Pennington, and Jascha Sohl-dickstein. Deep Neural Networks as Gaussian Processes. In International Conference on Learning Representations, 2018
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent. arXiv: 1902/0022000000 [cs, stat], February 2019.
Junhong Lin and Lorenzo Rosasco. Optimal Rates for Multi-pass Stochastic Gradient Methods. page 47.
Alexanderi G. \ del G. Matthews. Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahra- mani. Gaussian Process Behaviour in Wide Deep Neural Networks. In International Conference on Learning Representations, April 2018.
Radford M Neal. BAYESIAN LEARNING FOR NEURAL NETWORKS. PhD Thesis, University of Toronto, 1995.
Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes. arXiv preprint arXiv:1810.05148, 2018
Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, New York, NY, 2014. ISBN 978-1-107-03832-55
Jeffrey Pennington and Yasaman Bahri, Geometry of Neural Network Loss Surfaces via Random Matrix Theory. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2798-2806. International Convention Centre, Sydney, Australia, August 2017. PMLR. 00006.
14

---

Under review as a conference paper at ICLR 2020
Jeffrey Pennington and Pratik Worah. Nonlinear random matrix theory for deep learning. In Advances in Neural Information Processing Systems, pages 2634-2643, 2017. 00000.
Jeffrey Pennington and Pratik Worah. The Spectrum of the Fisher Information Matrix of a Single- Hidden-Layer Neural Network. In Advances in Neural Information Processing Systems 31, page 10, 2018.
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: Theory and practice. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garettt, editors, Advances in Neural Information Processing Systems 30, pages 4788 4798.
Curran Associates, Inc., 2017a. 00004.
Jeffrey Pennington, Samuel S. Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: Theory and practice. 1rXiv:1711.0473: [cs, stat], November 2017b. 00005.
Jeffrey Pennington, Samuel S. Schoenholz, and Surya Ganguli. The Emergence of Spectral Univer- sality in Deep Networks. 9XXv:18802.0999 [cs, stat], February 2018.
George Philipp and Jaime G. Carbonell. The Nonlinearity Coefficient Predicting Overfitting in Deep Neural Networks. arXiv:1806.00177 001799 [cs, stat]. May 2018. 00000.
Ben Poole, Subhaneil Lahiri, Maithreyi Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Ex- ponential expressivity in deep neural networks through transient chaos. In Advances In Neural Information Processing Systems, pages 3360-3368, 2016. 00047.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred A. Hamprecht, Yoshua Bengio, and Aaron Courville. On the Spectral Bias of Neural Networks. arXiv: 08734 [cs, stat), June 2018
Garvesh Raskutti, Martin J. Wainwright, and Bin Yu. Early stopping and non-parametric regression: An optimal data-dependent stopping rule. arXiv:/306.33 [stat], June 2013.
I. J. Schoenberg. Positive definite functions on spheres. Duke Mathematical Journal, 9(1:96-108, March 1942. ISSN 0012-7094, 1547-7398. doi:
Samuel S. Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein. Deep Information Propagation. 2017.
Bernhard Schölkopf and Alexander Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. Adaptive Computation and Machine Learning. MIT Press, Cambridge, Mass, 2002. ISBN 978-0-262- 19475-44
Alex J. Smola, Zoltán L. Óvári, and Robert Williamson. Regularization with Dot-Product Kernels. In T. K. Leen, T. G. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems 13, pages 308-314 MIT Press, 2001.
Sho Sonoda and Noboru Murata. Neural Network with Unbounded Activation Functions is Universal Approximator. Applied and Computational Harmonic Analysis, 43(2):233-268, September 2017. ISSN 10635203. doi: a...066...cha.005..1.
P.K.
Suetin.
Ultraspherical polynomials Encyclopedia of Mathematics.
Joel A. Tropp. An Introduction to Matrix Concentration Inequalities. arXiv:1501.0157 [cs, math, stat], January 2015.
Guillermo Valle-Pérez, Chico Q. Camargo, and Ard A. Louis. Deep learning generalizes because the cerrmmter-function map is biased towards simple functions. arXhv:1805.08522 [cs, stat], May 2018
Mark van der Wilk, Carl Edward Rasmussen, and James Hensman. Convolutional Gaussian Processes. In Advances in Neural Information Processing Systems 30, pages
2017.
Yuting Wei, Fanny Yang, and Martin J Wainwright. Early stopping for kernel boosting algorithms: A general analysis with localized complexities. page 11.
15

---

Under review as a conference paper at ICLR 2020
Christopher K Williams. Computing with Infinite Networks, In Advances in Neural Information Processing Systems, page 7, 1997.
Andrew G Wilson, Zhiting Hu, Ruslan R Salakhutdinov, and Eric P Xing. Stochastic Variational Deep Kernel Learning. In Advances in Neural Information Processing Systems, pages 2586-2594 2016a.
Andrew Gordon Wilson, Zhiting Hu, Ruslan Salakhutdinov, and Eric P Xing. Deep kernel learning. In Artificial Intelligence and Statistics, pages 370-378, 2016b.
Lechao Xiao, Yasaman Bahri, Sam Schoenholz, and Jeffrey Pennington. Training ultra-deep CNNs with critical initialization. In NIPS Workshop, 2017.
Bo Xie, Yingyu Liang, and Le Song. Diverse Neural Network Learns True Target Functions. arXiv: 1.03131 [cs, stat), November 2016.
Yuan Xu and E. W. Cheney. Strictly Positive Definite Functions on Spheres. Proceedings of the American Mathematical Society, 116(4):777-911, 1992. ISSN 0002-9939. doi: 10.2307/2159477.
Zhi-Qin John Xu, Yaoyu Zhang. and Yanyang Xiao. Training behavior of deep neural network in frequency domain. arXiv:1807.0125/ [cs, math, stat], July 2018.
Zhi-Qin John Xu, Yaoyu Zhang, Tao Luo, Yanyang Xiao, and Zheng Ma. Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks. arXiv:1901.0652. [cs, stat], January 2019.
Zhiqin John Xu. Understanding training and generalization in deep learning by Fourier analysis. (00::/888.4220 [cs, math, stat], August 2018.
Greg Yang. Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process
Behavior, Gradient Independence, and Neural Tangent Kernel Derivation. 0rX74.1902.04760 /cond-maat physics:math-ph, stat], February 2019.
Greg Yang and Sam S. Schoenholz. Deep Mean Field Theory: Layerwise Variance and Width Variation Methods to Control Gradient Explosion. February 2018.
Greg Yang and Samuel S. Schoenholz. Mean Field Residual Network: On the Edge of Chaos. In Advances in Neural Information Processing Systems, 2017.
Greg Yang, Jeffrey Pennington, Vinay Rao, Jascha Sohl-Dickstein, and Samuel S. Schoenholz. A Mean Field Theory of Batch Normalization. 1902.089922 [cond-mat], February 2019.
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On Early Stopping in Gradient Descent Learning. Constructive Approximation, 26(2):289-315, August 2007. ISSN 0176-4276, 1432- 0940. doi: 10.1007/500066-0000006----
Yaoyu Zhang. Zhi-Qin John Xu, Tao Luo, and Zheng Ma. Explicitizing an Implicit Bias of the Frequency Principle in Two-layer Neural Networks. arXiv:1905, 10264 [es, stat], May 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks. arXiv:1811.08888 [cs, math, stat], November 2018.
16

---

Under review as a conference paper at ICLR 2020
A RELATED WORKS
The Gaussian process behavior of neural networks was found by Neal
(995) for shallow networks
and then extended over the years to different settings and architectures (Williams 1997, Le Roux
and Bengio, 2007; Hazan and Jaakkola, 2015] Daniely et al. 2016
|
Lee Lee et al. 2018 Matthews et al.
Nova et al. 2018). This connection was exploited implicitly or explicitly to build new models (Cho and Saul [ Lawrence and Moore, 2007: Damianou and Lawrence] 2013 Wilson al. 2016a bl Bradshaw et al. [201]]] van der Wilk et al. [017]] Kumar et 20118 Blomqvist et al. 2018 et al., 2018 Novak et al.] 2018 Lee et al. (018). The Neural Tangent Kernel is a much more recent discovery by Jacot et al. (2018) and later AAllen Zhu et al.
Borovykh 2018 Garrgaa-Aoom
20 c b): Du et al. (2018); Arora et al. (2019b); Zou et al. (2018) 8) came upon the same reasoning independently. y. Like CK, NTK has also been applied toward building new models or algorithms
Arora et al. 2019a |Achiam et al. 2019).
Closely related to the discussion of CK and NTK is the signal propagation literature, which tries to understand how to prevent pathological behaviors in randomly initialized neural networks when they
2018 Hanin 2018 deep (Poole et al., 20166 Schoenholz et al. 2017: Yang and Schoenholz 2017
Hanin and Rolnick| [2088] Chen et al.) 2018)) Yang et al. 2019; Pennington et al. 2017a Hayou et al, 2018, Philipp and Carbonell| 2018). This line of work can trace its original at least to the advent of the Glorot and He initialization schemes for deep networks (Glorot and Bengio 2010 He et al. 2015). The investigation of forward signal propagation, or how random neural networks change with depth, corresponds to studying the infinite-depth limit of CK, and the investigation of backward signal propagation, or how gradients of random networks change with depth, corresponds to studying the infinite-depth detth limit of NTK. Some of the guite remarkable results from this literature includes how to train a 10,000 layer CNN (Xiao et al. 2017) and that, counterintuitively, batch normalization causes gradient explosion Yang et al. 2019).
This signal propagation perspective can be refined via random matrix theory (Pennington et al. 2017: 7 2018). In these works, free probability is leveraged to compute the singular value distribution of the imput-output map given by the random neural network, the input dimension and width tend to infinity together. Other works also investigate various questions of neural network training and generalization from the random matrix perspective (Pennington and Worah 2017 Pennington and Pennington and Worah 2018).
Bahri 2017
Yang
2019) presents a common framework, known as Tensor Programs, unifying the GP, NTK, signal propagation, and random matrix perspectives, as well as extending them to new scenarios, like recurrent neural networks. It proves the existence of and allows the computation of a large number of infinite-width limits (including ones relevant to the above perspectives) by expressing the quantity of interest as the output of a computation graph and then manipulating the graph mechanically.
Several other works also adopt a spectral perspective on neural networks (Candès) 1999| Sonoda
and Murata 2017 Eldan and Shamir 2016; Barron 1993 Xu et al. 2018 Zhang et al., 2019 Xu et al. 2019 Xu 20188; here we highlight a few most relevant to us. Rahaman et al. (2018) studies the real Fourier frequencies of relu networks and perform experiments on real data as well synthetic ones. They convincingly show that relu networks learn low frequencies components first. They also investigate the subtleties when the data manifold is low dimensional and embedded in various ways in the input space. In contrast, our work focuses on the spectra of the CK and NTK (which indirectly informs the Fourier frequencies of a typical network). Nevertheless, our results are complementary to theirs, as they readily explain the low frequency bias in relu that they found. Karakida et al.) (2018) studies the spectrum of the Fisher information matrix, which share the nonzero eigenvalues with the NTK. They compute the mean, variance, and maximum of the eigenvalues Fisher eigenvalues (taking the width to infinity first, and then considering finite amount of data sampled iid from a Gaussian). In comparison, our spectral results yield all eigenvalues of the NTK (and thus also all nonzero eigenvalues of the Fisher) as well as eigenfunctions.
Finally, we note that several recent works (Xie et al. 2016 Bietti and Mairal 2019 Basri et al. 2019 Ghorbani et al., 2019) studied one-hidden layer neural networks over the sphere, building on Smola et al. (2001)'s 's observation that spherical harmonics diagonalize dot product kernels, with the latter two concurrent to us. This is in contrast the focus on boolean cube here, which allows us study the fine-grained effect of hyperparameters on the spectra, leading to a variety of insights into neural networks' generalization properties.
17

---

Under review as a conference paper at ICLR 2020
B UNIVERSALITY OF OUR BOOLEAN CUBE OBSERVATIONS IN OTHER INPUT DISTRIBUTIONS
Using the spectral theory we developed in this paper, we made three observations, that can be roughly summarized as follows: the simplicity bias noted by Valle-Pérez et al. (2018) not universal; 2) for each function of fixed "complexity" there is an opumal depth such that networks shallower deeper will not learn it as well; 3) training last layer only is better than training all layers when learning "simpler" features, and the opposite is true for learning "complex" features.
In this section, discuss the applicability of these observations to distributions that are not uniform over the boolean cube: in particular, the uniform distribution over the sphere vdg the standard Gaussian (0, Ta), as well as realistic data distributions such as MNIST and CIFAR10.
Simplicity bias on the finiteness of the boolean cube as a domain, so we cannot effectively test this on the distributions above, which all have uncountable support.
The simplicity bias noted by Valle-Pérez et al. (018), in particular Fig. depends
Optimal depth With regard to the second observation, we can test whether an optimal depth exists for learning functions over the distributions above. Since polynomial degrees remain the natural indicator of complexity for the sphere and the Gaussian (see Appendices H.2 and H.3 for the relevant spectral theory), replicated the experiment in Fig. 3[b) for these distributions, using the same ground truth functions polynomials of different degrecs. The results are shown in Fig. 6 We see the same phenomenon in the boolean cube case, with an optimal depth for each degree, and with the optimal depth increasing with degree.
For MNIST and CIFARIO, the notion of "feature complexity" is less clear, so we will not test the hypothesis that "optimal depth increases with degree" for these distributions but only test for the existence of the optimal depth for the ground truth marked by the labels of the datasets. We do so by training a large number of MLPs of varying depth these datasets until convergence, and plot the results in Fig. 7 This figure clearly shows that such an optimal depth exists, such that shallower or deeper networks do monotonically worse as the depth diverge away from this optimal depth.
Again, the existence of the optimal depth not obvious at all, as conventional deep learning wisdom would have one believe that adding depth should always help.
Training last layer only vs training all layers Finally, we repeat the experiment in Fig. 3(c) for the sphere and the standard Gaussian, with polynomials of different degrees as ground truth functions. The results are shown in Fig. We see the same phenomenon as in the boolean cube case: for degree 0 polynomials, training last layer works better in general, but for higher degree polynomials, training all layers fares better.
Note that, unlike the sphere and the Gaussian, whose spectral theory tells us that (harmonic) polyno- mial degree is natural notion of complexity, for MNIST and CIFAR10 we have much less clear idea of what "complex" or a "simple" feature is. Therefore, we did not attempt a similar experiment on these datasets.
C THEORETICAL VS EMPIRICAL MAX LEARNING RATES UNDER DIFFERENT PREPROCESSING FOR MNIST AND CIFAR10
In the main text Fig. 5
the MNIST and CIFAR10 datasets, we preprocessed the data by centering and normalizing to the sphere (see Appendix E.2 for a precise description). With this preprocessing, our theory accurately predicts the max learning rate in practice.
In general, if we go by another preprocessing, such as PCA or ZCA, or no preprocessing. our theoretical max learning rate (0) is less accurate but still correlated in general. The only exception seems be relu networks PCA- 7CA- preprocessed CIFAR10 10. See Fig.
18

---

Under review as a conference paper at ICLR 2020
optimal opthts cxist over standard Gaussian and sphare too
dit
Gaustan
Sphere
0.6
BociCube
0.4
0.2
0.0
depth
Figure 6: Optimal depths exist over the standard Gaussian (O, Ta) and the uniform distribu- tion over the sphere Vdsá-1 as well. Here we use the exact same experimental setup as Fig. 3(b) (see Appendix B for details) except that the input distribution is changed from uniform over the boolean cube CTC to standard Gaussian No0, Ia) (solid lines) and uniform over the sphere vdgd-1 (dashed lines), where
128. We also compare against the results over the boolean cube from Fig.3(b) which are drawn with dotted lines. Colors indicate the degrees of the ground truth poly- nomial functions. The best validation loss for degree 0 to 2 are all very close matter which distribution the input is sampled from, such that the curves all sit on top of each other. For degree 3, there is less precise agreement between the validation loss over the different distributions, but the overall trend is unmistakably the same. We see that for networks deeper or shallower than the optimal depth, the loss monotonically increases as the depth moves away from the optimum.
optimal depths exist MNIST
training last
all
bast 6657 arT
CFÁR1o
WhIST bust ai 417
layer
al syen
3
2
10
depth
Septh
Figure 7: Optimal depths exist over realistic distributions of MNIST and CIFAR10. Here, trained relu networks with o² = 2, of = 0 for all depths from to 10. We used SGD with learning rate 10 and batch size 256, and trained until convergence. We record the best test emror throughout the training procedure for each depth. For each configuration, we repeat the randomly initialization and training for 10 random seeds to estimate the variance of the best test error. The rows demonstrate the best test error over the course training on CIFAR10 and MNIST, and the columms demonstrate the same for training only the last layer or training all layers. As one can see, the best depth when training only the last layer is 1, for both CIFAR 10 and MNIST. The best depth when training all layers is around for both CIFAR 10 and MNIST. Performance monotically decreases for networks shallower or deeper than the optimal depth. Note that we have reached the SOTA accuracy for MLPs reported in Lee et al. (2018) on CIFARIO, and within point of their accuracy on MNIST.
19

---

Under review as a conference paper at ICLR 2020
training last loyer vs training all layers
gausssin
sphere
1.0
deg
deg
bast vastvall lock (all layens)
0.8
0.8
0.6
0.6
0.4
0.2
0.0
0.0
(last layer)
best loss (last layer)
Figure 8: Just like over the boolean cube: Over the sphere Vds and the standard Gaussian (0, Ia), training only the last layer is better for learning low degree polynomials, but training all layers is better for learning high degree polynomials. Here use the exact same experimental setup as Fig. 3/c) (see Appendix E for details) except that the input distribution is changed from uniform over the boolean cube op standard Gaussian NO, La) (left) and uniform over the sphere v Vdgd-1 (right), where 128.
Theorotical empirical max learning rate under different preprocessing
No Pneproccasing
PCA128
ZCA128
103
10
10
detasel HMST CIFAR10 nonin eff
delaset
MNSS
TRARING LAST LAYER ONLY
CIFAR10
bisiresicl IT
10
20R
dilanee
10:1
NNST
CIFAR1
10-7
101
10-4
10-1
10-4
10
10
363
101
101
dataset HNIT
dataset
NHIST
CEPARIC
CITAR10
THANING ALL LAYSSS
noninn
nonil
erf
12P
thionetical
20
15:1
delase:
NIEST
10-1
10-2
CIFAR1O
nonin
10
10th
10:1
10? empirical
10t
10-9
10:2
10:t
10a
107
10:2
10t1
107
1nt
emprical
empirical max Ir
Figure 9: We perform binary search for the empirical max learning rate of MLPS of different depth, activations, o and of on MNIST and CIFAR 10 preprocessed in different ways. See Appendix F.2 for experimental details. The first row compares the theoretical and empirical max learning rates when training only the last layer. The second row compares the same when training all layers (under NTK parametrization (Eq. (MLP)) ). The three columns correspond to the different preprocessing procedures: no preprocessing. PCA projection
the first 128 components (PCA128), and ZCA projection to the first 128 components (ZCA128). In general, the theoretical prediction is less accurate (compared to preprocessing by centering and projecting to the sphere, as in Fig. 5), though still well correlated with the empirical max learning rate. The most blatant caveat the relu networks trained on PCA1 128- and ZCA128 1011128-pocee 128-proceseed CIFAR10.
20

---

Under review as a conference paper at ICLR 2020
relu ci: fractional varfance
10
degree
1.
Segmee2
-036
2.0
degree
8,2200
1.0
Oegree
0.000
2.5
degree
6.240
6.2
6.275
00007
6.225
10
0.7
0.
1030
--316
002225
-3.00
0001
5.4
6.223
6.2220
5.2
-05
-0.00
2.2
-8:0225
-.3050
02
-0:0
-0.00
0.3
6.3005
6.3810
death
dupth
degth
depth
-0.30
16
24
-1015
2/
0.4
-0000
10
101
161
10
327
307
101
10r
10:
16'
depits
depth
depmh
depth
rolu ntk: fracctional varlance
degg me
degree
24
degree
0:354
deggee
6.332
degree
6.3200
72
21
6:200
62175
0.324
8:355
-0 60
-0
-0 00
8:224
6.226
6:12
6.2300
62875
32
6-032
0.200
40.36 16
.0.00
0.003
6,000
6,3000
deg
-055
degiee
-0 00
degree
6:443
degine
6:24
40
0:335
0.221
40
60325
6.25
8
1024
8:223
0.12
-039
-000
-0m1
-6:055
-6053
0.003
6,000
9e2th
death
de2th
Figure 10:
2D contour plots of how fractional variance of each degree varies with of and depth, fixing o 2, for relu CK and NTK. For each degree k. and for each selected fractional variance value, we plot the level curve (depth, of)) achieving this value. The color indicates the fractional variance, given in the color bars.
21

---

Under review as a conference paper at ICLR 2020
D VISUALIZING THE SPECTRAL EFFECTS OF o o. AND DEPTH
While in the main text, we summarized several trends of interest kn several plots, they do not give the entire picture of how cigenvalues and fractional variances vary with o oh and depth. Here we try to present this relationship more completely in series of contour plots. Fig. shsswwss how varying depth and of changes the fractional variances of each degree, for relu CK and NTK. We are fixing -² = 2 in the CK plots, as the fractional variances only depend on the ratio / even though this is not true for relu NTK, we fix d = 2 as well for consistency. For erf, however, the fractional 2 variance will crucially depend both dh and oi so present 3D contour plots of how o 0 and depth changes fractional variance Fig.. 13] Complementarily, we also show Figs. [7 T2
a few slices of these 3D contour plots for different fixed values of of for erf CK and NTK.
22

---

Under review as a conference paper at ICLR 2020
erf fractional variance. fixing of
-0.25
0.5
6.35
0.000
0.00
19
-000
0.45
0.30
0.323
0.100
0.072
00.75
0.000
0.045
-004
0.03
0.05
-035
0.025
-0015
0000
0.00
0.033
0,000
0.00
155
10P
13t
10P
dopth
Sopth
depth
fractional variance,
de-gree 0
degree 2
de-reee 4
dh-gree 6
Sh-gree 8
2,050
2,032
2.04
LA300
-2.00
2.44
-2,20
-2033
12.73
2,40
+2024
-2015
-60225
-2.3
-280
-3024
22052
-2012
-5.16
0.013
50215
-5.15
-1.3
-2015
-5.088
-0.13
-60325
+3.00
-5.000
-5.00
---0023
-6-0425
degrio
degres
-5.14
degres
degres
52042
-0.12
-0.13
-2.1
-2.0
-5.00
-2032
-2018
-5024
-2016
2.02
-5.08
-5,00
-0:306
1:t.
1st.
1sc
lel
deeth
death
death
depth
fractional variance, fixing oj
-2,38
-2033
-20175
-2.044
-2.20
-8023
2002
-2013
-2078
2026
22030
5.000
-50200
10*
12P
10*
:40
10*
:6:
10*
16
2PP
desth
desth
depth
depth
depth
deggee
2.88
degree
2,120
degree 5
2,035
Segroe
2.055
-227
2,105
-2.45
-2000
2000
-2.40
-23
22033
2005
-2032
11024
-2010
-5015
12025
1002
5.000
1.000
erf ckc fractional variance, fixing of
degroe
degres
deproe
6002
degree
-50120
Segres
-6.06
-E,240
-8.000
-0 01235
-20035
-0.00
35
-8104
013s
-50200
-0002
0852
-E0230
-0.000
-0000G
-o 6015
-20335
-..00
0002
1.0000
1.1
1.7
12
121
107
10t
10
100
death
dept
depis
depth
depth
-0,05
8.000
-0 013
-6.05
0.00
0,000
-0 004
2
12f
137
30r
100
207
12
131
107
10F
10
16
Se5th
depts
depts
depth
Figure 11: 2D contour plots of how fractional variance of each degree varies with af and depth, for different slices of of, for erf NTK. These plots essentially show slices of the NTK 3D contour plots in Fig. 13 For σ 0. 14, for all even degrees i are O, so we omit the plots. Note the rapid change in the shape of the contours for odd degrees, going from of = to of 0.1. This is reflected in Fig. 13 as well.
23

---

Under review as a conference paper at ICLR 2020
erf ntt:: tractiaanoonoo nal variance, fixiing - degree
0.75
0,073
15%
-045
0.00
0.06
0.00
0.045
3.060
0.00
1004
2.000
0.03
0.02
2.015
0.30
0.00
0.00
3,000
10P
10
13R
10!
Sopth
depth
depth
ntk: fractional variance, fixing
deggree 0
-1.05
drggew
00000
deggree
degree
degree
0,240
00.00
- 2305
-3
3.096
0.300
-0.5
00:0
0.000
-0:45
-3024
-3000
-3022
0.05
0.000
6.355
0.15
-5
-0.30
-0:15
-3303
3.006
0.255
-0.0
3.00
03.035
-0.005
death
dogrio
degree
-026
degress
33092
dogres
-0.
2072
-3 3.000
-0.
-6.0
-028
-3.00
-02
F01
0.02
2.000
1dt.
10r
decch
Seath
depth
degth
fractional varianoe, fixing og 0.2
degree
0:355
33055
-8235
0.260
0.225
0.20
-0:30
-2024
2.00
0.30
00:5
-2013
0.000
6,000
201
30F
20F
10
101
10t
122
32*
20'
1.27
12a
32
207
depth
desth
depth
deptt
death
degioe
0.06
degree
0.24
desreee
308
degree
-022
2007
0.00
48
0000
10.44
00.0
-226
1028
-00
3.00
2.05
0.00
0:00
3.00
030
erf nik:: fractional variance, fixing
degroe
dogroe
dogree
degree
degres
6:75
2.00
000
6.05
-0.00 025
-0.00
6645
5.00
020
6.38
5.08
00.00
-0.00
-800
000
-0.00
1.000
000
121
121
10:
1:1
167
30r
10
102
16'
10:
depth
depth
depts
deptr
deptn
dupree
6.06
030
0300
-205
+600
2
-2023
2.030
10*
121 death
13¹
12*
131
107
107
1.7
107
10r
10
16'
depth
depts
depth
Figure 12: 2D contour plots of how fractional variance of each degree varies with a2 and depth, for different slices of of for erf' CK. These plots essentially show slices of the CK 3D contour plots in Fig. 13 For σ 0. /4 for all even degrees k are O, so we omit the plots. Note the rapid change in the shape of the contours for odd degrees, going from of = to of 0.1. This is reflected in Fig. 13 as well.
24

---

Under review as a conference paper at ICLR 2020
Erf Kernels: Fractional Variance Contours
degree
degrom
Oegiee
degree
CK
degrew
degree 3
degine
degrne
Oegnne
NTK
Sepaee3
Figure 13: 3D contour plots of how fractional variance of each degree varies with a² of and (depth), for erf CK and NTK. For each value of fractional variance, as given in the legend on the right, we plot the level surface in the (o of log, (depth))))) corresponding color. The closer blue the color, the higher the value. Note that the contour for the highest values in higher degree plots "floats in mid-air", implling that there is an optimal depth for learning features of that degree that is not particularly small nor particularly big.
achieving this value in the
25

---

Under review as a conference paper at ICLR 2020
E EXPERIMENTAL DETAILS
E.I FIG.
Fig. 3(a), (b) and (c) differ in the set of hyperparameters they involve (to be specified below), but in all of them, train relu networks against a randomly generated ground truth multilinear polynomial, with input space cD12s and L2 loss L(f) ee (f(z) (z)))
Training We perform SGD with batch size 1000. In each iteration, we freshly sample new batch, and we train for total of 100,000 iterations, so the network potentially sees 10 different examples. At every 1000 iterations. we validate the current network on freshly drawn batch of 10,000 examples. We thus record a total of 100 validation losses, and we take the lowest to be the "best validation loss."
Generating the Ground Truth Function The ground truth function f*(x) is generated by first sampling 10 monomials mi,...; m10 of degree k; then randomly sampling 10 coefficients a1...., #10 for them. The final function is obtained by normalizing (a:} such that the sum of their squares is 1:
(x)
0,
(11)
Hy Hlperparaaeters for Fig. 3(a)
The learning rate is half the theoretical maximum learning rate max(Ua, u1)
Ground truth degree & E {0, 2,
Depth 10}
activation = relu
a 2
of =
width = 1000
10 random seeds per hyperparameter combination
training last layer (marked "ck"), or all layers (marked "ntk"). the latter case, we use the NTK parametrization of the MLP (Eq. (MLP).
Hyperparameters for Fig. 3(b)
The learning rate is half the theoretical maximum learning rate 2 max((us f1)-1
Ground truth degree & (0, 3,
Depth E (0....,10}
activation relu
o = 2
of =
width 1000
100 random seeds per hyperparameter combination
training last layer weight and bias only
Note that, because the L2 loss here is L(f) E, ffx)) the maximum learning rate is
X max(uo, p1)=1 (see Thm 4.1 we instead adopt the convention L()) Eyez (((x)-f'(x))
then the maximum learning would 2 max(no. pt))
26

---

Under review as a conference paper at ICLR 2020
Algorithm Binary Search for Empirical Max Learning Rate
upper 16 x theoretical max lower +
tol +- 0.01 x theoretical max Ir
while upper - lower] > tol do f (upper + lower)/2
Run SGD with learning rate for 1000 iterations if loss diverges then
upper
else
lower
end
end while
Output: upper
Hyperparameters for Fig. 3(c)
The learning rate E 0.1
Ground truth degree k {0, 1, ...., 6}
Depth {l
activation & frelu, erf}
o = 2 for relu, but a E (1,2,...,,5 for erf
of (0, 10,,....,4
width 1000
random seed per hyperparameter combination
Training all layers, using the NTK parametrization of the MLP
Eq. (MLP)
E.2 MAX LEARNING RATE EXPERIMENTS
Here we describe the experimental details for the experiments underlying Figs. and
Theoretical max learning rate For fixed setup, compute according Eq. (CK) (if only last layer is trained) or|Eq. (NTK) (if all layers are trained). For ground truth problems where the output is ni-imennionaa,, the theoretical max learning rate is (0 -1; in particular, the max learning rates for MNIST and CIFARIO are times those boolean cube, sphere, and Gaussian. This because the kernel for an multi-output problem effectively becomes
0
K 12
17
0
0
K
where the factor due the factor the scaled square loss C(f.f))= Σ (f(x)()) (x))) The top eigenvalue for 1 @n is just J. times the top eigenvalue for K.
Empirical max learning rate learning rate as in Algorithm
For fixed setup, we perform binary search for the empirical max
Preprocessing In Fig. 5, for MNIST and CIFARIO, we center and project each image onto the sphere VdSd-1 where d = 28 28 784 for MNIST and d 32 32 3072 for CIFAR10. More precisely, we compute the average image T over the entire dataset, and we preprocess each image x =F --=-l -
I: as Vd
Fig. 9 there are three different preprocessing schemes. For "no preprocessing." we In
load the MNIST and CIFAR1O data as is. In "PCA128." " we take the top 128 eigencomponents of the "ZCA128. we take the top 128 eigencomponents
data, so that the data has only 128 dimensions. but rotate it back to the original space, so that the data still has dimension d, where d = 28 x 28 784
for MNIST and d = 3 32 x 32 3072 for CIFAR10.
27

---

Under review as a conference paper at ICLR 2020
Hyperparameters
Target function:
For boolean cube, sphere, and standard Gaussian, we randomly sample degree I polynomial as in [g. (II) For MNIST and CIFARIO, 10, we just use the label in the dataset, encoded one-hot vector for square-loss regression.
Depth E {1, 8, 16]
activation E {relu, erf}
a 2 for relu, but a 21, for erf
of [1....,4}
width = 1000
random seed per hyperparameter combination
Training last layer (CK) or all layers (NTK). In the latter case, we use the NTK parametriza-
tion of the MIP Fgq. (MLP).
F REVIEW OF THE THEORY OF NEURAL TANGENT KERNELS
F.1 CONVERGENCE OF INFINITE-WII KERNELS AT INITIALIZATION
Conjugate Kernel Via central-limit-lik intuition, each unit 16 (x) of Eq.. (MLP) should behave
like Gaussian width n - oc, is of large number of roughly independent random variables (Poole et al. 2016 Schoenholz et al., 2017; Yang and Schoenholz (017). The devil, of course, is what "roughly independent" means and how to apply the central limit theorem (CLT) to this setting. It can done, however, (Lee al. 2018 Matthews al., 2018 Novak al., 2018). and in the most general case, using "Gaussian conditioning' technique, this result can be rigorously generalized to almost any architecture Yang (2019). any case, the consequence that, for any finite set S C X,
(hl (x) laEs converges in distribution to N',,
as min nl } + oc, where y is the CK as given in Eq. (CK)
Neural Tangent Kernel By slightly more involved version of the "Gaussian conditioning" tech- nique, Yang 2019) also showed that, for any x, y E X,
(Voh' Voh (v))
converges almost surely ('(x,))
as the widths tend to infinity, where @ the NTK as given in Eq. (NTK)
F.2 FAST EVALUATIONS OF CK AND NTK
For certain ø like relu erf, Vo and Vo can be evaluated very quickly, that both the CK and NTK can be computed in (2 time, where X' is the set of points we want to compute the kernel function over, and L is the number of layers.
Fact F.1 (Cho and Saul (209)). For any kernel K
Vrelu (e)), x')
(V1 c²
2x
1
Vietu( (K)(z,x²)
(T arccos
2
where K (xxxx1/ K K( x').
Fact F.2 Neal 1995)). For any kernel K, 2
K( K(xxx')
Vent (K)((
aresin
π
V(K(I,)) x) 0.5) (K (x', x²) 0.5)
4
V (K)(()))))
T (1 (K x)) + 2K (K'(x'x'') 4K (Kxxxx))
28

---

Under review as a conference paper at ICLR 2020
Fact F.3. Let (x)) = (xp(z//)ooo some O. For any kernel K,
Vo(K)(a,x²) = exp ( [((,,) + (x, x') ) + (2', x2)
2x²
F.3 LINEAR EVOLUTION OF NEURAL NETWORK UNDER GD
Remarkably, the NTK governs the evolution of the neural network function under gradient descent in the indinite-width limit. First, let's consider how the parameters 0 and the neural network function evolve under continuous time gradient flow. Suppose f is only defined finite input space x²). We will visualize
X fx
f(x')
(
BC
01
0f(w))
80,
8f(a
801
[(x)
v
Vof
f(ak)
ac
On
0f
0f(a*)
(f(*)
80
(best viewed in color). Then under continuous time gradient descent with learning rate '),
0 0
Vof((() = -1 Vefe ((f.f) Vofe T
0e ft
0e 0 = = Vofe
Veft
((((f) =1 O2 VyC(f)
(12)
where θ Voft visualized as
Vof E Rkxk is of course the (finite width) NTK. These equations can be
0,
0 =
-
Thus f undergoes kernel gradient descent with (functional) loss L(f) and kernel O,, This kernel O of course changes evolves, but remarkably, it in fact stays constant for f being infinitely wide MLP (Jacot al. 2018):
Ocfi = -10 C(C(f),
(Training All Layers)
where è is the infinite-widh NTK corresponding to f. A similar equation holds for the CK Σ if train only the last layer,
Off -
(Training Last Layer)
If C is the square loss against a ground truth function f", then VyC(A) I V - 2 } (f+ f"),, and the equations above become linear differential equations. However, typically we only have a training set Ptrain C X' of size far less than |. In this case, the loss function is effectively
C(F) 2 2
1
Σ (()))
with functional gradient
VvC()) Ptrrin
Dtrain
f4)
where Drrain is a diagonal matrix of size x lo whose diagonal is on x E Ltrain and else. Then function still evolves linearly
0.fi nn( Dirsin)- (fe - ff)
(13)
where K is the CK or the NTK depending which parameters trained.
29

---

Under review as a conference paper at ICLR 2020
F.4 RELATIONSHIP TO GAUSSIAN PROCESS INFERENCE.
Recall that the initial fo in Eq. (13) is distributed as Gaussian process (0, Σ) in the infinite width limit. As [g. (13) is linear differential equation, the distribution of fa will remain Gaussian process for all E, whether K CK or NTK. Under suitable conditions, it can be shown that (ee al. (2019), in the limit as t + oo, if we train only the last layer, then the resulting function foe distributed as a Gaussian process with mean Sno given by
(x) Exx, X ( (( Xtrain -1 f (Attrai))
and kernel Var foo given by
Var (s, E(x, E(x, Xtrain EE A
, Atrain -1 E((ttrain .z)).
These formulas precisely described the posterior distribution of f given prior (O, Σ) and data (xx, ("(=)))=xxxtn
If we train all layers, then similarly as +- oc, the function foo is distributed Gaussian process with mean Soo given by (Lee et al. 2019)
(x) (ar, X 0 ( X (2ttrain).
This is, again, the mean of the Gaussian process posterior given prior (0, θ) and the training data {(z, f an expression involving both the NTK θ and the CK Σ; see Lee et al. (2019).
However, the kernel of frr is no longer the kernel this posterior, but rather
In any case, we can make the following informal statement in the limit of large width
Training the last layer (resp. all layers) of an MLP infinitely long, in expecta- tion, yields the mean prediction of the GP inference given prior N E) (resp. (00, θ)).
G A BRIEF REVIEW OF HILBERT--CHMIDT OPERATORS AND THEIR SPECTRAL THEORY
In this section, we briefly review the theory of Scihiet kernels, and more importantly, to properly define the notion of eigenvalues and eigenfunctions. A function K X²2 IR is called Hillert--Shhiidi operator if K E L x X),, i.c.
|
HS
def
E z.y0x
K(x, v² xo.
| I is known as the Hilbert-Schmide norm of K. K is called symmetric if K(x, y) = K K(y,z) and positive definite (resp. semidefinite) if
E X
(z))((,,)f()))
(resp. 2 0) for all f e (x) not a.e. zero
spectral theorem (Mercer's theorem) holds for Hillertt-Shhiin operators.
Fact G.1. If K is a symmetric positive semidefinite Selbert-Schhiit kernel, then there a sequence of scalars X 2 0 (eigenvalues) and functions fü E [2'(X)) (eigenfunctions), for E N, such that
Vi,i, (5) = =I(i=)) and K(x,1) = Σ (.((())))))
EEN
where the convergence is in L2 x X) norm
This theorem allows us to speak of the eigenfunctions and eigenvalues, which are important for training and generalization considerations when K is kernel used in machine learning, as discussed in the main text.
sufficient condition for K to be a Hilbert-SShhmid kernel in our case (concerning only probability measure X') is just that K is bounded, All Ks in this paper satisfy this property.
30

---

Under review as a conference paper at ICLR 2020
2.5
2.0
1.5
1.0
Figure 14: Example of given f
H EIGENDECOMPOSITIOX OF NEURAL KERNEL ON DIFFERENT DOMAINS
H.1 BOOLEAN CUBE
From the Fourier Series Perspective. We continue from the discussion of the boolean cube in the main text. Recall that TA is the shift operator on functions that sends (D-) )) to -)) Notice that, we let (t) = exd for some K E C. then T* = =A exct, Thus & is an "eigenfunction" of the operator Ta with eigenvalue -م, In particular, this implies that
Proposition H.1. Suppose ((t) e²/a² as the case when K the CK or NTK of I-layer neural network with nonlinearity cxp(-/o), up to multiplicative constant FFac F.3). Then the eigenvalue pa over the boolean cube D equals
N* 2 2- exp(-A/oo (xx((AA))))) exp(11o3)
where A = 2/d.
It would be nice if we can express any O as a linear combination of exponentials, so that Eq. (5) simplifies in the fashion Prop H.T this precisely the idea of Fourier series.
We will use the theory of Fourier analysis on the circle, and for this we need to discuss periodic
functions. Let $: [-2, > be defined as
((x)
if E [-1,1]
((x)
( x))
if [1.2]
(p-2 - x)
if -1
See Fig. 14 for example illustration. Note that if & is continuous on [-1, 1]. then & is continuous as periodic function on [-2, 2].
The Fourier basis on functions over 2] the collection (t + mist e
J.ez. Under generic condi-
tions (for example if V E [ 2, 2)), a function v has an associated Fourier series E,ez t We briefly review basic facts of Fourier analysis on the circle. Recall the following notion of functions of bounded variation.
Definition H.2. A function f : [a, b) + IR is said to have bounded variation if
op-
sup
Σ T=0
(f(x,-1- - oo.
where the supremum is taken over all partitions of the interval [a, b).
P= (zo...... Tar S x1 S ... < Znp-
Intuitively, a function of bounded variation has a graph (in (a, b) IR) of finite length.
Fact H.3 (Katznelson) (2004)). A bounded variation function f 2- 2] + IR that is periodic (i.e. f(-2) F(2)) has wectnwwise-covvereee Fourier series:
lim Σ T-
(s)e2 xist
V((), Vt
[-
SEt sE
31

---

Under review as a conference paper at ICLR 2020
From this fact easily follows the following lemma.
Lemma H.4. Suppose & is continuous and has bounded variation on [-1,1]. Then & is also continuous and has bounded variation, and its Fourier Series (on [-2, 2 converges pointwise to o.
Proof. & is obviously continuous and has bounded variation as well, and from Fact H.3 we know periodic continuous function with bounded variation has a pointwise-convergett Fourier Series.
Certainly, Ta sends continuous bounded variation functions to continuous bounded variation func- rist
tions. Because TAe Tist e- feiid &
TA Σ (s)e
Σ Ús)e SEZ
1mis e mist
SEZ
whenever both sides are well defined. If v is continuous and has bounded variation then Ta V is also continuous and has bounded variation, and thus its Fourier series, the RHS above, converges pointwise to Ta V
Now, observe
(1 (1+ =
Σ
Cf
Cd-Rk (I - -r
r=
(I (1 d- (1) = Σ G ((2-r) )
k.kk
r=0
= Pk
Expressing the LHS in Fourier basis, we obtain Theorem H.5.
Σ 11 - e brt
Pk
SEZ
where
1
/ (())e rist dt
(s))
4
[ ((t((e frist + (-1)"ed mistt dt 4 ___
1
is s even (-2 x(t) b(ttsinn()))))) s dt if is odd
[_ +(() cos( di
denote the Fourier coefficients th on 2- (Here is the imaginary unit here, not an index).
Recovering the values of + given the eigenvalues (a..--- Mad Conversely, given eigenvalues μo..... Pa corresponding to each monomial degree, we can recover the entries of the matrix K.
Theorem H.6. For any x. y T with Hamming distance r,
K(a,v) + (( -r A
((
k
pk:
k==
where C Cd--ar- 1))
k+s (5-'(())) as Eq. (7)
Proof. Recall that for any S [d], Xs(x) (z) = S is the Fourier basis corresponding S (see Eq. (3)..
Then by converting from the Fourier basis to the regular hasis, we get
+ (( - A K(I,y) for any 2, y 5od with Hamming distance
p4 Σ xs(x)xs(1).
|
32

---

Under review as a conference paper at ICLR 2020
4x WP
(x
(10
Rox 100
(x)
(x0
-055
(x)
(x0
Figure 15: Examples of Gegenbauer Polynomials for d = 128 (or a = 63).
If x and y differ set T S [d], then simplify the inner sum
- ) ( Σ mk Σ
(-1)lsnTi
Σ 1.
S||=
Remark H.7. we let T be the operator that sends μla + Mo+1, then we have the following operator expression
(((6-))))-10-->>7000
= - (1-7 T) plu
@
Remark H.8. The above shows that the matrix C
=2=241 Iky= satisfies
H.2 SPHERE
Now let's consider the case when X' = Vddd-1 is the radius /d sphere in IR equipped with the uniform measure. Again, because E X' all have the same norm, will consider o univariate function with K(x, y) = (( y) //|[|=|||vv| = 4b (x. /d).
As is long known (Schoenberg 1942 Gneiting 2013 Xu and Cheney 1992 Smola et al. 2001). K
diagonalized by spherical harmonics. review these results briefly below, as we will build on them to deduce spectral information of K on isotropic Gaussian distributions.
Review: spherical harmonics and Gegenbauer polynomials. Spherical harmonics are T.2 func- tions on Sdl1 that are eigenfunctions of the Laplace-Beltrami
Beltrami operator Aga-1 of Sd-1 They can be described as the restriction of certain homogeneous polynomials IRd to 8d-1, Denote by Hd-1.(l) the space of spherical harmonics of degree on sphere 5d-1, Then we have the orthogonal decompo- sition T.2 ( = Di Hd-1.(() It is standard fact that dim Hd-1((1 (d-1-1) (d-2-1)-
There is a special class of spherical harmonics called zonal harmonics that can be represented as (((,,)) y)) for specific polynomials IR IR, and that possess special reproducing property which we will deseribe shortly. Intuitively, the value of any zonal harmonics only depends on the
"height" of along some fixed axis y. a typicaa zonal harmonics looks like Fig. 16 The polynomials
p must be one of the Gegenbauer polynomials. Gegenbauer polyyoomalpolyoomiale {C,
(t) are orthogonal
polynomials with respect to the measure (1 - -2) on [-1, (see Fig. 15 for examples), and here we adopt the convention that
[ Ciol Clo (() 8 2 222-20 + 20) 1(n = f).
(14)
nl(n + [)
Then for each (oriented) axis y Sd-1 and degree there is unique zonal harmonic
z 10(1 E 1d1).())
z 1d-1 (z) def ली ((x)
for any y 8d-1, where cas -42
d-2
Very importantly, they satisfy the following
33

---

Under review as a conference paper at ICLR 2020
-0
-0
0.0
0.
-1.0
0.5
Figure 16: Visualization of zonal harmonic, which depends only on the "height" of the input along fixed axis. Color indicates function value.
Fact H.9 (Reproducing property (Suetin)). For any I E Hd-11(()
E
z 7d-1.10) (2) = f(y)T(( = m)
S4
- 1.00) (2) (m)m)))) = - 1.-1, (z))(( = m) = c c 2
((2, v)) = m)
2r-Sd-1
We also record a useful fact about Gegenbauer polynomials.
Fact H.10 (Suetin..
(1=2x-1 (+1)= (1= 20x - !)
1
By result of Schoonberg 1942). we have the following eigendecomposstion of K on the sphere. Theorem H.11 (Schoenberg). Suppose Gegenbauer expansion
[-1,1] is 1,2 ((1 (2) - so that has the
(1)) R4 ane c - (1).
Then has eigenspaces 2a-1.(0) def (f(x/Vd) f E Hd-1.00) with corresponding eigenval- a₁. Since Di- dd1,(()) is orthogonal decomposition of L3 (3((Vet-1), this describes all Va
eigenfunctions of K considered an operator 1.2 (v
For completeness, we include the proof of this theorem in Appendix
By Bezubik al. (2008), cigenvalues, via derivatives of d:
express the Gegenbauer coefficients, and thus equivalently the
Theorem H.12 (Bezubik al. (2008)). If the Taylor expansion of at O,
(
((1)
n!
n=0
is absolutely convergent on the closed interval [-1,1], then the Gegenbauer coefficients a in Thm H.1l in dimension d is equal to the absolute convergent series
T (11+24) (0) 21+2k KIr ( +1
=
r
(15)
34

---

Under review as a conference paper at ICLR 2020
As the dimension d of the sphere tends oc, the eigenvalues in fact simplify to the derivatives of t
Theorem H.13. Let K be the CK or NTK of an MLP on the sphere v vdsá-1, Then K can be expressed as K (xx, y) = (((x. y) /d) for some smooth ④b [-1.1] + IR. Let denote K 's eigenvalues on the sphere (as in Thm H.l.y. If we fix f and ler d + oc, then
lim d'as = (0), d
where Φ1C) denotes the hth derivalive of +
This theorem is the same as Thm 1.6 except that it concerns the sphere rather than the boolean cube.
Proof. By Thm 1.3. D's Taylor expansion around 0 is absolutely convergent on [-1, 1]. that the condition of Thm H.112 satisfied. Therefore, [q. (15) holds and is absolutely convergent. By
dominated convergence theorem, we can exchange the limit and the summation, and get
(1+ (1+2k) (0)
lim a1 = lim d'r d
+00
( +(++)
K=
8
d' (9)
(1422)) (0)
lim
d=
2 k!ll ( + k)
00
*
$ (((+2k)(0
(0)
lim
2
(k!) 2-
d++00
k=0
(00)
(0)
as desired.
H.3
ISOTROPIC GAUSSIAN
Now let's consider X' Id equipped with standard isotropic Gaussian NN0, 7), so that K behaves like
(z. y)
| d
11v 12
Kf(x)= = K(x,v)((x) =
E
f(v)
v-N((0.))
(o.()..))
|>
d
for any f (O,, In contrast to the previous two sections, K will essentially depend on the effect of the norms || and Iiy/l on Φ.
Note that isotropic Gaussian vector = (O, I) be sampled by independently sampling its direction uniformly from the sphere 1 and sampling its magnitude r from chi distribution Xa with degrees of freedom. Proceeding along this line logic yields the following spectral theorem:
Theorem H.14. function K (IRd) R of the form
K(x, y) = (z. v)
|
1
|=|||||||
d
d
forms a positive semidefinite Hilbert-Schmiit operator on L22 1)) iff & can be decomposed as
(11, Σ
Al (23) (1)
(16)
satisfying
80
223- + d 2-2 2)
Σ
| cd
|
||2
Σ
Cal
<0,
(17)
a1l ال2يي ) (ج
1=0
1=0
where
d-2 Ga.
35

---

Under review as a conference paper at ICLR 2020
are Gegenbauer polynomials as in Appendix H.2 with 1 ((c((22)
VsL C
c (t) (t) dt denoting the norm of C in [2 t2 -
and A are positvve semidefinite Hilbert-Schmidi kernels on (2x()x)), the I space over the probability measure of a Xa-variable divided by d, and with Aill denoting the Hilbert- Schmidt norm of Au.
In addition, K is positive definite iff all A are.
See Appendix for a proof. As consequence, K has an eigendecoomooition as follows under the standard Gaussian measure in dimensions.
Corollary H.15. Suppose K and & are in Thm H. and K is positive semidefinite Hilbert- kernels A₁. Let A₁ have eigendecom-
Schmidt operator, so thar Eg. holds, with position
Ailg. 9')
Σ an (naus(yuuss())
(18)
for eigenvalues an 2 0 and eigenfunctions uis (2xx)) with B uns(g) = 1. Then K has eigenvalues {au 1, E [0, (o)), and each eigenvalue ats corresponds the eigenspace
@ Hd-1.(0) def
|1::11 d
f Hd-1..))
uN
|
where Hd-1,(0) the space of degree spherical harmonics on the unit sphere Sd-1 of ambient dimension d.
For certain simple F, we can obtain {Ath22 explicitly. For example, suppose K is degree-s positive-homogeneooue in the sense that, for a, b >
K K(rr, by) = (ab)* K (x, v).
This happens when K is the CK or NTK of an MLP with degree-s easy that ((,,q, (1)) for some & [- IR, and
Then it's
(1,
1=0
where {ar} are the Gegenbauer coefficients of क.
((1) = Σ aca ( (122) (1)
1=0
We can then conclude with the following theorem.
Theorem H.16. Suppose (IRd)² - is a kernel given by
K(x, y) R( R[[|=]/ /d) 1/dll////////l/ (dd/)((((()) [1/llll))
for some functions R: oo) + IR, कb [-1, R. Let
(tt) Σ
aic d.l
c 12² (t)
1=0
be the Gegenbauer expansion of 6. Also define
def
R(g)2.
1x3
Then the standard Gaussian in Rad K has the following eigendecomposition
36

---

Under review as a conference paper at ICLR 2020
For each 1 2
R H.-10 1 -A-11((1a[/P//0ff//11ll Ha-1.01
is an eigenspace with eigenvalue X²a
For any S E (2()) that is orthogonal R, i.e. S(q) R(g) = 0,
E
g
the function
|[ / /d) (0/f/(///)))
for any f E (13(5)-1) is in the null space of K.
Proof. The A in Eq. (16) for K are all equal to
A(g..9)) X² R(q) R(g')
X
This is rank kernel (on (2) with eigenfunction R/X / and eigenvalue A?. The rest then follows straightforwardly from Thm H.IT
A common example where Thm H.16 applies is when K is the CK of MLP with relu, more generally degree-s positive homogeneous activation functions, so that the in Thm H.16 polynomial.
In general, cannot expect K can be exactly diagonalized in natural basis, {A1120 cannot even be simultaneously diagonalizable. We can, however, investigate the "variance due to each degree of spherical harmonics" by computing
a
def
E x
A((a.))
(19)
which is the coefficient of Gegenbauer polynomials in
al)) def
((1,g.g)= = Σ an C (1))
E g X3
(20)
1=0
Proposition H.17. Assume that q'), is continuous in q and q' Suppose for any d and any t E 1], the random variable ((t, q,4 with q. ~ d=1 x3 has a bound ( q, 9.d') I & Y for some random variable Y with E Y cc. Then for every E 1.
lim a.(()) ltt, 1)1 = O.
Proof. By the strong law of large number, d x2 converges almost surely. Because (tt, q, q') continuous in q and o', almost surely we have ott,, q, q') + (t,, 1, almost surely. Since t is bounded by Y. by dominated convergence, we have
c dt(() 1t,, 9-91-d-1x3
( (. (t, 1, - +
as desired.
In the final part of this section, we show that in the limit of large imput dimension d, the top eigenvalues of K over the standard Gaussian can be easily described (Thm H.19). First, we need to specify some conditions on &.
Definition H.18. Φ : [-1,1] x R+ x R - IR is called reasonable if
There a Taylor expansion in
Belg. E!
((t,g.q')
Σ
(21)
1=
that is absolutely convergent on (1.g.g)) E [11, 1, x R x RR, and such that each Bg is
smooth (C*) on (q. R+ x R
37

---

Under review as a conference paper at ICLR 2020
for all (t,q, E [-1,1] R* x RR, and for any oo), we have [B, q. 9.4 1 C(1 + l0" + ('1") for some constants C,r r > 0 that may depend on but not on L, 9. Theorem H.19. Suppose K is the CK or NTK of an MLP with polynomially bounded activation function. For every degree K over N Ia) has an eigenvalue aw at spherical harmonics degree I (in the sense Cor 11.15 with
040 E
E a.
A((g.)).
E
Arla.9)
gr
where A₁ is as in Eq. (18) Furthermore,
lim d' d=000
A(lg.d)= lim d' A((q,9) - 10 (0, g.0'~2xa
d=
gr
Here ②1() is the lth derivative (1, (1, q, 4') against
Proof. By Lem H.20 below, & is reasonable. Let a 2 Ar(g. 9) as in Eq. (19) and let by def I x Ar(g, g'). Let on be the ith largest eigenvalue of A, as in Eq.. (18) with am being the largest. Note that all of these quantities at, b,, au depend on d, but we suppress this notationally. We seek to prove the following claims:
1. ajo S as
2. ago 2 b
3. bj - (1)) (0,
4. d'a: + 4 (0, 1)
Claim aio S at. First note that a is the trace of the operator A,, so that at cigenvalue ay is at most aj
30 At.. Thus, any
Claim 2: auo Z by. Now, by Min-Max theorem, the largest eigenvalue am of A is equal to
sup Bg.g' f(9)f(''AA(qq.')
Eg f
where 0 E and q. ~ dxă- If we set f(q) = identically, then we get
2 E Ar g') = bi
as desired.
Claims and Now note that we have the following equalities in the Hilbert space L (2 because of the absolute convergence in Eq. (17);
00
(t) def
Φ q. q)
Aelg. al9.9)c...C
(t)
Σ
acc C2
( (t)
t= 3
(t) def
( g. )')
Σ
80
E
Ae (00.))c7/000
(t) Σ
b
bec
1 (t).
9.9
- x
a.''~
t=
Thus, by Eq. (15)
t 11+2M 24) (0)
a: = r
2 2 k!l' ( + k)
By the absolute convergence Eqq. (21)
differentiation commutes with expectation:
((++2)) (0) = +2
E Φ 9.9) = B1+2k(g.g)
Φ (1++2)) (0, 0.9.900 9).
gr xx
qr
1x3
q=
38

---

Under review as a conference paper at ICLR 2020
where B1+2k is as in Eq. (21) Furthermore, as d + 0c, because ( (t, g: q.g') is smooth and polynomially bounded in and d' while 2x3 has exponential tails and converges a.s. to 1, we have
E T ((+2k) (0,0, - (1+2k) (0, 1,
-r x
Finally, by dominated convergence, we get
d'a,= T d
d' $ (1+2k) (0)
2 2k kI +(+ - (0,1),
as desired.
The proof of lim bi =b00 1, 1) is similar.
Lemma H.20. Let 4 be the function corresponding to the CK or NTK of an MLP with polynomially Then & is reasonable (Dein H.18
bounded activation functions. futiuationunncioonss
Proof. The Taylor expansion Eq. (21) its absolute convergence, and the smoothness of B, follows from the proof of Thm 1.3 The polynomial-ouundddees of B₁ follows trivially from the polynomial- boundedness of activation.
H.4 IN HIGHI DIMENSION, BOOLEAN CUBE R SPHERE R STANDARD GAUSSIAN
For the same neural kernel K with K(x,z) v) (((r, v) |= |==11//d (wll//d)) let & be as defined in Eq. (20) and let &s def (tt, 1). Thus & the univariate that we studied in Appendix H.2 in the context of the sphere.
Empirical verification of the spectral closeness As d co. 1x2 converges almost surely to and each A; in Eg. (16) converges weakly to the simple operator that multiplies the input function by A1 1). We verify in Fig. 17 that, for different erf kernels, & approximates & when d is large, which would then imply that their spectra become identical for large d. Note that this is tautologically true for relu kernels with no bias aG 0 because they are positive-homogeneuus.
Next, we compute the eigenvalues of K the boolean cube and the sphere, well as the eigenvalues of the kernel K (xx 3) def Ee((z, /)/l|=||lbll] on the sphere, which "summarizes" the eigenvalues of K the standard Gaussian distribution. In Fig. 18 we compare them for different dimensions up degree (there, "Gaussian" means K the sphere). We see that by dimension 128, all cigenvalues shown are very close to each other for each data distribution.
Theoretical verification of the spectral closeness Thms H.13 H.19 and I.6 show that when the dimension is sufficiently large, the top eigenvalues K an operator on dip is very close the top eigenvalues of K as an operator on VdSd-1 and those of K as an operator on (0, La):
Corollary H.21. Let K be the CK or NTK of an MLP with polynomially bounded activation function. Then K can expressed as K ((x,y) = & (z, v)/d) for some smooth 4 1] + R. Let μt denote the eigenvalue of K as an operator on a corresponding to the eigenspace of degree k polynomials (see Thm 3.1 Let ag denote the eigenvalue of K as an operator on vdsa-1 corresponding to the eigenspace degree le spherical harmonics (see Thm H./ Let aga denote the largest eigenvalue of K as an operator on (O, Ia) restricted to degree k spherical harmonics (see) Thm H.19)
Then for any fixed k 2 0, for sufficiently large d, we have
lim d d
ch lim dhay- lim d'aro (+)) (0) d-soc
d-
where (0) is the kth derivative 4 at O. If ob(H (+) (0) * 0, then
lim pn/ ax lim nn/ un/axo 1. d
d=000
39

---

Under review as a conference paper at ICLR 2020
2,
d=2
d=4
0.5
3.25
d=8
3.15
1.0
0.5
1.0
-1.0
0.5
1.0
d=32
-0.5
3.06
d=128
-1.0
-0.5
0.5
1.0
45
Figure 17: In high dimension d, Gh defined in Eq. (20) approximates & very well. We show for 3 different erf kernels that the function & defining as an integral operator on the sphere is well-aaproximmate by & when is moderately large z 32 seems work well). This suggests that the eigenvalues of K as integral operator on the standard Gaussian should approximate those of K as an integral operator on the sphere.
erf CK 02=2,02=0.001,L-2
aganwalas
d=16
d=32
10-3
d=64
d=128
10
boolean
sphere
10-1
Gaussian
degree
Figure 18: In high dimension d, the eigenvalues are very close for the kernel over the boolean
cube, the sphere, and standard Gaussian. We plot the eigenvalues μ4 the erf CK, with o²
o. = 0)001, depth 2, over the boolean cube, the sphere, as well as kernel on the sphere induced by d. (Eq. (20) We do so for each degree & < 5 and for dimensions d 16,32, 32, 64, 128. We that by dimension 128, the eigenvalues shown are already very close to each other.
40

---

Under review as a conference paper at ICLR 2020
we fix ls and let the input dimension d co, then the fractional variance of degree & converges to (x1))11((((0))00)) (k1)-11((k(0
Σ520(1))
for all three input distributions Ci Vdsá-1 aand Ia).
Practically speaking, only the top eigenvalues matter. Observe that, in the empirical and theo- retical results above, we only verify that the top eigenvalues (f*,, aks or dgo for & small compared to d) are close when d is large. While this result may seem very weak at face value, in practice, the closeness of these top eigenvalues is the only thing that matters. Indeed, in machine learning, we will only ever have finite number, say N, of training samples to work with. Thus, we can only finite N N submatrix of the kernel K. This submatrix, of course, has only N eigenvalues. Furthermore, if these samples are collected eigenvalues approximate the largest N cigenvalues (top N counting multiplicity) of the kernel K itself (Tropp) 2015). As such, the smaller cigenvalues K can hardly be detected in the training sample, and cannot affect the machine learning process very much.
an iid fashion (as typically assumed), then these
Let's discuss more concrete example: Fig. 18 shows that the boolean cube eigenvalues μı are very close to the sphere eigenvalues ag for all k S 5. Over the boolean cube, 1i,,.... AA5 cover eigenspaces of total dimension (6) +... (5). which is 275,584,033 when d = 128. We need at least that many samples to be able to even detect the eigenvalue 146 and the possible difference between it and the sphere cigenvalue ag. But note in comparison, Imagenet, one the most common large datasets in use today, has only about 15 million samples, 10 times less than the number above.
Additionally, in this same comparison, d 128 dramatically pales compared to Imagenet's 's input dimension 3 x 256 = 196608, and even to the those of the smaller common datasets like CIFARIO (d = 3 x 32 3072) and MNIST (d 24 576) if we were to even use the input dimension of MNIST above, then ........ fA5 would cover eigenspaces of 523 billion total dimensions! Hence, it quite practically relevant consider the effect of large d on the eigenvalues, while keeping & small. Again, we remark that even when one fixes & and increases d, the dimension of eigenspaces affected by our limit theorems Thms H.13 1. and 1.6 increases like (dd*), which implies one needs an increasing number (d")) of training samples to see the difference of eigenvalues in higher degrees k.
Finally, from the perspective of fractional variance, we also can see that only the top k spectral closeness matters: Co H.2T for any c > 0, there is a such that the total fractional variance of degree 0 degree (corresponding
eigenspaces of total dimension O(d))) sums up more than 1-c e, for the cube, the sphere, and the standard Gaussian simultancously, when is sufficiently large. This is because the asymptotic fractional variance is completely determined by the derivatives of & at t O.
I OMITTED PROOFS
Theorem 3.1. On the d-dimensional boolean cube LT.d for every S S [d], Xs is an eigenfunction of K with eigenvalue
def
E B ZENA
E x SECo
S
Σ asdd
(4)
where 1 = (I,...,11 E L.
This definition of lild does not depend on the choice S, only on the cardinality of S. These are all of the eigenfunctions of K by dimensionality considerations!
Proof. We directly verify Kxs = M|s|Ss. Notice first that
K K(x, y) & (((z, v)) (( O v, 1)) = K(
where is Hadamard product. We then calculate
(x) E K x))
KLL K(L,roW(row))
Readdes familiar with boolean Fourier analysis may be reminded of the noise operator Tp, < O D'onnell 2014 Defn 2.46). In the language of this work, T, neural kernel with eigenvalues 14
41

---

Under review as a conference paper at ICLR 2020
Here using the fact that x and are boolean to get x = (x 2 y² Changing variable def
2 O ys we get
Kxs(v) - x -Msssss()
as desired. Finally, note that Mis) is invariant under permutation of [d], so indeed it depends only on the size of S.
Theorem H.11 (Schoenberg). Suppose 4 |-1,1] Gegenbauer expansion
R in L2 (2) -2) that it has the
(() Σ
a C 222 (t). (t).
1=0
Then has eigenspaces H021.(0) def (f(z/vd) : f E Hd-1.00 with corresponding eigenval-
Hd-1,() is orthogonal decomposition of 12 (V(St-1))) this describes all ues or. Since D Va
eigenfinnctons of K considered operator on L3 L3(Vd8*-1)
Proof. Let f E Hd-11(m) Then for any æ E Vdsa-1
K(x.v)((/VVd)=
(( (ddf
wEvasa-1
-EvaS
E
((r ((<//VV
jegí-1
1
(l//V ((a/Va..)) s())
E
al
G
SESd-1
Cd.1
1=0
E
Σ aj
(ū) f(0)
jeS4-1
2/V2
On
jES
E
zd-1((0)
2/v0
(,)))
(f)f(i)
by orthogonality
= an (xI/Vd
by reproducing property.
Lemma 3.2. With (& as in Thm 3.1
11 = 2 2T Ta) (T + -T)) (1)))
(5)
d
Cd- $ ((2 -r A
(d
2 Σ
(6)
r=0
where
dd-kk def
(-1rts
dd k) k
Proof. Because Σ, a./d only takes on values { { A (-2 2
+ 1)A ..... 1)A 2A), where
d we can collect like terms in Eq. (4) and obtain
Σ
II Ø i=
+
((2 2 - A
d
r=0 has r --1's
which can easily be shown to be equal to
((-r))))
14 2 c k +
proving Eq. (6) in the claim. Finally, observe that Cid-kikk is also the coefficient of x" in the
polynomial <1 + d)d-k, Some operator arithmetic then yields Rq. (5)
42

---

Under review as a conference paper at ICLR 2020
Theorem H.14. A function K (IR R of the form
K(x,y) y) = (z. y)
|| 1y
d
forms positive semidefinite Hilbert-Schmic operator (O, I)) iff Φ can be decomposed as
a(t,
o (t)
(16)
1=0
satisfying
Σ A 2 Cdll
1=2
1|
Σ |
00
ddl
-2
x2 x23-dT(1 2)
<00,
(17)
11(1 -=2)1 | (5
1=0
where
2-2 ca.
d+2-2
(
Gegenbauer polynomials in Appendix H.2 with |
1002(1-1)) dt denoting the norm of C in 1 1 (2)-111)
and A₁ are positive semidefinite Hilbert-Schmidt kernels on L2 the I space over the probability measure of Xa- 22-variable divided by d, and with || Arll denoting the Hilbert- Schmidt norm of A
In addition, K is positive definite iff all At are.
Proof. Note that an isotropic Gaussian vector (N( 1) can be sampled by independently sampling its direction uniformly from the sphere Sd and sampling its magnitude from chi distribution Xa with d degrees of freedom. In the following, we adopt the following notations
y Rd, 9 /221///d q' /1yll//d, 2/|1=|1, o' y/lloll Then, by the reasoning above,
Kf(x/Vo) = 2 ((o,,))).
E s
Here f E (O, I/d)) (so that f(//d) E L', I)) and d=' is the distribution of a x3 random variable divided by d. Because of this decomposition of 10, into product distribution of direction and magnitude, its space of 1,2 functions naturally decomposes into a tensor product of corresponding 2 spaces
I27 I)) 1.2(8=11) I.2 id
where every f E L, I)) can be written as a sum
f(x) Σ R(())
where q | /d, = x/||0||| as above, Pt (d-1,(1) is spherical harmonic of degree and RG E L x2) (i.e. R2(-/d) E (x))))) Here, the equality is understood as convergence of the RHS partial sums in the Hilbert space (dd-1 & x2)
Likewise, assuming K is Hilbert-Schmidt, then its Hilbert-Schmine norm (measured against the uniform distribution over the sphere) is bounded:
|
E v. 9. g.
(((1, ((,,
x3
(tt, q, o. 22 - -2) dt.
9.9 rd 1x -1
43

---

Under review as a conference paper at ICLR 2020
Thus & resides in the tensor product space
E F del (21 -))
I2 @ x3)
and therefore can be expanded as
(l, Σ Allg,d) (t)
where C xx7)) (t) are Gegenbauer polynomials as in Appendix H.2 and A x2) By
Lem 1.1 below. K being Hilbert-Schmidt implies that each Ag 18, as well. Furthermore, since K Hss- ( |3 finite, we have
c2llc + 00.
1 =
| 2
1=0
Here, ||A:|| =
E / Ar(g: g¹)² is the Hilbert-Schmidt norm of At (i.e. its norm in L2 x2) 22), and ||; - = cf (t) (00(1-))----10 dt is the norm of C
(=2) in
(11(( - 12) -1 Simplifying according to Eq. (14) (14)ds the equality in the claim.
Conversely, if each A is Silbert-Schmidt satisfying Eq. (17) then K is obviously a Hilbert-Schmidt kernel as it has finite Hilhert-Schmidt norm.
Lemma I.1. For each 1, A is positive semidefinite Hilbert-Schmidi kernel. It is positive definite if K is.
Proof. With = / x//|<|] as above, let =(v)) degree nonzero spherical harmonics Pm E (d-1((m) and some scalar function R'm E (d (x) that is not a.e. zero. We have
Pm for some
Kolz/Vd)
E nd
2 (((0,
1
E
Rm (a) Pml Σ
A( ((0,0')
of S
8
Xa
E gdg
Rm (m())) Σ
nd 1x
1=0
(m((v) g2
Amly, Pm
Therefore,
(
(()K/((//V)) 2)
E
Pm(())))
E (
Am )...g)))m(g)))) Rmmldd)
1x3
is nonnegative, and is positive if K is positive definite, by the assumption above that f is not a.e. zero. Since E Pm (v)² as P... f O. must have
Run Am (g. R' (g') 2 (or > if K is positive definite). 9.9 gd
This argument holds for any Rm E semidefinite, and positive definite if K is so.
that is not a.e. zero, so this implies that A, is positive
44

---

Under review as a conference paper at ICLR 2020
Weak Spectral Simplicity Bias
Theorem 4.1 (Weak Spectral Simplicity Bias). Let K be the CK or NTK of MLP on boolean cube W5. Then the eigenvalues Pk. k O,... d, satisfy
po 2 u2
P2k
M1 4122321 ... P2k+1
(9)
Again, there is a function & such that ((x, y) = @ />/l|=/|llllll) By Thm I.3 Taylor expansion with only nonnegative coefficients.
Proof.
has
(c) = + aict azc² +....
By Lem 1.2
Eq. (9) true for polynomials ((c) =
(c(c") 2 p2(c") 2.1"))-. 1 (c')) 2 uz(c") (aacc)2... 2... ...
(22)
Then since each jıg M4 (Φ) is linear function of +, pa (1) Er= (c²))((c)) also follows the same ordering.
Lemma 1.2. Let Ta be the shift operator with step A that sends a function o(-) to D A). Let (c) = c' for some Let μe be the eigenvalue of K (x, y) = (((x, 8) />/l|>/]lll on the boolean cube
KP Then for any S k S d,
11
ift + le odd
(23)
1 12 Mk - Mk 20
if + k is even.
(24)
We furthermore have the identity
-d-2
16-2 kb = =("
24-2
for any 2 k < d.
Proof. As in (5)
(T-TTa)* (T) (1)) (T(1) = 22- cf Edd ((2-r) ))
where C Cd-kek def E (.ag). It's easy observe that
Cd-kk Crd-kik if k is even
-Cd-k = d-r
if le is odd.
In the first case, when ((c) = e¹ with odd, then by symmetry be 0. Similarly for the second case when is even. This finishes the proof for Eq. (23)
Note that it's clear from the form of Eq. (5) that u < ((1) [1[)== always. So we show via induction
on d that the rest of Eq. (24) for any N. The induction will reduce the case of to the case of d 2. So for the base case, we need both d = and 1. Both can be shown by some simple calculations.
Now for the inductive step, assume
Eq. (24) for 2, and we observe that
p p1 2- T2/a) -2 -2 T2/a) d-> ((I T2/a)² (I Tata)
=2 - T2/2)² 2T + T2ía) d- (4T2)a)))))
=2-4+2 -T2/d)* k-2 2
d- (1 -
45

---

Under review as a conference paper at ICLR 2020
By Eq. (5)
expand this into
2-2
(1 2 2
2
4+2
2d-
1 (1- d dd)
r
0
2-2
2 2
2 2- d42
Od Md-k,y k
1 1- d -
0=0
d 2
2-2
Od-k (1
2-
(1-ra- d
d 2
d-2
2k-2'
1-2 By induction, Mk-2 2 0, so we have
=(d=2)
2d-2)
P 11 =
1 2 20
as desired.
Theorem I.3. Let K be the CK or NTK of an MLP with domain vds C Rd. Then K K(r,y) (2.w) | vll
where [-1,1] + I has a Taylor series expansion around 0
Φ(c) = uo + dre + az6? +...
(25)
with the properties that 04 2 0 ffror all i and Σ, 04 $(1) S co, so that Eg. (25) is absolutely convergent on e [-1,1].
Proof. We first prove this statement for the CK of an L layer MLP with nonlinearity c. Let '' be the corresponding d--fnccion for the CK D. suffices to prove this by induction on depth For L= 1, (x, x²) = = (n")- (x,x") + of by Eq. (CK) so clearly 1 (c) an + aie where ag and aj are nonnegative.
Now for the inductive step, suppose E' satisfies the property that " has Taylor expansion of the desired form. We seek to show the same for Σ' and $ First notice that it suffices show this for V (I since multiplication by o2 and addition of of preserves the property. But
V VE (x, x')
E (d(()((2))
where
(z,z')~ ~ N
(1,
(x, x)
3' ) =N vv(,,
E (x)()=)))
( (1)
o ('-((c)
x')
(c)
Φ'-
Using the notation Lem 1.4
we can express this as
4 (c) Φ
V Vo(E'~))z,z") ('))
(26)
Substituting the Taylor expansion of (c) into the Taylor expansion of a given by Lem 1.4 gives us *d-1(c)
a Taylor series whose coefficients are all nonnegative, since those of 41-1(1) and ø are nonnegative as well. In addition, plugging in I for in this Taylor series shows that the sum of the coefficients
equal ((1) 1, so the series is absolutely convergent for [-1, 1]. This proves the inductive step.
For the NTK, the proof similar, except we now also have a product step where we multiply Vor 1I with e and we simply just need to use the fact that product of two Taylor series with nonnegative coefficients is another Taylor series with nonnegative coefficients, and that the resulting radius of convergence is the minimum of the original two radii of convergence.
46

---

Under review as a conference paper at ICLR 2020
Lemma 1.4. Consider any 0 and any ø R - R square-integrable against (N, o²). Then the function
(-1,,, ((c) def EΦ(r)(y)
0² 0²c) where (x. ~ N (0,
occ )
E [Ø(x)
has Taylor series expansion around 0
Ō(c) do + aict agc² + ...
(27)
with the properties that 0; 0 for all and Σ, a2 ((1) 1, that Eq. (27) is absolutely
convergent on e [-1,1].
Proof. Since the denominator of ē doesn't 't depend on c, it suffices to prove this Taylor expansion
exists for its numerator. Let ((c) def
@(oc). Then
E ((x))(y) (xr v) N (0,
)² 0Cc
o²
B (()))(()) (1, ~N 1i (u( 1)]
By Fact I.5 this is just
+ + bic c bāc²² +...
where b, are the Hermite coefficients of क. Since @ E (P(((0,02))
Σ b <0
desired.
Fact 1.5 O'Donnell 20144). For any 6, E LO),)),
(z))((V)) (x, N (0. i)] andy arbic + azb2c +...
where ag and by are respectively the Hermite coefficients of & and ub.
Fixing k, taking the d limit In this subsection, we prove that μa d as d with k fixed. More precisely,
Theorem L6. Let K be the CK or NTK of an MLP on a boolean cube @ Then K can be expressed as K(x, y) (((x, u) / for some + 111,, + R. we fix k and let d - co, then
lim d p4 (0),
d=
where (K) denotes the kth derivative of
An immediate consequence, using the fact that the degree l eigenspace has dimension for large d, is
(
dh /k!
Theorem 5.1 (Asymptotic Fractional Variance). Let be the CK or NTK of an MLP on boolean cube G5' Then can be expressed as K(x, y) (((x, y) dd) for some analytic function + R. If we fix k and let the inpul dimension + 0o, then the fractional variance of degree k converges to
(k:)-11 (k)))))))))))) (0)
(K)))
-120011)100001
where (k) denotes the kth derivative of Tb
Let's s first give some intuition for why Thm 166 should be true.
By Eqs. (8) and (5)
1 Ta
d
Ta
14
((1)
2
2
d-k
1
d -
k
-
2d
r
r=
47

---

Under review as a conference paper at ICLR 2020
where (14) (1 "Ta)* Φ is the kthh backward finite difference with step A = 2/d. Approximating the finite difference with derivative, we thus would expect that, as suggested by [em 1.8
+ | (x) (x)))(()) (2/d)" (z), when d is large.
where (bk) is the kth derivative of Φ. Since 2d (²=²) is the probability mass at r of the binomial variable B def
d E X,, where X; is the Bernoulli variable taking =1 value with half chance each. This random variable converges almost surely to the delta distribution at O, by law of large numbers. Therefore, would expect
1
Pk ~ (1/d)=
as d + DO.
There is a single difficulty when trying to formalize this intuition. One is the possibility that the kth derivative ((aa does not exist at the endpoints and -1 (note that it must exist in the interior, (-1, 1)). In this case, we must show that the portion of the interval [-1, near the endpoints contributes exponentially little mass to the probability distribution of the binomial variable B, that it suppresses any blowup that can happen at the edge.
because by Thm I.3 & is analytic
We formalize this reasoning in the proof below.
Proof. We first prevent any blowup that may happen at the edge. Let liM be the keth backward difference of d with step size A = 2/d, as in Lem 1.8 First note the trivial bound
M (x)= Σ (-1) k
(1r sA) S
④(x xA)
8
< 2 t (x) < 2 (11
since & is nondecreasing by Lem 1.7 Then for any R E [0, (d - k3/2 1).
dh
d-k
d
kb
dt Uk
( (1 - A
2d
r
r=0
d
d-
k-
R-1
kb
( (1 r + dh
k
(d-k)
d k.
o 16 (1 rA).
2
2d
R+1
r=d k-
Now, in the second term, g1 - -r) S (1) as above, so that, by the binomial coefficient entropy bound Factt19)..
d d-k-
R-1
(d (d-ki k) x (1 + S
dh
R
d d (d- (1)
0 S d² ph
Σ
Σ
2d
2d
r=
r=d k-
d
(p) x) ((1)
2d k
d (1)
(28)
21- H (1) (p))())--1
where p = R/(d-k) kt). If we choose R lp(d k)] for fixed p < 1/10, then H()) 1, and 28
is decreasing exponentially fast to 0 with d.
Now we formalize the law of large number intuition. It then suffices show that
dh
d-k- R-1
k
Σ
[k] (1 - + (A)) (0).
2d
R+11
We will do so by presenting upper and lower bound which both converge to this limit.
We first discuss the upper bound. By Lem 1.8
dh
d-k
R-1
dd
d- km R-1
(d-
Σ
A <
Σ
Φ (k) (1 - rA).
2d
2d-k
-=
R+1
48

---

Under review as a conference paper at ICLR 2020
The RHS can be upper bounded by expectation binomial random variable: Let X; be #1 Bernoulli variables, and let + (b)) be the function
c (x) {
if e 23, -1p
otherwise
Note that o (p())( 20 (2:) is bounded function. Then with the binomial variable B = 2i (X++ k/
k)), we have
2d-k Σ
R-
d 2 (1 (1-
rD) (1-r))
E (k) (B).
2p
r
By strong law of large numbers, B converges almost surely RHS converges to
- Do with & fixed. Thus the
$ (k) (0) (0)
as desired.
A similar argument proceeds for the lower bound, after noting that, by Lem 18
R-1
d
k
d
R-1
d - k
Σ
o (1 +) S
④ [k| rA).
2d-k
2d
R+1
R+1
Lemma 1.7. Let K be the CK or NTK of an MLP with domain v Vdsd-1 C Rd. Then K(x, v)
(2..0)
where [-1,1] + analytic on (-1,1), and all derivatives of da are nonnegative
| vil
on
Proof. Note that, by Thm I.3 T has convergent Taylor expansion on (-1, i.e T is analytic on (-1.1). Thus, all derivatives of & exist (and are finite) on the interval (-1,1) and have the obvious Taylor series derived from Eq. (25) For example,
Φ' ('(c) = aic 2aze + 30zc² +....
Such Taylor series also converge on the open interval (-1, 1) (but could diverge on the endpoints - and 1). We get the desired result by noting that all a, are nonnegative.
By expressing finite difference as an integral, it's easy to see that
Lemma 1.8. With the same setting as in Lem 1.7 let (i(k be the kih backward finie difference with step size A = 2/d,
L (x)
(()).
Then ((+) is analytic on (-1,1), has all derivatives nonnegative, and
0 0 & (k) (x KD) < (x) s A (*),
(29)
where (1) is the kth derivative of
Proof. Everything follows immediately from
(1) h1 .... hx) dhi ...
and Lem 1.7
Fact 1.9 (Entropy bound of binomial coefficients). For any and R d/2.
d (d-
R
Σ
< ((p))
where p = RR(dd - k),, and is the binary entropy
H(p) -p pogg p p) logz p)-
49

---

Under review as a conference paper at ICLR 2020
probabiltt vo random networks on (a1)
# cxpth
10:1
reu [2
[1:012
2
probabiito
10-2
of|
10
10a
10a
10
100
10*
rank
Figure 19:
The same experiments as Fig. but over {0, 1)².
J THE {0, 1) VS THE {+1] BOOLEAN CUBE
Valle-Pérez al. (2018) actually did their experiments on the {0, 1]d boolean cube, whereas here, we have focused on the {=1} boolean cube. As datasets are typically centered before feeding into a neural network (for example, using Pytorch's torchvis sino.. rrans form. Norma ze), {+1)d is much more natural. In comparison, using the {0, 1)d cube is equivalent to adding bias in the input of network and reducing the weight variance in the input layer, since any {+1] corresponds to (z + 1) E 13.1 As such, one would expect there is more bias toward low frequency components with inputs from 13
Nevertheless, here we verify that our observations Section above still holds over the {0, 1]dd cube by repeating the same experiments as Fig. 1 in this setting (Fig. 19). Just like over the {+1]d cube, the relu network biases significantly toward certain functions, but with erf, and with increasing of this lessens. With depth 32 and o² the boolean functions obtained from erf network see no bias at all.
50


Reviews:
[{"review_id": "SyeX2Lk6KH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Updates:\n\nThanks for the updates. \n\nI find the new theoretical results interesting and potentially useful,  which shows, in the large $d$ setting, spectrums of CKs/NTKs  for boolean cube, sphere and isotropic Gaussian are closed to each other in some sense. Thus, I raise my score to weakly accepted but lower down my confidence level since I am not that familiar with Boolean cube literature. \n\n\n------------------------------------------------------\nThe study of extremely over-parameterized networks (i.e. infinitely width networks) has become one of the most active research directions in theory deep learning. The key objects in understanding such networks are the conjugate kernel [1, 2] (CK defined in the paper) and the Neural tangent kernels [3] (NTK). The CK characterizes how the network looks like at initialization (connection to Gaussian processes as well) and the NTK is very useful to characterize the gradient descent training dynamics of large width networks in the kernel regime. Understanding properties of such kernels, in particular, their spectra distribution and eigenspace, could be potentially an important step towards a finer-gained understanding of generalization in neural networks.   \n\nThe main contribution of this paper is the development of the spectral theory of CK and NTK on boolean cube (similar or weaker results on uniform distribution in spheres and Gaussian distribution in R^n). More precisely, the authors show that, over the space of boolean cube, the CK/NTK could be diagonalized using the Fourier basis and the eigenvalues depend only on the frequency (i.e. the degree of the monomials); Thm 3.1. The authors also develop some computation tools to compute the spectra; Lemma 3.2.   Using the tools developed in this paper, the authors are able to clarify some of the interesting observations found by other researchers. Most noticeably, the authors show that the observation in [4] 'neural network is biased towards simple functions' is NOT universal. Whether this statement is correct or not depends heavily on the choice of activation function (e.g. Relu v.s. Erf) and hyper-parameters (e.g. weight variance, depths).  There are also some other interesting empirical findings: the optimal depth of a neural network depends on the complexity (i.e. degree in the boolean cube setting) of the function to learn, CK (i.e. training only the last layer) tends to be more useful for learning less complex functions, etc. \n\nOverall, this is a nice paper. I am leaning for a weakly accept. \n\n\n[1] Amit Daniely, Roy Frostig, and Yoram Singer. Toward Deeper Understanding of Neural Networks:\nThe Power of Initialization and a Dual View on Expressivity. arXiv:1602.05897 [cs, stat], February\n2016.\n[2] Jaehoon Lee, Yasaman Bahri, Roman Novak, Sam Schoenholz, Jeffrey Pennington, and Jascha\nSohl-dickstein. Deep Neural Networks as Gaussian Processes. In International Conference on\nLearning Representations, 2018.\n[3] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kernel: Convergence and\nGeneralization in Neural Networks. arXiv:1806.07572 [cs, math, stat], June 2018. 00000\n[4] Guillermo Valle-Pérez, Chico Q. Camargo, and Ard A. Louis. Deep learning generalizes because\nthe parameter-function map is biased towards simple functions. arXiv:1805.08522 [cs, stat], May\n2018.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "S1xeMeCk5B", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper examined the spectrum of NNGP and NTK kernels and answer several questions about deep networks using both analytical results and experimental evidence:\n* Are randomly initialized and trained deep networks biased to simple functions?\n* How does this change with depth, activation function, and initialization?\n\nAll studies are conducted on a space of inputs that is a boolean cube. The input distribution is assumed to be uniform. Though it is argued in Section 3 that the results also generalize to uniform distributions on spheres and isotropic Gaussian distributions. Although this boolean cube setting is followed from previous works on the same topic, it does limit the scope of the paper. Discussions on how this assumption relates to practical problems are missing from the paper.\n\nPutting aside the limitations of restricting the input distributions on boolean cubes (and other similar choices), I really like the paper, which demonstrates the powerfulness of spectral analysis. I also found that many analytical results (e.g., computing eigenvalues of a kernel operator with respect to uniform distributions on a boolean cube) in the paper are highly nontrivial to derive, which adds to the value of the paper. These results might seem restricted in terms of deep network theory because of the assumptions on input distributions, but I do believe the methods used can be of interest to a wider audience.\n\nSome questions:\n* In Figure 1, the 10^4 boolean function samples are sorted according to frequency (rank). What precisely is the frequency (rank) here? It shouldn't be the frequency that corresponds to the eigendecomposition because each function sample could always have multiple components with different frequencies.\n* In Figure 1b, the y-axis is described as normalized eigenvalues, which seems different from degree k fractional variance defined in the next section. The degree k fractional variance is the sum of all normalized eigenvalues for degree k eigenfunctions. Is this difference intended or it is a mistake?\n* Is the ground truth degree k polynomial used in experiments defined somewhere in the paper?\n\nOn writing and clarity. Overall I find this paper well-written and a pleasure to read. Some minor issues are\n* The definition of \"neural kernels\" seems unnecessary and a bit sudden. It would be helpful to include the definition of Phi just after Eq. (2) for CK and NTK.\n* For introducing boolean analysis and Fourier series, it might be better to include the formula that explicit shows the expansion f(x) = \\sum_{S} f^p(S) X_S(x) before introducing Theorem 3.1.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1gapNDTFH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Aiming to resolve the question whether and why deep networks are biased towards simple functions, this paper gives a spectral analysis on neural networks' conjugate kernel(CK) and neural tangent kernel(NTK) on boolean cube. The eigenfunctions are identified and the eigenvalues are shown computable in polynomial time. Another main contribution of this paper is showing that the simplicity bias exists at least in a weak sense.\n\nI believe that this paper should be weakly rejected because it made more claims than what it can show in that the analysis doesn't work in real space, and the authors did not really show the simplicity bias. The following are my detailed comments.\n\nFirst, the whole analysis is based on boolean cube. Although the paper has shown empirically that in high dimension the uniform binary distribution is close enough to the uniform sphere distribution, it doesn't suffice to substitute boolean cube for sphere in real space. The spectral analysis in this paper is heavily due to working on boolean cube. The boolean cube is finite, which guarantees any inner-product kernel function $K(x,y) = \\Phi (<x,y>)$ can be diagonalized by finite many monomial functions, And there are only O(d) different eigenvalues, which enables efficient computation. These techniques are not easy to be transferred to real space. The experiment shows that the first five eigenvalues in boolean cube, sphere, gaussian is close, but key problems here are first, in practive the dimension $d$ could be smaller and second, sphere and gaussian have infinitely many eigenvalues while boolean cube has $2^d$ eigenvalues. The experiment cannot really justify that all eigenvalues are close (only first several are shown), not to mention the tail eigenvalues over the first $2^d$-th.\n\nEven if we assume that boolean cube is a reasonable choice, we should notice the goal of computing eigenvalues is to eventually show the inductive bias toward 'simple functions'. However, the authors failed to show it at least from the following perspectives:\n1) This paper did not show the trend of eigenvalues, but only the weak version of, for example, $\\mu_{2k-2} > \\mu_{2k}$. In the limiting case, it is more reasonable to fix dimension $d$ rather than the degree $k$.\n2) Working on boolean cube leads to limited complexity. The most complicated base function is restricted to $\\mathcal{X}_S$ where $S = \\{1, 2, \\dots, d\\}$. So the weak simplicity bias theorem actually only describes the relation among finite $d$ eigenvalues.\n3) No optimization arguments appear in this paper. Based on the spectral analysis, it is not rigorous enough to claim the networks are biased to simple functions, given that the target function consists of simple multilinear monomial functions. \n\nSince the boolean spectra is not a reliable measure, the further experiments under such a measure is therefore put under doubt.\n\nTo summarize, this paper definitely contains some rigorous analysis which I appreciate, but it made some claims that are not verified. More importantly, the boolean cube is not the appropriate domain which is hard to generalize to real space and the simplicity bias theorem in this paper is to some extent weak. Therefore, I suggest rejecting this paper in its current form.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors develop a spectral analysis on the boolean cube for the neural "conjugate kernel" (CK) and "tangent kernel" (NTK). The analysis sheds light into inductive biases of neural networks, such as whether they are biased to simple functions.  

This work contains rigorous analysis and theory which is useful for further discussions. However, the theory and insights do not feel complete. One important drawback is that the analysis is limited by the boolean cube setting; this also means that it is more difficult to link theory to practical scenarios. This has been discussed a lot during the rebuttal and among reviewers. Empirical validation has attempted to deal with these concerns, but it would be useful to have this validation coming from theory, or at least have further relevant theoretical insights. This could happen by further building on the theorem provided in the rebuttal for eigenvalue behavior when d is large.
Decision: Reject