Title: 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 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 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 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 sphere, and show that lower degree spherical harmonics are easier to be learned by over-parameterized neural networks.

1. INTRODUCTION:

Over-parameterized neural networks have achieved great success in many applications such as computer 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-parameterized neural networks can fit complicated target function or even randomly labeled data (Zhang et 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., 2018b; a) has made efforts in the perspective of "implicit bias", which states that training algorithms for deep learning implicitly pose an inductive bias onto the training process and lead to a solution with low complexity measured by certain norms in the parameter space of the neural network.

Among many attempts to 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 a 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 twolayer 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.

Meanwhile, a 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 show that under certain over-parameterized condition, the neural network trained by gradient descent 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 certain 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 a theoretical explanation for spectral bias. Under NTK regime, we establish a precise characterization for the training process of neural networks. More specifically, we theoretically prove that over-parameterized neural networks' training process can be controlled by the eigenvalues of the integrating operator defined by the NTK. Under the specific case of uniform distribution on unit sphere, we give an 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 we 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 over-parameterization 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.

2. We present a more general result about the spectra of the neural tangent kernel. In particular, we show that the order of eigenvalues appears as µ k " Ωpmaxtk ´d´1 , d ´k`1 uq. Our result is better than the bound Ωpk ´d´1 q derived in Bietti and Mairal (2019) when d " k, which is clearly a more practical setting.

3. We establish a 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 lowerfrequency components can be learned with less training examples and narrower networks with a faster convergence rate. As far as we know, this is the first attempt to give a comprehensive theory justifying the existence of spectral bias.

1.1. ADDITIONAL RELATED WORK:

