Towards Understanding the Spectral Bias of Deep Learning
Authors: Yuan Cao
Zhiying Fang
Yue Wu
Ding-Xuan Zhou
Quanquan Gu
Venue:  (2020)

Abstract: An intriguing phenomenon observed during training neural networks is the spectral bias, where neural networks are biased towards learning less complex functions. The priority of learning functions with low complexity might be at the core of explaining generalization ability of neural network, and certain efforts have been made to provide theoretical explanation for spectral bias. However, there is still no satisfying theoretical results justifying the existence of spectral bias. In this work, we give a comprehensive and rigorous explanation for spectral bias and relate it with the neural tangent kernel function proposed in recent work. We prove that the training process of neural networks can be decomposed along different directions defined by the eigenfunctions of the neural tangent kernel, where each direction has its own convergence rate and the rate is determined by the corresponding eigenvalue. We then provide a case study when the input data is uniformly distributed over the unit shpere, and show that lower degree spherical harmonics are easier to be learned by over-parameterized neural networks.

Under review as a conference paper at ICLR 2020
TOWARDS UNDERSTANDING THE SPECTRAL BIAS OF DEEP LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
An intriguing phenomenon observed during training neural networks is the spee- tral bias, where neural networks are biased towards learning less complex func- tions. The priority of learning functions with low complexity might be the core of explaining generalization ability of neural network, and certain efforts have been made to provide theoretical explanation for spectral bias. However, there is still no satisfying theoretical result justifying the underlying mechanism of spectral bias. In this paper, we give a comprehensive and rigorous explanation for spectral bias and relate it with the neural tangent kernel function proposed in recent work. We prove that the training process of neural networks can be de- composed along different directions defined by the eigenfunctions of the neural tangent kernel, where each direction has its own convergence rate and the rate is determined by the corresponding eigenvalue. We then provide a case study when the input data is uniformly distributed over the umit sphere, and show that lower degree spherical harmonics are easier to be learned by wer-parameterized neural networks.
INTRODUCTION
pver-parameterized neural networks have achieved great success in many applications such as com- puter vision (He et al., 2016), natural language processing (Collobert and Weston, 2008) and speech recognition (Hinton et al., 2012). It has been shown that over parametermmeee neural networks can fit complicated target function or even randomly labeled data (Zhang al., 2016) and still exhibit good generalization performance when trained with real labels. Intuitively, this is at odds with the traditional notion of generalization ability such as model complexity. In order to understand neural network training, a line of work (Soudry et al., 2017; Gunasekar et al., 201 8b;a) has made efforts in the perspective of "implicit bias", which states that training algorithms for deep learning implicitly pose inductive bias onto the training process and lead to solution with low complexity measured by certain norms in the parameter space of the neural network.
Among many attempts establish implicit bias, Rahaman et al. (2018) pointed out an intriguing phenomenon called spectral bias, which says that during training, neural networks tend to learn the components of lower complexity faster. The concept of spectral bias is appealing because this may intuitively explain why over-parameterized neural networks can achieve a good generalization performance without overfitting. During training, the networks fit the low complexity components first and thus lie in the concept class of low complexity. Arguments like this may lead to rigorous guarantee for generalization.
Great efforts have been made in seek of explanations about the spectral bias. Rahaman et al. (2018) evaluated the Fourier spectrum of ReLU networks and empirically showed that the lower frequencies are learned first; also lower frequencies are more robust to random perturbation. Andoni et al. (2014) showed that for sufficiently wide two-layer network, gradient descent with respect to the second layer can learn any low degree bounded polynomial. Xu (2018) provided Fourier analysis to two- layer networks and showed similar empirical results on one-dimensional functions and real data. Nakkiran et al. (2019) used information theoretical approach to show that networks obtained by stochastic gradient descent can be explained by a linear classifier during early training. All these studies provide certain explanations about why neural networks exhibit spectral bias in real tasks. But explanations in the theoretical aspect, if any, are to some extent restricted. For example, the popular Fourier analysis is usually done in the one-dimensional setting, and thus lacks generality.

---