Recently, there is a rich literature about the property of neural tangent kernel. Jacot et 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) (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 n and will eventually converge to 0. 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 psq :" ş S d κpx, sqf psqdτ psq where κp¨, ¨q is the NTK function and τ psq 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 proposed a harmonic decomposition for the functions in the reproducing kernel Hilbert space which we utilize in our proof. Based on the technique in Bach (2017) , Bietti and Mairal (2019) studied the eigenvalue decay of integrating operator L κ f pxq defined by NTK on unit sphere by using spheri-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 a two-layer networks with bias terms. Yang and Salman (2019) studied the the eigenvalues of integral operator with respect to the NTK on Boolean cube by Fourier analysis.

The rest of the paper is organized as follows. We state the notation, problem setup and other preliminaries 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.

2. PRELIMINARIES:

In this section we introduce the basic problem setup including the neural network structure and the training algorithm, as well as 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 a vector v " pv 1 , . . . , v d q T P R d and a number 1 ď p ă 8, we denote its p´norm by }v} p " p ř d i"1 |v i | p q 1{p . We also define infinity norm by }v} 8 " max i |v i |. For a matrix A " pA i,j q mˆn , we use }A} 0 to denote the number of non-zero entries of A, and use }A} F " p ř d i,j"1 A 2 i,j q 1{2 to denote its Frobenius norm. Let }A} p " max }v}pď1 }Av} p for p ě 1, and }A} max " max i,j |A i,j |. For two matrices A, B P R mˆn , we define xA, By " TrpA J Bq. We use A ľ B if A ´B is positive semi-definite. In addition, we define the asymptotic notations Op¨q, r Op¨q, Ωp¨q and r Ωp¨q as follows. Suppose that a n and b n be two sequences. We write a n " Opb n q if lim sup nÑ8 |a n {b n | ă 8, and a n " Ωpb n q if lim inf nÑ8 |a n {b n | ą 0. We use r Op¨q and r Ωp¨q to hide the logarithmic factors in Op¨q and Ωp¨q.

2.2. PROBLEM SETUP:

Here we introduce the basic problem setup. We consider two-layer fully connected neural networks of the form

f W pxq " ? m ¨W2 σpW 1 xq,

where W 1 P R mˆpd`1q , W 2 P R 1ˆm1 are the first and second layer weight matrices respectively, and σp¨q " maxt0, ¨u is the entry-wise ReLU activation function. The network is trained according to the square loss on n training examples S " tpx i , y i q : i P rnsu:

L S pWq " 1 n ÿ pxi,yiqPS py i ´θf W px i qq 2 ,

where θ is a small coefficient to control the effect of initialization, and the data inputs tx i u n i"1 is assumed to follow some unknown distribution τ on the unit sphere S d P R d`1 . Without loss of generality, we also assume that |y i | ď 1.

We first randomly initialize the parameters of the network, and then apply gradient descent to optimize both layers. We present our detailed neural network training algorithm in Algorithm 1.

Algorithm 1 GD for DNNs starting at Gaussian initialization Input: Number of iterations T , step size η. Generate each entry of W p0q 1 and W p0q 2 from N p0, 2{mq and N p0, 1{mq respectively. for t " 0, 1, . . . , T ´1 do Update W pt`1q " W ptq ´η ¨∇W L S pW ptq q. end for Output: W pT q .

The initialization scheme for W p0q given in Algorithm 1 is known as He initialization (He et 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 are chosen following the principle that the initialization does not change the magnitudes of inputs in each layer. The second layer parameter is not associated with the ReLU activation function, thus it is initialized with variance 1{m instead of 2{m.

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., 2018b; 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 to a limiting kernel, i.e., Neural Tangent Kernel (Jacot et al., 2018) . In this paper, we denote it by κpx, x 1 q " lim mÑ8 m ´1x∇ W f W p0q pxq, ∇ W f W p0q px 1 qy and we have κpx, x 1 q " xx, x 1 y ¨κ1 px, x 1 q `2 ¨κ2 px, x 1 q,

(2.1) where κ 1 px, x 1 q " E w"N p0,Iq rσ 1 pxw, xyqσ 1 pxw, x 1 yqs, κ 2 px, x 1 q " E w"N p0,Iq rσpxw, xyqσpxw, x 1 yqs.

(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 to 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

EQUATION

where t " xx, x 1 y{ p}x} }x 1 }q.

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. Let L 2 τ pXq be the Hilbert space of square-integrable functions with respect to a Borel measure τ from X Ñ R. For any continuous kernel function κ : X ˆX Ñ R and τ we can define an integral operator L κ on L 2 τ pXq by

L κ pf qpxq " ż X κpx, yqf pyqdτ pyq, x P X.

(2.4)

It 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 a sum of positive semi-definite kernels. Clearly this kernel is also continuous and symmetric. Thus we know that the neural tangent kernel κ is a Mercer kernel.

3. MAIN RESULTS:

In this section we present our main results. In Section 3.1, we give a general result on the convergence rate of gradient descent along different eigendirections of neural tangent kernel. Motivated by this result, in Section 3.2, we give a case study on the spectrum of L κ when the input data are uniformly distributed over the unit sphere S d . In Section 3.3, we combine the spectrum analysis with the general convergence result to give explicit convergence rate for uniformly distributed data on the unit sphere.

3.1. CONVERGENCE ANALYSIS OF GRADIENT DESCENT:

In this section we study the convergence of Algorithm 1. Instead of studying the standard convergence of loss function value, we aim to provide a refined analysis on the speed of convergence along different directions defined by the eigenfunctions of L κ . We first introduce the following definitions and notations.

Let tλ i u iě1 with λ 1 ě λ 2 ě ¨¨¨be the strictly positive eigenvalues of L κ , and φ 1 p¨q, φ 2 p¨q, . . . be the corresponding orthonormal eigenfunctions. Set v i " n ´1{2 pφ i px 1 q, . . . , φ i px n qq J , i " 1, 2, . . .. Note that L κ may have eigenvalues with multiplicities larger than 1 and λ i , i ě 1 are not distinct. Therefore for any integer k, we define r k as the sum of the multiplicities of the first k distinct eigenvalues of L κ . Define V r k " pv 1 , . . . , v r k q. By definition, v i , i P rr k s are rescaled restrictions of orthonormal functions in L 2 τ pS d q on the training examples. Therefore we can expect them to form a set of almost orthonomal bases in the vector space R n . The following lemma follows by standard concentration inequality. Lemma 3.1. Suppose that |φ i pxq| ď M for all x P S d and i P rr k s. For any δ ą 0, with probability at least 1 ´δ,

}V J r k V r k ´I} max ď CM 2 a logpr k {δq{n,

where C is an absolute constant.

Denote y " py 1 , . . . , y n q J and p y ptq " θ ¨pf W ptq px 1 q, . . . , f W ptq px n qq, t " 0, . . . , T . Then Lemma 3.1 shows that the convergence rate of }V J r k py ´p y ptq q} 2 roughly represents the speed gradient descent learns the components of the target function corresponding to the first r k eigenvalues. The following theorem gives the convergence guarantee of }V J r k py ´p y ptq q} 2 . Theorem 3.2. Suppose |φ j pxq| ď M for j P rr k s and x P S d . For any , δ ą 0 and integer k, if

n ě r Ωp ´2 ¨maxtpλ r k ´λr k `1q ´2, M 4 r 2 k uq, m ě r ΩppolypT, λ ´1 r k , ´1qq,

then with probability at least 1 ´δ, Algorithm 1 with η " r Oppmθ 2 q ´1q, θ " r Op q satisfies n ´1{2 ¨}V J r k py ´p y pT q q} 2 ď 2p1 ´λr k q T ¨n´1{2 ¨}V J r k y} 2 ` . 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 to smaller eigenvalues. Moreover, by showing that learning the components corresponding to larger eigenvalues 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 a 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 tangent kernel, then learning this function up to good accuracy takes longer time, and requires more examples and a wider network.

3.2. SPECTRAL ANALYSIS OF NEURAL TANGENT KERNEL FOR UNIFORM DISTRIBUTION:

After presenting a general theorem (without assumptions on data distribution) in the previous subsection, 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 analysis 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 1 P S d Ă R d`1 , we have the Mercer decomposition of the neural tangent kernel κ :

S d ˆSd Ñ R, κ `x, x 1 ˘" 8 ÿ k"0 µ k N pd,kq ÿ j"1 Y k,j pxq Y k,j `x1 ˘, (3.1)

where Y k,j for j " 1, ¨¨¨, N pd, kq are linearly independent spherical harmonics of degree k in d`1 variables with N pd, kq " 2k`d´1 k `k`d´2 d´1 ˘and orders of µ k are given by µ

0 " µ 1 " Ωp1q, µ k " 0, k " 2j `1, µ k " Ω `max d d`1 k k´1 pk `dq ´k´d , d d`1 k k pk `dq ´k´d´1 , d d`2 k k´2 pk `dq ´k´d´1 (˘, k " 2j,

where j P N `. More specifically, we have µ k " Ω `k´d´1 ˘when k " d and µ k " Ω `d´k`1 when d " k, k " 2, 4, 6, . . .. Remark 3.5. In the above theorem, the coefficients µ k are actually different eigenvalues of the integral operator L κ on L 2 τ d pS d q defined by

L κ pf qpyq " ż S d κpx, yqf pxqdτ d pxq, f P L 2 τ d pS d q,

where τ d is the uniform probability measure on unit sphere S d . Therefore the λ r k in Theorem 3.2 is just µ k´1 given in Theorem 3.4 when τ d is uniform distribution.

Remark 3.6. Vempala and Wilmes (2018) studied two-layer neural networks with sigmoid activation function, and established guarantees to achieve 0 ` error with iteration complexity T " pd`1q Opkq log p}f ˚}2{ q under the over-parameterization condition m " pd`1q Opkqpolyp}f ˚}2{ q , where f ˚is the target function, and 0 is certain function approximation error. Another highly related work is Bietti and Mairal (2019) , which gives µ k " Ωpk ´d´1 q. The order of eigenvalues we present appears as µ k " Ωpmaxpk ´d´1 , d ´k`1 qq. This is better when d " k, which is closer to the practical setting.

3.3. EXPLICIT CONVERGENCE RATE FOR UNIFORMLY DISTRIBUTED DATA:

In this subsection, we combine our results in the previous two subsections and give explicit convergence rate for uniformly distributed data on the unit sphere. Note that the first k distinct eigenvalues of NTK have spherical harmonics up to degree k ´1 as eigenfunctions.

Corollary 3.7. Suppose that k " d, and the sample tx i u n i"1 follows the uniform distribution τ d on the unit sphere S d . For any , δ ą 0 and integer k,

if n ě r Ωp ´2 ¨maxtk 2d`2 , k 2d´2 r 2 k uq, m ě r ΩppolypT, k d`1 , ´1qq, then with probability at least 1 ´δ, Algorithm 1 with η " r Oppmθ 2 q ´1q, θ " r Op q satisfies n ´1{2 ¨}V J r k py ´p y pT q q} 2 ď 2 `1 ´Ω `k´d´1 ˘˘T ¨n´1{2 ¨}V J r k y} 2 ` ,

where r k " ř k´1 k 1 "0 N pd, k 1 q and V r k " pn ´1{2 φ j px i qq nˆr k with φ 1 , . . . , φ r k being a set of orthonomal spherical harmonics of degrees up to k ´1.

Corollary 3.8. Suppose that d " k, and the sample tx i u n i"1 follows the uniform distribution τ d on the unit sphere S d . For any , δ ą 0 and integer k, if n ě r Ωp ´2d 2k´2 r 2 k q, m ě r ΩppolypT, d k´2 , ´1qq, then with probability at least 1 ´δ, Algorithm 1 with η " r Oppmθ 2 q ´1q, θ " r Op q satisfies

n ´1{2 ¨}V J r k py ´p y pT q q} 2 ď 2 `1 ´Ω `d´k`2 ˘˘T ¨n´1{2 ¨}V J r k y} 2 ` ,

where r k " ř k´1 k 1 "0 N pd, k 1 q and V r k " pn ´1{2 φ j px i qq nˆr k with φ 1 , . . . , φ r k being a set of orthonomal spherical harmonics of degrees up to k ´1.

Corollaries 3.7 and 3.8 further illustrate the spectral bias of neural networks by providing exact calculations of λ r k , V r k 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 on n and m depend exponentially on either k or d. We would like to emphasize that such exponential dependency is reasonable and unavoidable. In our case, we can take the d " k setting as an example. The exponential dependency in k is a 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 reasonable to expect to learn less than n independent components of the true function, which means that it is unavoidable to assume

n ě r k " k´1 ÿ k 1 "0 N pd, k 1 q " k´1 ÿ k 1 "0 2k 1 `d ´1 k 1 `k1 `d´2 d´1 ˘" k´1 ÿ k 1 "0 2k 1 `d ´1 k 1 `k1 `d´2 k 1 ´1 ˘" Ωpd k´1 q.

Similar arguments can apply to the requirement of m and the k " d setting.

4. EXPERIMENTS:

In this section we illustrate our results by training neural networks on synthetic data. Across all tasks, we train a 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 10 .

4.1. LEARNING COMBINATION OF SPHERICAL HARMONICS:

First, we show a result when the target function is exactly linear combination of spherical harmonics. The target function is explicitly defined as

f ˚pxq " a 1 ¨P1 pxζ 1 , xyq `a2 ¨P2 pxζ 2 , xyq `a4 ¨P4 pxζ 4 , xyq,

where the P k ptq is the Gegenbauer polynomial, and ζ k , k " 1, 2, 4 are fixed vectors that are independently generated from uniform distribution on unit sphere in R 10 in our experiments. Note that according to the addition formula ř N pd,kq j"1 Y k,j pxqY k,j pyq " N pd, kqP k pxx, yyq, every normalized Gegenbauer polynomial is a spherical harmonic, so f ˚pxq is a linear combination of spherical harmonics of order 1,2 and 4. The higher odd-order Gegenbauer polynomials are omitted because the spectral analysis showed that µ k " 0 for k " 3, 5, 7 . . . . Following the setting in section 3.1, we denote v k " n ´1{2 pP k px 1 q, . . . , P k px n qq. By Lemma 3.2 v k 's are almost orthonormal with high probability. So we can define the (approximate) projection length of residual r ptq onto v k at step t as p a k " |v J k r ptq |, where r ptq " pf ˚px 1 q´θf W ptq px 1 q, . . . , f ˚px n q´θf W ptq px n qq and f W ptq pxq is the neural network function. Remark 4.1. Here p a k is the projection length onto an approximate vector. In the function space, we can also project the residual function rpxq " f ˚pxq ´θf W ptq pxq onto the orthonormal Gegenbauer functions P k pxq. Replacing the training data with randomly sampled data points x i can lead to a random estimate of the projection length in function space. We provide the corresponding result for freshly sampled points in Appendix E.1. The results are showned in Figure 1 . It can be seen that at the beginning of training, the residual at the lowest frequency (k " 1) converges to zero first and then the second lowest (k " 2). The highest frequency component is the last one to converge. Following the setting of Rahaman et al. (2018) we assign high frequencies a larger scale, expecting that larger scale will introduce a better descending speed. Still, the low frequencies are regressed first.

4.2. LEARNING FUNCTIONS OF SIMPLE FORM:

Apart from the synthesized low frequency function, we also showed the dynamics of normal functions' projection to P k pxq. These functions, though in a 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 ˚pxq " ř i cospa i xζ, xyq or f ˚pxq " ř i xζ, xy pi , where ζ is a fixed unit vector. The coefficients of given components are calculated in the same way as in Section 4.1. 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 is controlled at 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 P 1 pxq. To show a general tendency it is better to restrict the target function in the even function space.

5. CONCLUSION AND DISCUSSION:

In this paper, we give theoretical justification for spectral bias through a detailed analysis of the 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 eigenvalues 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 S d . Combined with the convergence analysis, we give the exact order of convergence rate on different directions. We also conduct experiments on synthetic data to support our theoretical result.

So far, we have considered the upper bound for convergence with respect to low frequency components 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 essential 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 to weaken the requirement on over-parameterization, or study the spectral bias in a non-NTK regime to furthur close the gap between theory and practice.

A REVIEW ON SPHERICAL HARMONICS:

In this section, we give a brief review on 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 d " x P R d`1 : }x} 2 " 1 ( , whose surface area is given by ω d " 2π pd`1q{2 {Γppd `1q{2q and denote τ d the uniform measure on the sphere. We have the addition formula

N pd,kq ÿ j"1 Y k,j pxqY k,j pyq " N pd, kqP k pxx, yyq, (A.1)

where P k ptq is the Legendre polynomial of degree k in d `1 dimensions, explicitly given by (Rodrigues' formula)

P k ptq " ˆ´1 2 ˙k Γ `d 2 Γ `k `d 2 ˘`1 ´t2 ˘2´d 2 ˆd dt ˙k `1 ´t2 ˘k`d ´2 2 .

We can also see that P k ptq, the Legendre polynomial of degree k shares the same parity with k. By the orthogonality and the addition formula (A.1) we have, ż

S d P j pxw, xyqP k pxw, yyqdτ d pwq " δ jk N pd, kq P k pxx, yyq. (A.2)

Further we have the recurrence relation for the Legendre polynomials,

tP k ptq " k 2k `d ´1 P k´1 ptq `k `d ´1 2k `d ´1 P k`1 ptq, (A.3)

for k ě 1 and tP 0 ptq " P 1 ptq for k " 0.

The Hecke-Funk formula is given for a spherical harmonic

Y k of degree k ż S d f pxx, yyqY k pyqdt 1 d pyq " ω d´1 ω d Y k pxq ż 1 ´1 f ptqP k ptqp1 ´t2 q pd´2q{2 dt.

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 connections between neural network gradients throughout training and the neural tangent kernel. To do so, we first introduce the following definitions and notations.

Define K p0q " m ´1px∇ W f W p0q px i q, ∇ W f W p0q px j qyq nˆn , K p8q " pκpx i , x j qq nˆn " lim mÑ8 K p0q . Let t p λ i u n i"1 , p λ 1 ě ¨¨¨ě p λ n be the eigenvalues of n ´1K 8 , and p v 1 , . . . , p v n be the corresponding eigenvectors. Set p

V r k " pp v 1 , . . . , p v r k q, p V K r k " pp v r k `1, . . . , p v n q.

For notation simplicity, we denote

∇ W f W p0q px i q " r∇ W f W px i qs ˇˇW"W p0q , ∇ W l f W p0q px i q " r∇ W l f W px i qs ˇˇW"W p0q , l " 1, 2.

The following lemma is a direct application of Proposition 1 in Smale and Zhou (2009) or Proposition 10 in Rosasco et al. (2010) . It bounds the difference between the eigenvalues of NTK and their finite-width counterparts.

Lemma B.1. For any δ ą 0, with probability at least 1 ´δ,

|λ i ´p λ i | ď Op a logp1{δq{nq.

The following lemma is partly summarized from the proof of equation ( 44) in Su and Yang (2019) .

Its purpose is to further connect the eigenfunctions of NTK with their finite-width, finite-sample counterparts.

Lemma B.2. Suppose that |φ i pxq| ď M for all x P S d . There exist absolute constants C, C 1 , c 2 ą 0, such that for any δ ą 0 and integer k with r k ď n, if n ě Cpλ r k ´λr k `1q ´2 logp1{δq, then with probability at least 1 ´δ,

}V J r k p V K r k } F ď C 1 1 λ r k ´λr k `1 ¨c logp1{δq n , }V r k V J r k ´p V r k p V J r k } 2 ď C 2 " 1 λ r k ´λr k `1 ¨c logp1{δq n `M 2 r k c logpr k {δq n  .

The following two lemmas are key to characterize the dynamics of the residual throughout training. These two 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., 2018b; 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 p0q , . . . , W ptq are inside the ball BpW p0q , ωq. If ω ď Oprlogpmqs ´3{2 q, then with probability at least 1 ´Opn 2 q ¨expr´Ωpmω 2{3 qs, y ´p y pt 1 `1q " rI ´pηmθ 2 {nqK 8 spy ´p y pt 1 q q `eptq , }e pt 1 q } 2 ď r Opω 1{3 ηmθ 2 q ¨}y ´p y pt 1 q } 2 for all t 1 " 0, . . . , t ´1, where y " py 1 , . . . , y n q J , p y pt 1 q " θ ¨pf W pt 1 q px 1 q, . . . , f W pt 1 q px n qq J .

Lemma B.4. Suppose that the iterates of gradient descent W p0q , . . . , W ptq are inside the ball BpW p0q , ωq. If ω ď r Opmintrlogpmqs ´3{2 , λ 3 r k , pηmq ´3uq and n ě r Opλ ´2 r k q, then with probability at least 1 ´Opt 2 n 2 q ¨expr´Ωpmω 2{3 qs, }p p V K r k q J py ´p y pt 1 q q} 2 ď }p p V K r k q J py ´p y p0q q} 2 `t1 ¨ω1{3 ηmθ 2 ¨?n ¨r Op1 `ω? mq (B.1)

} p V J r k py ´p y pt 1 q q} 2 ď p1 ´ηmθ 2 λ r k {2q t 1 } p V J r k py ´p y p0q q} 2 `t1 λ ´1 r k ¨ω2{3 ηmθ 2 ¨?n ¨r Op1 `ω? mq `λ´1 r k ¨r Opω 1{3 q ¨}p p V K r k q J py ´p y p0q q} 2 (B.2) }y ´p y pt 1 q } 2 ď r Op ? nq ¨p1 ´ηmθ 2 λ r k {2q t 1 `r Op ? n ¨pηmθ 2 λ r k q ´1q `λ´1 r k t 1 ω 1{3 ¨?n ¨r Op1 `ω? mq (B.

3) for all t 1 " 0, . . . , t ´1. We first show that all the iterates W p0q , . . . , W pT q are inside the ball BpW p0q , ωq. We prove this result by inductively show that W ptq P BpW p0q , ωq, t " 0, . . . , T . First of all, it is clear that W p0q P BpW p0q , ωq. Suppose that W p0q , . . . , W ptq P BpW p0q , ωq. Then the results of Lemmas D.2, D.4, D.5, B.3 and B.4 hold for W p0q , . . . , W ptq . Denote u ptq " y ´p y ptq , t P T . Then we have

}W pt`1q l ´Wp0q l } F ď t ÿ t 1 "0 }W pt 1 `1q l ´Wpt 1 q l } F " η t ÿ t 1 "0 › › › › › 1 n n ÿ i"1 py i ´θ ¨fW ptq px i qq ¨θ ¨∇W l f W ptq px i q › › › › › F ď ηθ t ÿ t 1 "0 1 n n ÿ i"1 |y i ´θ ¨fW ptq px i q| ¨}∇ W l f W ptq px i q} F ď C 1 ηθ ? m t ÿ t 1 "0 1 n n ÿ i"1 |y i ´θ ¨fW ptq px i q| ď C 1 ηθ a m{n t ÿ t 1 "0 }y ´p y pt 1 q } 2 ,

where the second inequality follows by Lemma D.4. By Lemma B.4, we have

t ÿ t 1 "0 }y ´p y pt 1 q } 2 ď r Op ? n{pηmθ 2 λ r k qq `r OpT ? n{pηmθ 2 λ r k qq `λ´1 r k T 2 ω 1{3 ? n ¨r Op1 `ω? mq.

It then follows by the choice ω " CT {pθλ r k ? mq, η " r Oppmθ 2 λ r k q ´1q, θ " r Op q and the assumption m ě r OppolypT,

λ ´1 r k , ´1qq that }W pt`1q l ´Wp0q l } F ď ω, l " 1, 2.

Therefore by induction, we see that with probability at least 1´OpT 3 n 2 q¨expr´Ωpmω 2{3 qs, Wp0q, . . . , WpT q P BpW p0q , ωq .

Applying Lemma B.4 then gives n ´1{2 ¨} p V J r k py ´p y pT q q} 2 ď p1 ´ηmθ 2 λ r k {2q T ¨n´1{2 ¨} p V J r k py ´p y p0q q} 2 `T λ ´1 r k ¨ω2{3 ηmθ 2 ¨r Op1 `ω? mq `λ´1 r k ¨r Opω 1{3 q ¨n´1{2 ¨}p p V K r k q J py ´p y p0q q} 2 .

Now by ω " CT {pλ r k ? mq, η " r Opθ 2 mq ´1 and the assumption that m ě m ˚" r Opλ ´14 r k ¨ ´6q, we obtain n ´1{2 ¨} p V J r k py ´p y pT q q} 2 ď p1 ´λr k q T ¨n´1{2 ¨} p V J r k py ´p y p0q q} 2 ` {16. (B.4) By Lemma 3.1, θ " r Op q and the assumptions n ě r Ωpmaxt ´1pλ r k ´λr k `1q ´1, ´2M 2 r 2 k uq, the eigenvalues of V J r k V r k are all between 1{ ? 2 and ? 2. Therefore by Lemma B.2 we have

} p V J r k py ´p y pT q q} 2 " } p V r k p V J r k py ´p y pT q q} 2 ě }V r k V J r k py ´p y pT q q} 2 ´}pV r k V J r k ´p V r k p V J r k qpy ´p y pT q q} 2 ě }V J r k py ´p y pT q q} 2 { ? 2 ´?n ¨Oˆ1 λ r k ´λr k `1 ¨c logp1{δq n `M r k c logpr k {δq n ě }V J r k py ´p y pT q q} 2 { ? 2 ´ ? n{16.

Similarly,

} p V J r k py ´p y p0q q} 2 ď ? 2 ¨}V J r k py ´p y p0q q} 2 ` ? n{16 ď ? 2 ¨}V J r k y} 2 `?2 ¨}V J r k p y p0q } 2 ` ? n{16.

By Lemma 3.1, with probability at least 1 ´δ, }V J r k } 2 ď 1 `Cr k M 2 a logpr k {δq{n. Combining this result with Lemma D.3 gives }V J r k p y p0q } 2 ď θOp a n log pn{δqq ď ? n{8. Plugging the above estimates into (B.4) gives n ´1{2 ¨}V J r k py ´p y pT q q} 2 ď 2p1 ´λr k q T ¨n´1{2 ¨}V J r k y} 2 ` . Applying union bounds completes the proof.

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 k " d and we present a more general case including k " d and d " k. For any function g : S d Ñ R, by denoting g 0 pxq " ş S d gpyqdτ d pyq, it can be decomposed as