Under review as a conference paper at ICLR 2020
Meanwhile, recent line of work (Jacot et al., 2018; Du et al., 2018b; Li and Liang, 2018; Chizat and Bach, 2018) has shed light on new approaches to analyze neural networks. In particular, they condition, the neural network trained by gradient de-
show that under certain over-parameteriza scent behaves similar to the kernel regression predictor using the neural tangent kernel (NTK) (Jacot et al., 2018). Du et al. (2018b) showed that the convergence is provably guaranteed under cer- tain over parameterization conditions determined by the smallest eigenvalue of NTK. Arora et al. (2019b) further gave a finer characterization of error convergence based on the eigenvalues of NTK's Gram matrix. Su and Yang (2019) improved the convergence guarantee in terms of the k-th largest eigenvalue for certain target functions.
Inspired by these works mentioned above, we can present theoretical explanation for spectral bias. Under NTK regime, we establish a precise characterization for the training process of neural net- works. More specifically, we theoretically prove that wver-parameterized neural networks' training process can be controlled by the eigenvalues of the integrating operator defined by the NTK. Un- der the specific case of uniform distribution on unit sphere, we give exact calculation for these eigenvalues and show that the lower frequencies have larger eigenvalues, which thus leads to faster convergence. We also conduct experiments to corroborate the theory establish.
Our contributions are highlighted as follows:
1. We prove a generic theorem for arbitrary data distributions, which states that under certain sample complexity and preammteeettiiiioonnnn conditions, the error term's convergence along different directions actually relies on the corresponding eigenvalues. This theorem gives a more precise control on the regression residual than Su and Yang (2019), where the authors focused on the case when the labeling function is close to the subspace spanned by the first few eigenfunctions.
We present more general result about the spectra of the neural tangent kernel. particular, we show that the order of eigenvalues appears as μ4 (mmaammaa==----- d Our result is better than the bound [2(A -2()=d-1) derived in Bietti and Mairal (2019) when >> k. which is clearly a more practical setting.
3. We establish rigorous explanation for the spectral bias based on the aforementioned theoretical results without any specific assumptions on the target function. We show that the error terms from different frequencies are provably controlled by the eigenvalues of the NTK, and the lower- frequency components can be learned with less training examples and narrower networks with faster convergence rate. As far as know, this is the first attempt to give comprehensive theory justifying the existence of spectral bias.
1.1 ADDITIONAL RELATED WORK
Recently, there a rich literature about the property of neural tangent kernel. Jacot al. (2018) first showed that during training, the network function follows a descent along the kernel gradient with respect to the Neural Tangent Kernel (NTK) under infinity width setting. Li and Liang (2018) and Du et al. (2018b) implicitly built connection between Neural Tangent Kernel and gradient descent by showing that GD can provably optimize sufficiently wide two-layer neural networks. In Du et al. (2018b), it is shown that gradient descent achieve zero training loss a linear convergence rate for training two-layer ReL.U network with square loss. Allen-Zhu et al. (2018); Du et al. (201 8a); Zou et al. (2018); Cao and Gu (2019b); Arora et al. (2019a); Zou and Gu (2019); Cao and Gu (2019a) further studied the optimization and generalization of deep neural networks. These papers are all in the so-called neural tangent kernel regime, and their requirements on the network width depend either implicitly or explicitly on the smallest eigenvalue of the kernel Gram matrix. Later, Su and Yang (2019) showed that this smallest eigenvalue actually scales in the number of samples and will eventually converge to O. In order to obtain constant convergence rate, Su and Yang (2019) assumed that the target function f can be approximated by the first few eigenfunctions of the integrating operator L, f(s) Sgr s((z s)f(s)) where x(-..) -) is the NTK function and r(s) is the input distribution, and proved linear convergence rate up to the this approximation error.
A few theoretical results have been established towards understanding the spectra of neural tangent kernels. Bach (2017) studied two-layer ReLU networks by relating it to kernel methods, and pro- posed harmonic decomposition for the functions in the reproducing kernel Hilbert space which utilize in our proof. Based on the technique in Bach (2017). Bietti and Mairal (2019) studied the eigenvalue decay of integrating operator [xx) defined by NTK on unit sphere by using spheri-
2

---

Under review as a conference paper at ICLR 2020
cal harmonics. Vempala and Wilmes (2018) calculated the eigenvalues of NTK corresponding to two-layer neural networks with sigmoid activation function. Basri et al. (2019) established similar results as Bietti and Mairal (2019), but considered the case of training the first layer parameters of two-layer networks with bias terms. Yang and Salman (2019) studied the the eigenvalues of integral operator with respect the NTK Boolean cube by Fourier analysis.
The rest of the paper is organized as follows. We state the notation, problem setup and other prelim- inaries in Section 2 and present our main results in Section 3. In Section 4, we present experimental results to support our theory. Proofs of our main results can be found in the appendix.
PRELIMINARIES
In this section we introduce the basic problem setup including the neural network structure and the training algorithm, as well some background on the neural tangent kernel proposed recently in Jacot et al. (2018) and the corresponding integral operator.
2.1 NOTATION
We use lower case, lower case bold face, and upper case bold face letters to denote scalars, vectors and matrices respectively. For vector
"0i.....,a))) E Id and number 1 < p 00, we denote its n-nor by |Vv|pp = Eh lexl)) 1/,, We also define infinity norm by l|v|| max; [ug]- For matrix A (Ai,) mxn, we use All to denote the number of non-zero entries of A, and use || ( A2,) 1/2 to denote its Frobenius norm. Let ||A||p max Avlpp for p > 1, and |A|| max m |A, For two matrices A, B E R= we define (A, B) = Tr(A We use A B if A B positive semi-definite. In addition, we define the asymptotic notations O(-), (()).()) and 52(-) as follows. Suppose that a, and 6, be two sequences. We write a, = (b,,) lim -up la,,/b,.l sc, and an = (bb,,) if lim inf lan/bal > 0. We use O(.) and ((-) to hide the logarithmic factors in O-)) and (2(-).
2.2 PROBLEM SETUP
Here introduce the basic problem setup. We consider two-layer fully connected neural networks of the form
fw(x) = Vm. W Wix),
where W, e 1d++1), W R xmml are the first and second layer weight matrices respectively, and (-) = (0, is the entry-wise ReLU activation function. The network is trained according to the square loss on training examples S {(x;, vi) i [n]]]:
Ls(W)
1
Σ (x:
(u (x,)))))
where 0 is a small coefficient to control the effect of initialization, and the data inputs {xx][_ assumed to follow some unknown distribution 7 on the unit sphere gd e RR+11, Without loss of generality, also assume that |y4| < 1.
We first randomly initialize the parameters of the network, and then apply gradient descent to opti- mize both layers. We present our detailed neural network training algorithm in Algorithm 1.
Algorithm GD for DNNs starting at Gaussian initialization
Input: Number of iterations T, step size 77. Generate each entry ( and w from (00,2/m) and N 1/m) respectively.
fort= = O, 1..... T 1 do
Update ((++1) ( -1 VwLs(W(!))
end for Output: W(T)
'eere the dimension of input is d + since throughout this paper assume that all training data lie in the d-dimensional unit sphere 8d e dR
3

---

Under review as a conference paper at ICLR 2020
The initialization scheme for W given in Algorithm is known He initialization (He al., 2015). This scheme generates each entry of the weight matrices from a Gaussian distribution with mean zero. The variances of the Gaussian distributions in initialization principle that the initialization does not change the magnitudes of inputs in each layer. The sec- ond layer parameter is not associated with the ReLU activation function, thus it is initialized with variance 1/m instead of 2/m.
chosen following the
2.3 NEURAL TANGENT KERNEL
Many attempts have been made to study the convergence of gradient descent assuming the width of the network is extremely large (Du et al., 201 8b; Li and Liang, 2018). When the width of the network goes to infinity, with certain initialization on parameters, the inner product of gradients of the output function would converge limiting kemnl,, i... Neural Tangent Kernel (Jacot et al., 201 8). In this paper, we denote by x(x,x') = limm-sco m ( (V (x), V Vw Vwfo (x')) and have
x(x,x') = (x,x) (x(,x') + x2(xxx)),
(2.1)
where
(1 x') = E Ew-N x))o ((w, x')], R2 x2 x') = -ow (
(2.2)
Since we apply gradient descent to both layers, the Neural Tangent Kernel is the sum of two different kernel functions and clearly it can be reduced one layer training setting. These two kernels are arc-cosine kernels of degree 0 and 1 (Cho and Saul, 2009). Their explicit expressions are given as
1 (t (π arccos (f)) V1 12). -1-
(f)
2T (π arccos (t)), (2(() 2x
(2.3)
where (x, x (|x/ |Ix|I).
2.4 INTEGRAL OPERATOR
The theory of integral operator with respect to kernel function has been well studied in machine learning (Smale and Zhou, 2007: Rosasco et al., 2010) thus we only give a brief introduction here. (X) Let (2(X) be the Hilbert space of square-interrable functions with respect to Borel measure from X - IR. For any continuous kernel function Xx IR and we can define an integral operator L (X) by
(x(f(xx= = m(xx)) XE
(2.4)
has been pointed out in Cho and Saul (2009) that arc-cosine kernels are positive semi-definite. Thus the kernel function defined by (2.1) is positive semi-definite being a product and sum of positive semi-definite kernels. Clearly this kernel is also continuous and symmetric. Thus we know that the neural tangent kernel is Mercer kernel.
3 MAIN RESULTS
In this section present main results. In Section 3.1, give general result the conver- gence rate of gradient descent along different eigendirections of neural tangent kerne.. Motivated by this result, in Section 3.2, we give uniformly distributed over the unit sphere sd. In Section 3.3, we combine the spectrum analysis with the general convergence result give explicit convergence rate for uniformly distributed data on the unit sphere.
study the spectrum of Thp, when the input data
3.1 CONVERGENCE ANALYSIS OF GRADIENT DESCENT
In this section we study the convergence of Algorithm Instead of studying the standard conver- gence of loss function value, aim to provide refined analysis on the speed of convergence along different directions defined by the eigenfunctions of Lg. first introduce the following definitions and notations.
4

---

Under review as a conference paper at ICLR 2020
Let (Ariea with A1 > A2 > be the strictly positive eigenvalues of Lx, and Φ1 (-), 22(+), ..... be the corresponding orthonormal cigenfunctions. Set V, ()(x)) (x,x),,) (x,)) " 1, ..... Note that L₁ may have eigenvalues with multiplicities larger than 1 and X > are not distinct. Therefore for any integer k, we define rk as the sum of the multiplicities of the first & distinct eigenvalues of Lg- Define V,, (V1,....
Vra).. Vr..)...r................... By definition, vi. i E [r*] are rescaled restrictions of orthonormal functions in (8)) on the training examples. Therefore we can expect them to form set of almost orthonomal bases in the vector space R". The following lemma follows by standard concentration inequality.
Lemma 3.1. Suppose that [x)] & M for all x sd and i [rx] For any 5 > O, with probability at least 1 - 6,
V V I max & CM2VVoogl log(rr/0)//
where C' is an absolute constant.
Denote y (y1,...,,'. and g(0) = 0 (Swio (xi) S (x,)). o...., Then Lemma 3.1 shows that the convergence rate of [VT, (y - (11 roughly represents the speed gra- dient descent learns the components of the target function corresponding to the first r3 eigenvalues. The following theorem gives the convergence guarantee of V (y- -f(())2
Theorem 3.2. Suppose (x)] & M for [r*] and x E s4, For any e, > 0 and integer k. if n > 0(c=2. max ((Ar. - -rr+t1) - m > ((polyyT A-) then with probability at least 1 8, Algorithm 1 with 1) ((mm²) 10((m00))1)))) )))))))))))))))) Ö(e) satisfies
n 1/2 V Fg (y - )(7) - &
- 2(1-~r,,) >..))" n 1/2 y122
Remark 3.3. Theorem 3.2 theoretically reveals the spectral bias of deep learning. Specifically, as long as the network is wide enough and the sample size is large enough, gradient descent first learns the target function along the the eigendirections of neural tangent kernel with larger eigenvalues, and then learns the rest components corresponding learning the components corresponding to larger cigenvalues can be done with smaller sample size and narrower networks, our theory pushes the study of neural networks in the NTK regime towards a more practical setting. For these reasons, we believe that Theorem 3.2 to certain extent explains the empirical observations given in Rahaman et al. (2018), and demonstrates that the difficulty of function to be learned by neural network can be characterized in the eigenspace of neural tangent kernel: if the target function has a component corresponding to a small eigenvalue of neural tan- gent kernel, then learning this function up to good accuracy takes longer time, and requires more examples and a wider network.
smaller eigenvalues. Moreover, by showing that
3.2 SPECTRAL ANALYSIS OF NEURAL TANGENT KERNEL FOR UNIFORM DISTRIBUTION
After presenting general theorem (without assumptions on data distribution) in the previous sub- section, we now study the case when the data inputs are uniformly distributed over the unit sphere. We present our results (an extension of Proposition 5 in Bietti and Mairal (2019)) of spectral analy- sis of neural tangent kernel. We show Mercer decomposition of neural tangent kernel for two-layer setting. We give explicit expression of eigenvalues and show orders of eigenvalues in both cases when d >> k and k >> d.
Theorem 3.4. For any x, x' Sd Rd-1, we have the Mercer decomposition of the neural tangent kernel K Sd x gd IR,
((d.)) YE, (x) (x'),
(xxx)
Σ
14 Σ
(3.1)
where Ye for j = 1.... (d,, k) are linearly independent spherical harmonics of degree k in d+ 1
variables with N(d, k) 2k+d-1 (k+d-2) and orders of μ4 are given by
140 = = -((1,, 1h = 0, k = 2j + 1,
#4 = Z (max (d k (k: + d) k-d d k (k: + d)- --- 2d+2 2k d) -kd-1]] k 2j,
where j E N More specifically, we have μu = D (k: 1) when k >> d and u4 = S (d-
when d >> k k 2, 2,4,6....
5

---

Under review as a conference paper at ICLR 2020
Remark 3.5. In the above theorem, the coefficients Pa actually different eigenvalues of the integral operator Ln on (8") defined by
= S x(x. x(xx))) f LT
(x(f(r) =
where Ta is the uniform probability measure on unit sphere S Therefore the Ar in Theorem 3.2 is just 1 given in Theorem 3.4 when Ta is uniform distribution.
Remark 3.6. Vempala and Wilmes (2018) studied two-layer neural networks with sigmoid tivation function, and established guarantees to achieve <o + e error with iteration complexity T (d+1) (k) log (Il/* la/e) under the peraraaattttiitiiioonn condition m = (d+1) (()plly()) la/c), where _ is the target function, and en is certain function approximation error. Another highly re- lated work is Bietti and Mairal (2019), which gives 14; (((k--11). The order of eigenvalues we present appears as jo [M ( d. dd dd). This is better when k. which is closer to the practical setting.
3.3 EXPLICIT CONVERGENCE RATE FOR UNIFORMLY DISTRIBUTED DATA
In this subsection, combine results in the previous two subsections and give explicit conver- gence rate for uniformly distributed data on the unit sphere. Note that the first distinet eigenvalues of NTK have spherical harmonics up to degree k 1 as eigenfunctions.
Corollary 3.7. Suppose that & d and the sample {x,]__ follows the uniform distribution Ta the unit sphere $d. For any e, 8 > and integer k, if n > (e -2 max 2d 22d-222))), m > (poly(T, katt,e=1)), then with probability at least 8, Algarithm with ((m6))-1), 0 Ö(e) satisfies
n2 1/2 V ra - & 2 ((1="" n 1122 v +
where ты = > N(d,k) k') and Vr. = (n- (n 12-1 (x:))xx with ,r....,,r. being set of or- thonomal spherical harmonics degrees up -- 1.
Corollary 3.8. Suppose that d
and the sample {x1 follows the uniform distribution Ta on the unit sphere gd. For any 6,5 > 0 and integer k if n > Ô( 2(k2222))))) m > ((poly(T,d ad-²,,e=)), then with probability at least 8, Algorithm with 17 Ö((mf?)-1) Ö(c) satisfies
n -1/2 IV (y - & 2 (1 n 11/2, y
k- where rkk -K kd, and Vr, thonomal spherical harmonics of degrees up to
with Φ .1,-..,0r or. being set of or-
Corollaries 3.7 and 3.8 further illustrate the spectral bias of neural networks by providing exact calculations of Ary Vr,, and M in Theorem 3.2. They show that if the input distribution is uniform over unit sphere, then spherical harmonics with lower degrees are learned first by over-parameterized neural networks.
Remark 3.9. In Corollaries 3.7 and 3.8, it shows that the conditions tially on either i or We would like to emphasize that such exponential dependency is reasonable and unavoidable. In our pendency in & is natural consequence of the fact that in high dimensional space, there are a large number of linearly independent polynomials even for very low degrees. It is apparently only reason- able to expect to learn less than independent components of the true function, which means that it unavoidable to assume
and m depend exponen-
take the d >> k setting
example. The exponential de-
N(d,k)
Σ
2 + d
d
(k'dd-2))
+
2k' + d
(x--))
((dd-1)).
k
k'
K-O
K-0
Similar arguments can apply the requirement of and the k d setting.

---

Under review as a conference paper at ICLR 2020
4 EXPERIMENTS
In this section illustrate results by training neural networks synthetic data. Across all tasks, we train two-layer hidden neural networks with 4096 neurons and initialize it exactly as defined in the setup. The optimization method is vanilla full gradient descent. We sample 1000 training data which is uniformly sampled from the unit sphere in R
4.1 LEARNING COMBINATION OF SPHERRCCAL HARMONICS
First, we show a result when the target function is exactly linear combination of spherical harmonics. The target function is explicitly defined
(x) = 01 Pi(KS x)) + 02 P2((S2, x)) + 04 P)((
where the P&(() the Gegenbauer polynomial, and Çk. 1, 2, 4 are fixed vectors that are inde- pendently generated from uniform distribution on unit sphere in R in our experiments. Note that according to the addition formula _j=1 - YKu Y (y) N NNd,, (xxx y))) every normalized Gegenbauer polynomial a spherical harmonic, so f (x) is linear combination of spherical har- monics of order 1,2 and 4. The higher odd-order Gegenbauer polynomials are omitted because the spectral analysis showed that μ4 for 3, 5, 7....
Following the setting in section 3.1, we denote Va n (/x)((( (x.))) By Lemma 3.2 Vi 's are almost orthonormal with high probability. So we can define the (approximate) projection
length of residual r(() onto Vi at step I as
ā = Gv=lvvr(()) !v)
where (()) (x)(xx)) - ffw (x))..... (x,)) fw (x,) and fwoe (x) is the neural network function.
Remark 4.1. Here ā& is the projection length onto an approximate vector, In the function space, we can also project the residual function r(x) f*(x) - ( onto the orthonormal Gegenbauer functions Px Replacing the training data with randomly sampled data points x; can lead random estimate of the projection length in function space. We provide the corresponding result for freshly sampled points Appendix E.
('(xr (z)) ( 12()) (P()))
f"(x) 1P)(2) 3P 5P(())
12
k=1
projection length åk
projection length āk
k=2
k=4
k=4
0..
0.4
0.0
2500
5000
7500
10000
12500
15000
17500
20000
0
2500
5000
7530
10000
12509
15600
17500
20003
step
step
(a) components with the same scale
(b) components with different scale
Figure 1: Convergence curve for projection length onto different components. (a) shows the curve when the target function have different component with the same scale. (b) shows the curve when the higner-order components have larger scale. Both illustrate that the lower-order components are learned faster. Log-scale figures shown in Appendix E.2.
The results showned in Figure 1. It can be seen that the beginning of training, the residual at the lowest frequency (k- = 1) converges to zero first and then the second lowest (A: = 2). The highest frequency component is the last one converge. Following the setting of Rahaman al. (2018) assign high frequencies a larger scale, expecting that larger scale will introduce a better descending speed. Still, the low frequencies regressed first.

---

Under review as a conference paper at ICLR 2020
4.2 LEARNING FUNCTIONS OF SIMPLE FORM
Apart from the synthesized low frequency function, we also showed the dynamics of normal func- tions' projection to (a))). These functions, though in simple form, have non-zero components in almost all frequencies. In this subsection we further show our results still apply when all frequencies exist in the target function, which is given by f*(x) M. cos(a,<S x)) or fx) (, where Ç is fixed unit vector. The coefficients of given components are calculated in the same way in Section 4.1.
(2) cos(42) + cos(62)
(()x) = 10fa²
1.75
k=2
k=2
projection length āv
10-
k=4
projection length ak
1.50
k=4
0.
k=6
125
k=6
1.00
0.6
0.75
0.4
0.50
0.25
2300
5000
75.00
10000
12303
35300
17300
20000
2500
5000
7300
10000
22000
20000
step
step
(a) cosine function along one direction
(b) even polynomial along one direction
Figure 2: Convergence curve for different components. (a) shows the curve of a trigonometric function. (b) shows the curve of polynomial with even degrees. Both exhibits similar tendency as combination of spherical harmonics.
Figure 2 shows that even for arbitrarily chosen functions of simple form, the networks can still first learn the low frequency components of the target function. Notice that early in training not all the curves may descend, we believe this is due to the unseen components' influence on the gradient. Again, as the training proceeds, the convergence controlled the predicted rate.
Remark 4.2. The reason why we only use cosine function and even polynomial is that the only odd basis function with non-zero eigenvalue is (xx.. To show a general tendency it is better restrict the target function in the even function space.
CONCLUSION AND DISCUSSION
In this paper, we give theoretical justification for spectral bias through a detailed analysis of convergence behavior of two-layer neural networks with ReLU activation function. We show that the convergence of gradient descent in different directions depends on the corresponding eigenval- ues and essentially exhibits different convergence rates. We show Mercer decomposition of neural tangent kernel and give explicit order of eigenvalues of integral operator with respect to the neural tangent kernel when the data is uniformly distributed on the unit sphere Sd. Combined with the convergence analysis, we give the exact order of convergence rate on different directions. We also conduct experiments synthetic data to support our theoretical result.
So far, we have considered the upper bound for convergence with respect to low frequency com- ponents and present comprehensive theorem to explain the spectral bias. One desired improvement is to give the lower bound of convergence with respect to high frequency components, which is es- sential to establish tighter characterization of spectral-biased optimization. It is also interesting to extend our result to other training algorithms like Adam, where the analysis in Wu et al. (2019); Zhou et al. (2018) might be implemented with a more careful quantification on the projection of residual along different directions. Another potential improvement is to generalize the result to multi-layer neural networks, which might require different techniques since our analysis heavily rely on exactly computing the eigenvalues of the neural tangent kernel. It is also an important direction weaken the requirement on over wver-paramtterzattion or study the spectral bias in a non-NTK regime to furthur close the gap between theory and practice.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
ALLEN-ZHU, Z.., LI, Y. and SONG, Z. (2018). A convergence theory for deep learning via over- paramcterization. arXiv preprint arXiv:1811.03962
ANDONI, A., PANIGRAHY, R., VALIANT, G. and ZHANG, L. (2014). Learning polynomials with neural networks. International Conference on Machine Learning.
ARORA, S., DU, S. S., HU, W., LI, Z., SALAKIUTDINOY, R. and WANG, R. (2019a). On exact computation with infinitely wide neural net. arXiv preprint 1rXiv:1904.11955
ARORA, S., Du, S. S., HU, W., LI, Z. and WANG, R. (2019b). Fine-graiee Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:1901.08844
ATKINSON, K. and HAN, W. (2012). Spherical harmonics and approximations on the unit sphere: an introduction, vol. 2044. Springer Science & Business Media.
BACH, F. (2017). Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research 18 1-53.
BASRI, R., JACORS, D., KASTEN, Y. and KRITCHMAN, S. (2019). The convergence rate of neural networks for learned functions of different frequencies. arXiv preprint arXiv:1906.00440
BIETTI, A. and MAIRAL, J. (2019). On the inductive bias of neural tangent kernlss. arXiv preprint arXiv:I905. 12173.
CAO, Y. and Gu, Q. (2019a). Generalization bounds stochastic gradient descent for wide and deep neural networks. arXiv preprint 13X1v:190..13210.
CAO, and GU, Q. (2019b). A generalization theory of gradient descent for learning over- parameterized deep relu networks. arXiv preprint 10Xiv:190.001330
CHIZAT, L. and BACH, F. (2018). A note lazy training in supervised differentiable programming. arXiv preprint ar arXiv: 182.0799..
CHO, Y. and SAUL. L. K. (2009). Kernel methods for deep learning. In Advances in neural information processing systems.
COLLOBERT, R. and WESTON, J. (2008). unified architecture natural language processing: Deep neural networks with multitask learning. In Proceedings of the 25th international confer- ence on Machine learning. ACM.
DU, S. S., LEE, J. D., LI, H., WANG, L. and ZHAI, X. (2018a). Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv:1811.03800
DU, S. S., ZIAI, X., Poczos, B. and SINGHI A. (2018b). Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02055
FRYE, C. and EFTIIMIOU, C. J. (2012). Spherical harmonics in dimensions. arXiv preprint 1rX5v:1205.3548.
GUNASEKAR, S., LEF, J., SOUDRY, D. and SREBRO, N. (2018a). Characterizing implicit bias in terms of optimization geometry. arXiv preprint arXiv:1802.08244
GUNASEKAR, S., LEF, J., SOUDRY, D. and SREBRO, N. (2018b). Implicit bias gradient descent linear convolutional networks. arXiv preprint / 00468.
HE, K., ZHANG, X., REN, S. and SUN, J. (2015). Delving deep into rectifiers: Surpassing human- level performance imagenet classification. In Proceedings of the IEEE international confer- ence on computer vision.
HE, K., ZHANG, X., REN, S. and SUN, J. (2016). Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition.

---

Under review as a conference paper at ICLR 2020
HINTON, G., DENG, L., YU, D., DAHL, G., MOHAMED, A.-R., JAITLY, N., SENIOR, A., VAN- HOUCKE, V., NGUYEN, P., KINGSBURY, B. ET AL. (2012). Deep neural networks for acoustic modeling in speech recognition. IEEE Signal processing magazine 29.
JACOT, A., GABRIEL, F. and HONGLER, C. (2018). Neural langent kernel: Convergence and generalization in neural networks. arXiv preprini arXiv: 180::0077777
LI, Y. and LIANG, Y. (2018). Learning overparameterized neural networks via stochastic gradient descent on structured data, arXiv preprint /8088.8008... 0/204.
NAKKIRAN, P., KAPLUN, G., KALIMERIS, D.. YANG, T., EDELMAN, B. L., ZHANG, F. and BARAK, B. (2019). Sgd neural networks learns functions of increasing complexity. arXiv preprint 1905.
RAHAMAN, N.. BARATIN, A., ARPIT, D., DRAXLER, F., LIN, M., HAMPRECHT, F. A., BEN- GIO, Y. and COURVILLE, A. (2018). On the spectral bias of neural networks. arXiv preprint arXiv:1806.08734
ROSASCO, L.,, BELKIN, M. and VITO, E. D. (2010). On learning with integral operators. Journal of Machine Learning Research 11 905-934.
SMALE, S. and ZHOU, D.-X. (2007). Learning theory estimates via integral operators and their approximations. Constructive approximation 26 153-172.
SMALE, S. and ZhOU, D.-X. (2009). Geometry on probability spaces. Constructive Approximation 30 311.
SOUDRY, D., HOFFER, E. and SREBRO, N. (2017). The implicit bias of gradient descent on sepa- rable data, arXiv preprint arXiv: 10345.
SU, L. and YANG, P. (2019). On learning perrpparamtterized neural networks: A functional ap- proximation prospective. arXiv preprint
VEMPALA, S. and WILMES, J. (2018). Gradient descent for one-hidden-llyer neural networks: Polynomial convergence and sq lower bounds. arXiv preprint
Wu, X., DU, S. S. and WARD, R. (2019). Global convergence of adaptive gradient methods for an over-parameterized neural network. arXiv preprint D.XXvv19002077
XU, Z. J. (2018). Understanding training and generalization deep learning by fourier analysis. arXiv preprint arXiv: 1008.04889499
YANG, G. and SALMAN, H. (2019). A fine-grained spectral perspective neural networks. arXiv preprint urXiv:1907.10599
ZHANG, C., BENGIO, S., HARDT, M., RECHT, B. and VINYALS, O. (2016). Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 161 1.03530.
ZhOO, D., TANG, Y., YANG, Z., CAO, Y. and Gu, Q. (2018). On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint 17X1v.1808.0567.
Zou, D., CAO, Y., ZHOU, D. and GU, Q. (2018). Stochastic gradient descent optimizes over- parameterized deep relu networks. arXiv preprint arXiv: 1811888888.
Zou, D. and GU, Q. (2019). An improved analysis of training over-parameterized deep neural networks. arXiv preprint arXiv: / 04688.
10

---

Under review as a conference paper at ICLR 2020
A REVIEW ON SPHERICAL HARMONICS
In this section, we give brief review relevant concepts in spherical harmonics. For more detials, see Bach (2017), Bietti and Mairal (2019), Frye and Efthimiou (2012) and Atkinson and Han (2012)
for references.
We consider the unit sphere s = {x e Rd+1 ||x|| = 13, whose surface area is given by wa = 2x (d++1) / 1)/2) and denote Ta the uniform measure the sphere.
For
any
1, we consider a set of spherical harmonics They form an orthonormal basis and dizōsk. Moreover, since
YKU S - EIj satisfy the following equation (Yus, Yaj Saw they are homogeneous functions of degree k, it is clear that (x)) has the same parity k.
< -
kd, 2k+d-1 (
We have the addition formula
(d..) Σ
(x)(x) ((d.))P
(A.1)
where (t) is the Legendre polynomial of degree i in d + dimensions, explicitly given by (Ro- drigues' formula)
Pa(1) = (-1) [ T [(k+ (1-
dt - (1))
We also see that P&((), the Legendre polynomial of degree l: shares the same parity with k. By the orthogonality and the addition formula (A.1) I) we have,
[
6gk Px((x,,))
(ww.
(A.2)
N(d, k))
Further we have the recurrence relation for the Legendre polynomials,
k
k d-
(Pa())
2k + d Pk- (1)
2k + d Pa+1(1)
(A.3)
for k > 1 and tPo(f) = Pt(t) for k = 0. The Hecke-Funk formula is given for a spherical harmonic Yy of degree k
[( x))x d(y) - [
(()) - -ty(d- (2yld-2)/2
2t.
wi
B PROOF OF MAIN THEOREMS
B.1 PROOF OF THEOREM 3.2
In this section we give the proof of Theorem 3.2. The core idea of our proof is to establish connec- tions between neural network gradients throughout training and the neural tangent kernel. To do we first introduce the following definitions and notations.
(n (;)x lim x K ( Let (A d > ... > An be the eigenvalues of n 'K and vi...., v be the corresponding eigenvectors. Set V., (......,,, v..), V- (Pruti,..., Vn))
Define K
m (VV (x:), Vw fwos (x,)))xxm
K(x))
For notation simplicity, we denote Wwfwo [Vw, (x)]wxxxllwwwwrrr)
(Vw w= Ww,
1,2.
The following lemma is direct application of Proposition in Smale and Zhou (2009) Proposi- tion 10 Rosasco et al. (2010). bounds the difference between the eigenvalues NTK and their width counterparts.
11

---

Under review as a conference paper at ICLR 2020
Lemma B.1. For any 8 > 0, with probability at least 6,
[ - X & ((v1og(1/0)/m))
The following lemma is partly summarized from the proof of equation (44) in Su and Yang (2019). Its purpsse is to further connect the eigenfunctions of NTK with their finite-width, knite-sampll counterparts.
Lemma B.2. Suppose that [xx(x) M for all x 84, There exist absolute constants C, C", d" 0, such that for any 8 >> 0 and integer k with Ta & n, if d C(rr, Ar++1)= 2 log((10), then with probability least 1 5,
(og(1/0)
IV I C²
Arz- An+1
VV - - Vi & Ct
1
log 1//)
+ M Mrr
log(rk/00 (r)
drz -
The following two lemmas are key to characterize the dynamics of the residual throughout training. These results, especially Lemma B.4, are the ones that distinguish our analysis from previous works on neural network training in the NTK regime (Du et al., 201 8b; Su and Yang, 2019), since our analysis provides more careful characterization on the residual along different directions.
Lemma B.3. Suppose that the iterates of gradient descent W(O) W()) are inside the ball B(W("), w). If & O(Ioo((m)] 3/2), then with probability at least - On²)) expl-S(me22/3))
((((+1)) [I (1mm0² /n) (
((()) + e()), /|ee < 1(w byy -s((t)
for all L' 00=0, 0.....,-- 1, where y = Vn) 8(()) = 0- (Uwi") (wass
Lemma B.4. Suppose that the iterates of gradient descent W(O), ,..., W()) are inside the ball
B((()), w.) If w & [(min([log(m)] -3/2 A3 (1m))-9) and e Ö(A,²) then with probability
at least 1 - ot??n?? expp-S(mmw22))
Ty - )(1 < (((+2) T - (10)) )| I'- mmm0 Vn. O(-
(B.1)
V.. (y - ((0)))2 < (1 - mmd \r /2) VT_ (y - -0(0) )|2 + + 2/13 mm)2
vn Ö(1 + ww))
+ + 0(w ( (y - ((0))]12
(B.2)
ly 1y-5 < Ō(vn) (1 pmo X,, / 2)) + ÖÖVn. (ymo² \rr)
+ - - 1/3 vn. 0(1 + w/m
(B.3)
for all L' = 0
Now we are ready to prove Theorem 3.2.
Proof of Theorem 3.2. Define w = CT/(Dr, mm) for some small enough absolute constant C. Then by union bound, as long as m t R(poly ---,,--)) the conditions on w given in Lem- mas D.2, D.4, D.5, B.3 and B.4 are all satisfied.
We first show that all the iterates (0() result by inductively show that W()) B(W(0) _w), = 0, ..... T. First of all, it is clear that ( B B(W(0),u) w). Suppose that (()) (!)) ((((0) w). Then the results of Lemmas D.2, D.4,
(T) are inside the ball B(W()) w). We prove this
12

---

Under review as a conference paper at ICLR 2020
D.5, B.3 and B.4 hold for W()) W Denote u = = = --(()) te T. Then we have
| [++1)
00
('+1)) w
1
n
(y: 0 fwis (x:)) O- Vw,
1
71
11
|i 0. swie (xx)) Vw: (x:)l
1
P=0
C m
Σ y 0. (xi)l
< CinDO m/n
ly (20)
M=0
where the second inequality follows by Lemma D.4. By Lemma B.4, we have
Σ l 1000 < Ö(Vn//mm00 )rr)) + HOT OOTVn/(mm// )rx)) Xx 13
1/3 Vn- Ō(1 + wym).
then follows by the choice w = (0 vm), 17 Ō((m0 ). 0 Ō(e) and the assumption m > (poly(TT, X, that |w(++)) w & w, 1 = 1.2. Therefore by induction, we see that with probability at least (0( W(O). ..... W(T) B(W("), w).
Applying Lemma B.4 then gives
n 1/2 VV (y - ((T))2 & (1 - mym0² Are /2) n 1/2 IVT - -
ra
+ Tx w mmQ² 0(1 wvm
+ x=o ((w\/3) n 112 [[( TTy-))( (y - -210))22
Now by = (Ar 17 ((02m) and the assumption that m > m = -(1=114 6 )0-),
we obtain
n 1/2, [ rq. (y - -2 <
n 1/2. [V (y - 8(00 + e/16.
(B.4)
By Lemma 3.1, 0- = Ö(e) and the assumptions > (m (Amr d ) the
eigenvalues of VT. Vr, are all between 1/v2 and v2. Therefore by Lemma B.2 we have
V.. (y- 5 Vr VT (y -2(
Vr. V r (y- ((7))22 1(Vr V
V., Vy - S(T))l2
log (og(1/5) + Mrk
log(rk/0 /8)
V (y- 3(T))l2/V2 - -n. 0
Arz -rr+11
VV (y - ((T))12/V22 1/lll//2-///16..6
Similarly,
V - 5/ < v2. IV (y 12 E//7/6
2- VV yl1 + V2- V2, 5000 12 + evni16.
By Lemma 3.1, with probability least 1- 8. V 2 1 Mr V /log(rr/0)/m Combining this result with Lemma D.3 gives VVTT3(00)) < 00 (v n log (n/0)) < n/8. Plugging the above estimates into (B.4) gives
1/2 vy 2 1011-~n2)" n 1/2 V tc.
Applying union bounds completes the proof.
13

---

Under review as a conference paper at ICLR 2020
B.2 PROOF OF THE THEOREM 3.4
Proof of the Theorem 3.4. The idea of the proof is close to that of Proposition 5 in (Bietti and Mairal, 2019) where they consider > and we present a more general case including k >> and > For any function gd R, by denoting (0(x)
IS 9y )dT((y), it can be decomposed as
N(LA)
g(x)= Σ [x(x)) Σ
Σ
kd,
(B.5)
where we project function g to spherical harmonics in the second equality and apply the addition equation in the last equality. For positive-definite dot-product kernel n(x, x') sd x S - IR which has the form x(x, x') = (x)x for R [--, 1] - I. we can present decomposition by (B.5) if we consider g(x)
ol x, 2 for z E Sd and Φ [-1,
x(x,x)) Σ (dd,k) k))
x() (X)x))))aaT
8
S -1
(dd k))
- Pa (xx
wi
where we apply the Hecke- Funk formula and addition formula. By denoting A = (wa-1/wa) 1"1 (1)) - 2)/2 dt and the addition formula, we have
N(p.)
x(x,x') Σ ps (a,
(x)(x)V
(B.6)
This formula (B.6) is the Mercer decomposition for the kernel function s(x, x') and μe is exactly the eigenvalue of the integral operator LK on L2(S4) defined by
La(s))y) = J3d
x(x, (x)(xxx)((), S L2(%)
By using same technique as x(x, x),, can derive similar expression for o(ww,)) x)) max {(w, x), 0} and o' d'(ww))) I((w,x) > 0}, since they are essentially dot-product func- tion on L2 (Sd). We deliver the expression below without presenting proofs.
d' d'(w,
N k)) Px((w,,
(B.7)
o(w,x)) Σ B2 (dd
(B.8)
where 31 (wa-1/wa) (())(())))))))))))) 21/2 and B2 = (wa-1/wa) 12 (1)
(2) (2 We add more comments on the values of 31.x and 32 It has been pointed out in Bach (2017) that when > a and when i and a have same parity, we have 3a-1,A 0. This because the Legendre polynomial (t( is orthogonal to any other polynomials of degree less than & with respect to the density function p(t) (1 (2dd-2)/2 Then we clearly know that B1.x 0 for = 2j and 82, for 2j + with j E N
For two kernel function defined in (2.2), we have
Ny xx(xx x')
F N(o.) x)) (ww,)))
Ew-NN [o'((w/li) |w| (w))(((//lll))xxx)))
[ o'((v, ((Vx ( (v,x)))dra("
(B.9)
14

---

Under review as a conference paper at ICLR 2020
The first equality holds because o' is 0-homogeneous function and the second equality is true since the normalized direction of a multivariate Gaussian random variable satisfies uniform distribution on the unit sphere. Similarly can derive
x²(x,x')
(d + 1) 3d
o((v, o((v,x))o (V) (v)))))a
(B.10)
By combing (A.2), (B.7), (B.8), (B.9) and (B.10), we can get
<1(x,x') = Σ ((N.)()))))(((x)))))
(B.11)
k=0
and
S0
x2(x,x) = (d + 1) Σ k-0
(d.
(B.12)
Comparing (B.6). (B.11) and (B.12), we can easily show that
P1. f and 12, (d + 1)
(B.13)
In Bach (2017), explicit expressions for 31,x and 32,k for le 2 a + are presented by
d a-la((-1))
all (1-1 1-0
[(d/2)
1,+
2x
2
( I ttdtatl
By Stirling formula [(x) 2 x 1/2 e- /2T, we have following expression of Bat1,k for k > a+
(d 1)d (k- aa
Ba+1. C(as)
Ω d -
(k: عوي
(k a 1) T (k: + d + 1
I
where C(a)
Laal expla + 1}.
Also Bo+1.0
BI.1
d-1 (()(())
d-1 and $2 2da
Thus combine (B.13) know that Patlk
4nd T
Ω (d k + d) d By considering (A.3) and (B.6), we have
Po 11,1 + 2/12.0.
= 0, = 2j + 1, JEN
and
K
A d 1 2k + d M1 2,2
A4 2k + 111
for k > 1 and l of W. From the discussion above, we thus know exactly that for k 2
P Ω (max (d k-
1 (k: d) k-d -
& - dd-22 2(k + d) k x-d-1]).
This finishes the proof.
B.3 PROOF OF THE COROLLARIES 3.7 AND 3.8
Proof of the Corollaries 3.7 and 3.8. We only need to bound (6)(x) for j E [rx] to finish the proof. Since now assume input data follows uniform distribution the unit sphere Sd, (y(x)) would be spherical harmonics order at most for j e [rx]. For any spherical harmonics Y, of order & and any point on gd, we have an upper bound (Proposition 4.16 in Frye and Efthimiou (2012))
[x((x)] < (N(d,K) k) { xf(y)dra(x))
Thus we know that (x) & (N(dkk). For & >> d, we have ((d,k) 2 ( Oldd-1). For d vo k we have ((d,k) k) 2k+d (k+d-2) O(dt). This completes the proof. 1
15

---

Under review as a conference paper at ICLR 2020
C PROOF OF TECHNICAL LEMMAS
C.I PROOF OF LEMMA B.2
Proof of Lemma B.2. The first inequality directly follows by equation (44) in Su and Yang (2019).
To prove the second bound, we write Vr = rv A
V TA B, where A E R **k, B (((=r))xxr
Let ć C²(rr, -r VVoooo//)///// &2 C"" M log(rx/0), //0/// be the bounds given in the first inequality and Lemma 3.1. By the first inequality, we have
B F
B
V V. Ia
Moreover, since V V = A A + B B, by Lemma 3.1 we have
|AA - 1|2 = A A
1l2 V Vr 1|2 + |B
rx52 5
Therefore
IV V
1
7
I AA AA VT + V AB (V.) V BATV, +
V BB (V. - Vn, VT
(AA -IV ru 2
(AA
JAAT - 112 2)
O(riE2 +11)
Plugging in the definition of & and Eg completes the proof.
C.2 PROOF OF LEMMA B.3
Proof of Lemma B.3. The gradient descent update formula gives
20 Σ yys
W(++1) W(t) +
Ofwro (x:)) 0V Ow (w.owx(...).
(C.1)
For any j E [n]. subtracting (!!) and applying inner product with (V on both sides gives
(Vw/wwi(x))) ((++)) w(l) 2n02
2 (yr - 11 (X,), (x/w)(xx)).
Further rearranging terms then gives
Uj -(((+1)) y; - -()()), 2
U/ Ofwco K?, Jigh I2 + Tajj
(C.2)
where
21182
h1s Σ (vi Ow KV w wx)) www.://wwww/.w../.....o//.... - 1m
12,5. 21
n
Σ (y: (x:cco(x)) (K!)) -K?3),
Is. = 0- [xwaen - (wro())) (Vw.wWWwww w(+)))++))))))) - -W(S)]
For I2,j,, by Lemma D.6, we have
n
Misal & 2/3 1132131m003))
Of (x:) O3w mm=0") 1y -
12/V 1/
16

---

Under review as a conference paper at ICLR 2020
For 12,5,e by Bernstein inequality and union bound, with probability at least 1 - O(n²) exp( (S1(mm2)3))) we have
with probability at least 1 - O(n) (an)))xppl-aa)
[K] kl < (13)/3)
for all ز e [n]. Therefore
1 112 & O(w mml²)
11 (fwwo(x)) & O0w")(10000) 15-551012 12/VV. 11
For 13,j,, we have
Is x O(w2/3 /
|| (t+ w
1(w /mf)-
2n y; 0fwro .. (x))l2
1=1
< 16 1/3 (0mm2))
1
Σ
|i4 (x))
x mm62) mm00))
Ily 1l//i
where the first inequality follows by Lemmas D.2, the second inequality is obtained from (C.1), and the third inequality follows by Lemma D.4. Setting the j-th entry of e as I [1g + f2.j + 13.j. and writing (C.2) into matrix form completes the proof.
C.3 PROOF OF LEMMA B.4
Proof of Lemma B.4. Denote u (1) y - -()), 1 T. Then we have
(((=))
11 Tn(
[I (1m10²) /n) K 20 Iu ( +
|n(0)//2
1l2 + ((w 1/3
mm00) /300)mmmm))))
vn. Õ(1 + wvm),
where the first inequality follows by Lemma B.3, and the second inequality follows by Lemma D.5.
Therefore we have
II
(0) 2 l' w mm000 Vn. 5(1 + @v1+,
for 1' = ..... This completes the proof of IB. Similarly, we have
VT (()++))
2 V ri [ - (1m6² /n) K
1|2 (w mm0d)) -I
< (1 m Sr,)) T
2 + Ō 13 mmmd) (1) (T
r2 (()) 122 + TT
$ (1 mmnd Xr./ 2) rh
12 2 . 11 ((())) ( [n 12
rh
< (1 mmma \r, /2
VT
+ t- (w mm02) (w v Õ(1 + wmm
+ mmm)))))))) ((
(0)
for t' = 0,... t - 1, where the third inequality is by Lemma B.1 and the assumption that w &
8(22, ). > o(>,,). and the fourth inequality is by (B.1). Therefore we have
VT. u 10) 2|2 (1 >mmar /2) VT u (0) ||2 t'. (ym6² 2n./2)-1 (w//3mmm0y vn. 001 wvm
+ (nmo²² /2) 1 Ō ( 1/3
mm0²) (m00))m0))))))))))))mm))))))))
1(V=) " (0) 22
(1 nmn >,T//2 2) V (0)
t'1,,t 2/3 mmof. vn. Ō(1 + wym
TM
+ 1 0(wl13) -1| [ F2)
J (0) 12
< (1 m >,, VT u (0)
2 + l' A w/
vn. 01 ww/
+ X,1 Ö(wl/3) || ( Tu (0)2
17

---

Under review as a conference paper at ICLR 2020
This completes the proof of (B.2). Finally, for (B.3), by assumption have 1/ mmm02 Ō(1) Therefore
+1)
2 < || (ymm)) K J r V r (e)) 1a ||I
(1/10² /m
K
1000/2
+
IV. u 12 Ō mmm)²) ((V+
22
12
< (1 - mmm
(01 2 + Ō(w 1/3 mmn0")
0(1) 1( "
re
< mmm Ar. 2)
( (00 + Õ(1) 11 (((
T 11
F2
& (1 1mm X,, /2) (12 + 0(1) II r%
101l ll2 + I'w 1/ "m Vn- Ö( wym
for t' 0,.... ,,... 1, where the third inequality is by Lemma B.1 and the assumption that & Ö(A2,) ). and the fourth inequality follows by (B.1). Therefore we have [u O(vn). (1 -ymme Xra/))" O((mm0())p )t) (.) ( 12 A/ Vn Ö(1 + wv/)..
This finishes the proof.
u
D AUXILIARY LEMMAS
In this section we list several auxiliary lemmas on the properties of weer-parameterized neural net- works we need in our proof Theorem 3.2. These results are mostly summarized from Allen-Zhu et al. (2018) and Cao and Gu (2019a).
D.1 AUXILIARY LEMMAS
Denote
D; = diag [[((Wxx)) > ( > +]),
D diag( | (0) x,11 > O)..... ... 1[( x²)m > 0}).
Lemma D.1 (Allen-Zhu Zhu et al. (2018)). If w & [[llg(mm]] -3/2), then with probability at least 1 O(n) expl 20mpp
D. D 10) $ m
for all W (( ()), [n].
Lemma D.2 (Cao and Gu (2019a)). There exists an absolute constant x such that, with probability
at least - (nn) exp[-[Q(mw=+) over the randomness of W for all i e [n] and W, W B(W B(W(") ( with w & k[log(m))) 33/2, it holds uniformly that
(x,) (x,) ( (x,), W - W) & 0 o( 1/3 log(m) |
W l1.
Lemma D.3 (Cao and Gu (2019a)). For any 5 > 0, if m Clog(n/8) for large enough absolute | (a:)) & (lg(n/8)) for all i e [m]. Lemma D.4 (Cao and Gu (2019a)). There exists an absolute constant such that, with probability at least - (n)) exp[_[((m=?())) for all i [n]. I [4] and W e B(W("),, w) with w <
constant C, then with probability at least
C'Ilog(m)] -3 it holds uniformly that [w:)fw(x)) Olvm).
The following lemma provides a uniform bound of the neural network function value over ((W(0), ,w).
Lemma D.5. Suppose that m > aiw 1og(//1) and ~ & ((log(m))--) Then with probabil- log(n/))) ity at least - 6. (x;) < O((llog(n/8) + w/m) for all W E B(W(()) w) i [n]]
Lemma D.6. I & (1lo(m))) 3/2). then with probability at least - O(n) expl 2/3w)
/w,/w(x) Vw/ww/ (x:) & 2/3 (/)))))
(x,) -Nw.ww//))-/wwwwwoollloo Vwfwoo (x,)) < (33)33m)
for all W (0)()) (w) and i [n].
18

---

Under review as a conference paper at ICLR 2020
D.2 PROOFS OF LEMMAS D.5 AND D.6
Proof of Lemma D.5. By Lemmas D.2 and D.4, we have
(xw( (x:o)())) < (wo.
w \W::/wo 2
V log(m)) |W1 w
Oww/m),
where the last inequality is by the assumption & [log(m)] -3 Applying triangle inequality and Lemma D.3 then gives
[fw(x)) & (w [fw(x;) [wilo: O(ylog(n/8) + O(wvm)
O(y Ololog((/0) wym),
This completes the proof.
Proof of Lemma D.6. By direct calculation, have
Sw, (x.) = vm
x, Vw, - - D, W,W
Therefore we have
/w,,/w(x)) Vw, (wi:/o)
Vm. D D.W. x - D W x
Vm WWW,D, D; x; w D (0)
P
vm W.D, W 2 D (0)
F
v m (0) (D( D.jl + vm (w W;)
By Lemma 7.4 in Allen-Zhu al. (2018) and Lemma D.I, with probability at least
exp[-Q(m)}, ym- [ (D. (0) - D.)lIF & ((w1/3mm) for all i E [n]. Moreover, clearly
[( Dz P W W2/r & w. Therefore
VW fw( fwi (x)))ll & (()))//m)))
for all i E [n]. This proves the bound for the first layer gradients. For the second layer gradients, have
fwo (x;) /mm [o( xT Vw,fw(x,) = smm Com.oo(Wie [oxx)))
It therefore follows by the 1-Lipschitz continuity of (-) that
[w.fw(x;) Vw.fwoo (x:)]le & /m- || x wwm & w3/3/mm
This completes the proof of the first inequality.
The second inequality directly follows by triangle inequality and Lemma D.4:
KVwfw Vw.w fw,w(xx)) mk (0) & V Ww/wxx) - V Wwfwo (xx), V (wx:)
KVwSwoo Vw/w(xx)) Wwfwio (x;)
(3)
This finishes the proof.
E
ADDITIONAL EXPERIMENTAL RESULTS
E. ESTIMATING THE PROJECTION LENGTHI IN FUNCTION SPACE
As mentioned in Section 4.1, when using freshly sampled points, we are actually estimating the projection length of residual function r(x) f (x) fo (x) onto the given Gegenbauer poly- nomial P& (x). Here we present in Figure 3 a comparison between the projection length using train-
ing data and that using test data. An interesting phenomenon is that the network generalizes well
19

---

Under review as a conference paper at ICLR 2020
on the lower-order Gegenbauer polynomial and along the highest-order Gegenbauer polynomial the network suffers overfitting.
(x) 1P((z) (2(2) + (2)
f(x)
(P)(z) + 1P)(2) (P)(z)
12
k=1
projection length āx
km2
projection length ax
k=2
k=4
k=4
08
0.-
04
00-
0.0
2500
5000
75.00
10000
12503
15200
17500
20000
2500
5000
10000
12500
15200
17500
20000
step
step
(a) projection onto training data
(b) projection onto test data
((x) = 1P (2))) (1))))
[((x) (P) 3P(() + 5P
k=1
k=1
projection length år
k=2
k=2
k=4
projection length
k=4
3-
2500
5000
75:00
10000
12500
15000
17520
20303
0
2505
5000
75:0
10000
12500
15000
17520
20003
step
step
(c) projection onto training data
(d) projection onto test data
Figure 3: Convergence curve projection length onto vectors (determined by training data) and functions (estimated by test data). We that for low-order Gegenbauer polynomials, the network lears the function while for the high-order Gegenbauer polynomial, the network overfits the training data.
E.2 NEAR-LINEAR CONVERGENCE BEHAVIOR
In this subsection, we present the same curve shown in Section 4.1 in logarithmic scale instead of linear scale. As shown in Figure we can see that the convergence of different projection length close linear convergence, which is well-aligned with our theorem. Note that performed moving average of range 20 on these curves to avoid the heavy oscillation especially in late stage.
20

---

Under review as a conference paper at ICLR 2020
[xx) (P(()) + (P(() + (P(())
[() 1P(()) 3P 5P(())
10
k=1
projection length āx
k=2
k=2
101
k=4
projection length
k=4
10-
2
10
109
10-4
30
10
10-4
10-
2500
5000
1500
10000
12500
15000
17500
20620
2500
5000
7550
10000
12500
15200 17500 20000
step t
step
(a) components with the same scale
(b) components with different scale
Figure 4: Log-scale convergence curve for projection length onto different component. (a) shows the curve when the target function have different component with the same scale. (b) shows the curve when the higner-order components have larger scale. Both exhibit nearly linear convergence especially at late stage.
21


Reviews:
[{"review_id": "SJlRf3oiKS", "reviewer": "AnonReviewer3", "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": "The paper aims to provide theoretical justification for a \"spectral bias\" that is observed in training of neural networks: a phenomenon recorded in literature (Rahaman et al.), where lower frequency components of a signal are fit faster than higher frequency ones. The contributions of the paper are as follows:\n1. Proves an upper bound on the rate of convergence on the residual error projected on top few eigenfunctions (of a certain integral operator). The upper bound is in terms of the eigenvalues of the corresponding eigenfunctions and is distribution independent.\n2. Provides an upper bound on the decay of eigenvalues in the case of depth-2 ReLU networks and also a exact characterization of the eigenfunctions. While such upper bounds and the characterization of eigenfunctions existed in literature earlier, it is argued that the new bounds are better.\n3. Combining the above two results, a justification is obtained for the \"spectral bias\" phenomenon that is recorded in literature.\n4. Some toy experiments are provided to exhibit the spectral bias phenomenon.\n\nRecommendation:\nI recommend \"weak acceptance\". The paper takes a step towards explaining the phenomenon of spectral bias in deep learning. While concrete progress is made in the context of depth-2 ReLU networks (even though in NTK regime), perhaps the ideas could be extended to deeper networks.\n\nTechnical comments:\n- It is argued that the new bound of $O(\\mathrm{min}(k^{-d-1}, d^{-k+1}))$ is better than the bound of $O(k^{-d-1})$ from the previous work of Bietti and Mairal, in the regime where $d \\gg k$. I think there is a typo here. In the regime of $d \\gg k$, the bound $k^{-d-1}$ is the smaller one so both bounds are comparable. It is argued that $d \\gg k$ is the more relevant regime, but then there isn't any improvement here.\n- The proof of spectral analysis is said to follow a similar outline as compared to the prior work of Bietti-Mairal, but it is not clear to me where this new proof deviates and improves on prior techniques? Or is it just a more careful analysis of the prior techniques?\n- The proof operates in the \"Neural Tangent Kernel\" regime, by considering hugely overparameterized networks. This can be viewed as a negative thing, but then, most results in literature also operate in this regime and it is a major challenge for the field to prove results in the mildly overparameterized / non-NTK regime!\n\nPotential suggestions for improvement:\n- In Section 4: the y-axis of the graph is labeled \"error's coefficient\" which is non-informative. Is it $|a_k - \\hat{a}_k|$ ? I also had a question here about the proposed Nystrom method: Why is it okay to use the training points in the Nystrom method. Ideally, we should use freshly sampled points. Is there a justification for using the training points? If not, perhaps it is best to go with freshly sampled points.\n- I felt the proofs in the Appendix are very opaque and it is hard to pinpoint what the new insight is (at least for a reader, like me, who does not have an in-depth familiarity with these convergence proofs).\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "S1e1WhjGFr", "reviewer": "AnonReviewer2", "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": "This paper studies the training of overparametrized neural networks by gradient descent. More precisely, the authors consider the neural tangent regime (NTK regime). That is, the weights are chosen sufficiently large and the neural network is sufficiently overparametrized. It has been observed that in this scenario, the neural network behaves approximately like a linear function of its weights.\n\nIn this regime, the authors show that, the directions corresponding to larger eigenvalues of the neural tangent kernel are learned first. As this corresponds to learning lower-degree polynomials first, the authors claim that this explains the \"spectral bias\" observed in previous papers.\n\n-I think that from a mathematical point of view, the main result of this paper is what one would expect intuitively: \nWhen performing gradient descent with quadratic loss where the function to be learnt is linear, it is common knowledge that convergence is faster on directions corresponding to larger singular values. Since in the NTK regime, the neural network can be approximated by a linear function around the initialization one expects the behavior predicted by the main results. From a theoretical perspective, I see the main contribution of the paper as making this statement precise.\n\n-I am skeptical about some of the implications for practitioners, which are given by the authors: \nFor example, on p.5 the authors write \"Therefore, Theorem 3.2 theoretically explains the empirical observations given in Rahaman et al. (2018), and demonstrates that the difficulty of a function to be learned by neural network should be studied in the eigenspace of neural tangent kernel.\" To the best of my knowledge, it is unclear whether practitioners train neural networks in the NTK regime (see, e.g., [1]). Moreover, I am wondering whether some of the assumptions of their theorem are really met in practice. For example, the required sample size for higher order polynomials grows exponentially fast with the order and the required step size goes to zero exponentially fast. Does this really correspond to what is observed in practice? (Or is this a mere artifact of training in the NTK regime?)  Is this what one observes in the experiments by Ramahan?\n\nI think the paper is not yet ready for being published.\n 1. There are many typos. Here is an (very incomplete) list.\n    -p. 2: \"Su and Yang (2019)\" improves the convergence...\"\n    -p. 2: \"This theorem gives finer-grained control on error term's\"\n    -p. 2: \"We present a more general results\"\n    -p. 4: \"The variance follows the principal...\"\n    -p. 4: \"...we will present Mercer decomposition in (the) next section.\"\n2. I think that the presentation can be polished and many statements are somewhat unclear. For example, on p. 7 the authors write \"the convergence rates [...] are exactly predicted by our theory in a qualitative sense.\"\n    The meaning of this sentence is unclear to me. Does that mean in a quantitative sense? To be honest, only considering Fig. 1 I am not able to assess whether the convergence rates of the different components are truly linear. \n\nI decided for my rating of the paper because of the following reasons:\n-I think that for a theory paper the results obtained by the authors are not enough, as they are rather direct consequences of the \"near-linearity\" of the neural network around the initialization.\n-In my view, there is a huge gap between current theoretical results for deep learning and practice. For this reason, it is not problematic for me that it is unclear, what the results in this paper mean for practitioners. (Apart from that, results for the NTK regime are interesting in its own right.) However, in my view, one should explain the limitations of the theory more carefully.\n-The presentation of the paper needs to be improved.\n\nReferences:\n[1] A note on lazy training in supervised differentiable programming. L Chizat, F Bach - arXiv preprint arXiv:1812.07956, 2018 \n\n\n\n-----------------------------\n\nI highly appreciate the authors' detailed response. However, I feel that the paper does not contain enough novelty to justify acceptance.\n\n------\n\"Equation (8) in Arora et al., (2019b) only provides a bound on the whole residual vector, i.e., , and therefore cannot show different convergence rates along different directions.\"\n\nWhen going through Section 4 , I think that it is implicitly stated that one has different convergence along different directions.\n-----\nFor this reason, I am not going to change my score.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of 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": "HJlZsUhVYS", "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": "I must qualify my review by stating that I am not an expert in kernel methods, and the mathematics in the proof is more advanced than I typically use. So it is possible that there are technical flaws to this work that I did not notice.\n\nThat being said, I found this to be quite an interesting paper. It provides a concise explanation for the types of features learned by ANNs: those that correspond to the largest eigenvalues of the kernel function. Because these typically correspond to the lowest-frequency components, this means that the ANNs tend to first learn the low frequency components of their target functions. This provides a nice explanation for how ANNs can both: a) have enough capacity to memorize random data; yet b) generalize fairly well in many tasks with structured input data. In the case of structured data, there are low frequency components that correspond to successfully generalized solutions.\n\nI have a few questions about the generality of this result, and its application to make better machine learning systems:\n\n1) As far as I can tell, the proof applies strictly vanilla SGD (algorithm 1). Would it be possible to extend this proof to other optimizers (say, ADAM)? That extension would help to connect this theory to the practical side of the field.\n\n2)  Given that the kernel depends on the loss function, and it's the eigenspectrum of the kernel's integrator operator that determines the convergence properties, can this work be applied to engineering better loss functions for practical applications? \n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose to understand spectral bias during training of neural networks from the perspective of the NTK. While reviewers appreciated aspects of the work, the general consensus was that the current version is not ready for publication; some concerns stem from whether the the NTK model and finite neural networks are sufficiently similar that we should be able to gain real practical insights into the behaviour of finite models. This is partly an empirical question, and stronger experiments are required to have a better sense of the answer. Nonetheless, the authors are encouraged to persist with this work, taking into account reviewer comments in future revisions.


Decision: Reject