gpxq " 8 ÿ k"0 g k pxq " 8 ÿ k"0 N pd,kq ÿ j"1 ż S d Y kj pyqY kj pxqgpyqdτ d pyq " 8 ÿ k"0 N pd, kq ż S d gpyqP k pxx, yyqdτ d pyq, (B.5)

where we project function g to spherical harmonics in the second equality and apply the addition equation in the last equality.

For a positive-definite dot-product kernel κpx, x 1 q : S d ˆSd Ñ R which has the form κpx, x 1 q " p κpxx, x 1 yq for p κ : r´1, 1s Ñ R, we can present a decomposition by (B.5) if we consider gpxq " φpxx, zyq for z P S d and φ : r´1, 1s Ñ R,

κpx, x 1 q " 8 ÿ k"0 N pd, kq ż S d p κpxy, x 1 yqP k pxy, xyqdτ d pyq " 8 ÿ k"0 N pd, kq ω d´1 ω d P k pxx, x 1 yq ż 1 ´1 p κptqP k ptqp1 ´t2 q pd´2q{2 dt,

where we apply the Hecke-Funk formula and addition formula. By denoting λ k " pω d´1 {ω d q ş 1 ´1 p κptqP k ptqp1 ´t2 q pd´2q{2 dt and the addition formula, we have

κpx, x 1 q " 8 ÿ k"0 µ k N pd, kqP k pxx, x 1 yq " 8 ÿ k"0 µ k N pp,kq ÿ j"1 Y k,j pxqY k,j px 1 q. (B.6)

This formula (B.6) is the Mercer decomposition for the kernel function κpx, x 1 q and µ k is exactly the eigenvalue of the integral operator L K on L 2 pS d q defined by L κ pf qpyq "

ż S d

κpx, yqf pxqdτ d pxq, f P L 2 pS d q.

By using same technique as κpx, x 1 q, we can derive a similar expression for σpxw, xyq " max txw, xy, 0u and σ 1 pxw, xyq " 1txw, xy ą 0u, since they are essentially dot-product function on L 2 pS d q. We deliver the expression below without presenting proofs.

σ 1 pxw, xyq " 8 ÿ k"0 β 1,k N pd, kqP k pxw, xyq, (B.7) σpxw, xyq " 8 ÿ k"0 β 2,k N pd, kqP k pxw, xyq, (B.8)

where β 1,k " pω d´1 {ω d q ş 1 ´1 σptqP k ptqp1´t 2 q pd´2q{2 dt and β 2,k " pω d´1 {ω d q ş 1 ´1 σ 1 ptqP k ptqp1t 2 q pd´2q{2 dt. We add more comments on the values of β 1,k and β 2,k . It has been pointed out in Bach (2017) that when k ą α and when k and α have same parity, we have β α`1,k " 0. This is because the Legendre polynomial P k ptq is orthogonal to any other polynomials of degree less than k with respect to the density function pptq " p1 ´t2 q pd´2q{2 . Then we clearly know that β 1,k " 0 for k " 2j and β 2,k " 0 for k " 2j `1 with j P N `.

For two kernel function defined in (2.2), we have

κ 1 px, x 1 q " E w"N p0,Iq " σ 1 pxw, xyqσ 1 pxw, x 1 yq ‰ " E w"N p0,Iq " σ 1 pxw{ }w} , xyqσ 1 pxw{ }w} , x 1 yq ‰ " ż S d σ 1 pxv, xyqσ 1 pxv, x 1 yqdτ d pvq. (B.9)

The first equality holds because σ 1 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 we can derive κ 2 px, x 1 q " pd `1q In Bach (2017) , explicit expressions for β 1,k and β 2,k for k ě α `1 are presented by

β α`1,k " d ´1 2π α!p´1q pk´1´αq{2 2 k Γpd{2qΓpk ´αq Γp k´α`1 2 qΓp k`d`α`1 2 q .

By Stirling formula Γpxq « x x´1{2 e ´x?

2π, we have following expression of β α`1,k for k ě α `1

β α`1,k " Cpαq pd ´1qd d´1 2 pk ´αq k´α´1 2 pk ´α `1q k´α 2 pk `d `α `1q k`d`α 2 " Ω ´d d`1 2 k k´α´1 2 pk `dq ´k´d´α 2

where Cpαq "

? 2α! 2π exptα `1u. Also β α`1,0 " d´1 4π Γp α`1 2 qΓp d 2 q Γp d`α`2 2 q , β 1,1 " d´1 2dπ and β 2,1 " d´1 4πd Γp 1 2 qΓp d`2 2 q Γp d`3 2 q .

Thus combine (B.13) we know that µ α`1,k " Ω `dd`1`α k k´α´1 pk `dq ´k´d´α ˘.

By considering (A.3) and (B.6), we have

EQUATION

µ k " k 2k `d ´1 µ 1,k´1 `k `d ´1 2k `d ´1 µ 1,k`1 `2µ 2,k , for k ě 1 and k ‰ k 1 .

From the discussion above, we thus know exactly that for k ě 1

µ k " Ω `max d d`1 k k´1 pk `dq ´k´d , d d`1 k k pk `dq ´k´d´1 , d d`2 k k´2 pk `dq ´k´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 |φ j pxq| for j P rr k s to finish the proof. Since now we assume input data follows uniform distribution on the unit sphere S d , φ j pxq would be spherical harmonics of order at most k for j P rr k s. For any spherical harmonics Y k of order k and any point on S d , we have an upper bound (Proposition 4.16 in Frye and Efthimiou (2012) )

|Y k pxq| ď ˆN pd, kq ż S d Y 2 k pyqdτ d pyq ˙1 2 .

Thus we know that |φ j pxq| ď a N pd, kq. For k " d, we have N pd, kq " 2k`d´1 k `k`d´2 d´1 ˘"

Opk d´1 q. For d " k, we have N pd, kq " 2k`d´1 k `k`d´2 d´1 ˘" Opd k q. This completes the proof.

This completes the proof of (B.2). Finally, for (B.3), by assumption we have ω 1{3 ηmθ 2 ď r Op1q. Therefore

}u pt 1 `1q } 2 ď }rI ´pηmθ 2 {nqK 8 s p V r k p V J r k u pt 1 q } 2 `}rI ´pηmθ 2 {nqK 8 s p V K r k p p V K r k q J u pt 1 q } 2 `r Opω 1{3 ηmθ 2 q ¨} p V J r k u pt 1 q } 2 `r Opω 1{3 ηmθ 2 q ¨}p p V K r k q J u pt 1 q } 2 ď p1 ´ηmθ 2 p λ r k q} p V J r k u pt 1 q } 2 `r Opω 1{3 ηmθ 2 q ¨} p V J r k u pt 1 q } 2 `r Op1q ¨}p p V K r k q J u pt 1 q } 2 ď p1 ´ηmθ 2 λ r k {2q} p V J r k u pt 1 q } 2 `r Op1q ¨}p p V K r k q J u pt 1 q } 2 ď p1 ´ηmθ 2 λ r k {2q} p V J r k u pt 1 q } 2 `r Op1q ¨}p p V K r k q J u p0q } 2 `t1 ω 1{3 ηmθ 2 ? n ¨r Op1

`ω? mq for t 1 " 0, . . . , t ´1, where the third inequality is by Lemma B.1 and the assumption that ω ď r Opλ 3 r k q, and the fourth inequality follows by (B.1). Therefore we have

}u pt 1 q } 2 ď Op ? nq ¨p1 ´ηmθ 2 λ r k {2q t 1 `r Oppηmθ 2 λ r k q ´1q ¨}p p V K r k q J u p0q } 2 `λ´1 r k t 1 ω 1{3 ? n ¨r Op1

`ω? mq. This finishes the proof.

D AUXILIARY LEMMAS:

In this section we list several auxiliary lemmas on the properties of over-parameterized neural networks we need in our proof of Theorem 3.2. These results are mostly summarized from Allen-Zhu et al. ( 2018) and Cao and Gu (2019a) 

EQUATION

EQUATION

1 x i q m ą 0u ˘.

Lemma D.1 (Allen-Zhu et al. ( 2018)). If ω ď Oprlogpmqs ´3{2 q, then with probability at least 1 ´Opnq ¨expr´Ωpmω 2{3 qs, }D i ´Dp0q i } 0 ď Opω 2{3 mq for all W P BpW p0q , ωq, i P rns. Lemma D.2 (Cao and Gu (2019a) ). There exists an absolute constant κ such that, with probability at least 1 ´Opnq ¨expr´Ωpmω 2{3 qs over the randomness of W p1q , for all i P rns and W, W 1 P BpW p0q , ωq with ω ď κrlogpmqs ´3{2 , it holds uniformly that (Cao and Gu (2019a) ). For any δ ą 0, if m ě C logpn{δq for a large enough absolute constant C, then with probability at least 1 ´δ, |f W p0q px i q| ď Op a logpn{δqq for all i P rns. Lemma D.4 (Cao and Gu (2019a) ). There exists an absolute constant C such that, with probability at least 1 ´Opnq ¨expr´Ωpmω 2{3 qs, for all i P rns, l P rLs and W P BpW p0q , ωq with ω ď Crlogpmqs ´3, it holds uniformly that

|f W 1 px i q ´fW px i q ´x∇ W f W px i q, W 1 ´Wy| ď O ´ω1{3 a m logpmq ¯¨}W 1 1 ´W1 } 2 . Lemma D.3

}∇ W l f W px i q} F ď Op ? mq.

The following lemma provides a uniform bound of the neural network function value over BpW p0q , ωq.

Lemma D.5. Suppose that m ě Ωpω ´2{3 logpn{δqq and ω ď Oprlogpmqs ´3q. Then with probability at least 1 ´δ, |f W px i q| ď Op a logpn{δq `ω? mq for all W P BpW p0q , ωq i P rns. Lemma D.6. If ω ď Oprlogpmqs ´3{2 q, then with probability at least 1 ´Opnq ¨expr´Ωpmω 2{3 qs,

}∇ W f W px i q ´∇W f W p0q px i q} F ď Opω 1{3 ? mq, |x∇ W f W px i q, ∇ W f W px j qy ´x∇ W f W p0q px i q, ∇ W f W p0q px j qy| ď Opω 1{3 mq

for all W P BpW p0q , ωq and i P rns.

D.2 PROOFS OF LEMMAS D.5 AND D.6:

Proof of Lemma D.5. By Lemmas D.2 and D.4, we have

|f W px i q ´fW p0q px i q| ď }∇ W1 f W p0q px i q} F }W 1 ´Wp0q 1 } F `}∇ W2 f W p0q px i q} F }W 2 ´Wp0q 2 } F `Opω 1{3 a m logpmqq ¨}W 1 ´Wp0q 1 } 2 ď Opω ? mq,

where the last inequality is by the assumption ω ď rlogpmqs ´3. Applying triangle inequality and Lemma D.3 then gives

|f W px i q| ď |f W p0q px i q| `|f W px i q ´fW p0q px i q| ď Op a logpn{δqq `Opω ? mq " Op a logpn{δq `ω? mq,

This completes the proof.

Proof of Lemma D.6. By direct calculation, we have Therefore }∇ W1 f W px i q ´∇W1 f W p0q px i q} F ď Opω 1{3 ? mq for all i P rns. This proves the bound for the first layer gradients. For the second layer gradients, we have ∇ W2 f W p0q px i q " ? m ¨rσpW p0q 1 x i qs J , ∇ W2 f W px i q " ? m ¨rσpW 1 x i qs J It therefore follows by the 1-Lipschitz continuity of σp¨q that

∇ W1 f W p0q px i q " ? m ¨Dp0q i W p0qJ 2 x J i , ∇ W1 f W px i q " ? m ¨Di W J 2 x J i . Therefore we have }∇ W1 f W px i q ´∇W1 f W p0q px i q} F " ? m ¨}D i W J 2 x J i ´Dp0q i W p0qJ 2 x J i } F " ? m ¨}x i W 2 D i ´xi W p0q 2 D p0q i } F " ? m ¨}W 2 D i ´Wp0q 2 D p0q i } F ď ? m ¨}W

}∇ W2 f W px i q ´∇W2 f W p0q px i q} F ď ? m ¨}W 1 x i ´Wp0q 1 x i } F ď ω ? m ď ω 1{3 ? m.

This completes the proof of the first inequality.

The second inequality directly follows by triangle inequality and Lemma D.4:

|x∇ W f W px i q, ∇ W f W px j qy ´mK p0q | ď |x∇ W f W px i q ´∇W f W p0q px i q, ∇ W f W px j qy| `|x∇ W f W p0q px i q, ∇ W f W px j q ´∇W f W p0q px j qy| ď Opω 1{3 mq.

This finishes the proof.

E ADDITIONAL EXPERIMENTAL RESULTS:



E.1 ESTIMATING THE PROJECTION LENGTH IN FUNCTION SPACE:

As mentioned in Section 4.1, when using freshly sampled points, we are actually estimating the projection length of residual function rpxq " f ˚pxq ´θf W ptq pxq onto the given Gegenbauer polynomial P k pxq. Here we present in Figure 3 a comparison between the projection length using training data and that using test data. An interesting phenomenon is that the network generalizes well on the lower-order Gegenbauer polynomial and along the highest-order Gegenbauer polynomial the network suffers overfitting. We can see that for low-order Gegenbauer polynomials, the network learns 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 4 we can see that the convergence of different projection length is close to linear convergence, which is well-aligned with our theorem. Note that we performed a moving average of range 20 on these curves to avoid the heavy oscillation especially in late stage. 

:

Here the dimension of input is d `1 since throughout this paper we assume that all training data lie in the d-dimensional unit sphere S d P R d`1 .

Figures and Tables:

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 are shown in Appendix E.2.

Figure 2: Convergence curve for different components. (a) shows the curve of a trigonometric function. (b) shows the curve of a polynomial with even degrees. Both exhibits similar tendency as combination of spherical harmonics.

j : S d Ñ R|1 ď j ď N pd, kq " 2k`d´1 k `k`d´2 d´1 ˘).They form an orthonormal basis and satisfy the following equation xY ki , Y sj y S d " ş S d Y ki pxqY sj pxqdτ d pxq " δ ij δ sk . Moreover, since they are homogeneous functions of degree k, it is clear that Y k pxq has the same parity as k.

Now we are ready to prove Theorem 3.2. Proof of Theorem 3.2. Define ω " CT {pλ r k ? mq for some small enough absolute constant C. Then by union bound, as long as m ě r ΩppolypT, λ ´1 r k , ´1qq, the conditions on ω given in Lemmas D.2, D.4, D.5, B.3 and B.4 are all satisfied.

´W2 qD i } F By Lemma 7.4 in Allen-Zhu et al. (2018) and Lemma D.1, with probability at least 1 q} F ď Opω 1{3 ? mq for all i P rns. Moreover, clearly }pW p0q ´W2 qD i } F ď }W p0q 2 ´W2 } F ď ω.

Figure3: Convergence curve for projection length onto vectors (determined by training data) and functions (estimated by test data). We can see that for low-order Gegenbauer polynomials, the network learns the function while for the high-order Gegenbauer polynomial, the network overfits the training data.

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.

Peer review (iclr2020):
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. That 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. I have a few questions about the generality of this result, and its application to make better machine learning systems: 1) 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. 2) 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?