Year: 2019

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.

heading: 1 INTRODUCTION
text: 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`1uq. Our result is better than the bound Ωpk´d´1q 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.

heading: 1.1 ADDITIONAL RELATED WORK
text: 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) 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 can achieve zero training loss at a linear convergence rate for training two-layer ReLU network with square loss. Allen-Zhu et al. (2018); Du et al. (2018a); 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 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κfpsq :“ ş
Sd κpx, sqfpsqdτ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κfpxq 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.

heading: 2 PRELIMINARIES
text: 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.

heading: 2.1 NOTATION
text: 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 “ pv1, . . . , vdqT P Rd and a number 1 ď p ă 8, we denote its p´norm by }v}p “ p řd i“1 |vi|pq1{p. We also define infinity norm by }v}8 “ maxi |vi|. For a matrix A “ pAi,jqmˆn, we use }A}0 to denote the number of non-zero entries of A, and use }A}F “ p řd i,j“1A 2 i,jq1{2 to denote its Frobenius norm. Let }A}p “ max}v}pď1 }Av}p for p ě 1, and }A}max “ maxi,j |Ai,j |. For two matrices A,B P Rmˆn, we define xA,By “ TrpAJBq. We use A ľ B if A´B is positive semi-definite. In addition, we define the asymptotic notations Op¨q, rOp¨q, Ωp¨q and rΩp¨q as follows. Suppose that an and bn be two sequences. We write an “ Opbnq if lim supnÑ8 |an{bn| ă 8, and an “ Ωpbnq if lim infnÑ8 |an{bn| ą 0. We use rOp¨q and rΩp¨q to hide the logarithmic factors in Op¨q and Ωp¨q.

heading: 2.2 PROBLEM SETUP
text: Here we introduce the basic problem setup. We consider two-layer fully connected neural networks of the form
fWpxq “ ? m ¨W2σpW1xq,
where W1 P Rmˆpd`1q, W2 P R1ˆ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 “ tpxi, yiq : i P rnsu:
LSpWq “ 1
n
ÿ
pxi,yiqPS pyi ´ θfWpxiqq2 ,
where θ is a small coefficient to control the effect of initialization, and the data inputs txiuni“1 is assumed to follow some unknown distribution τ on the unit sphere Sd P Rd`1. Without loss of generality, we also assume that |yi| ď 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 Wp0q1 and W p0q 2 from Np0, 2{mq and Np0, 1{mq respectively.
for t “ 0, 1, . . . , T ´ 1 do Update Wpt`1q “Wptq ´ η ¨∇WLSpWptqq. end for Output: WpT q.
1Here the dimension of input is d` 1 since throughout this paper we assume that all training data lie in the d-dimensional unit sphere Sd P Rd`1.
The initialization scheme for Wp0q 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.

heading: 2.3 NEURAL TANGENT KERNEL
text: 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,x1q “ limmÑ8m´1x∇WfWp0qpxq,∇WfWp0qpx1qy and we have
κpx,x1q “ xx,x1y ¨ κ1px,x1q ` 2 ¨ κ2px,x1q, (2.1)
where κ1px,x1q “ Ew„Np0,Iqrσ1pxw,xyqσ1pxw,x1yqs, κ2px,x1q “ Ew„Np0,Iqrσpxw,xyqσpxw,x1yqs.
(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
κ1ptq “ 1
2π pπ ´ arccos ptqq , κ2ptq “
1
2π
´
t ¨ pπ ´ arccos ptqq ` a 1´ t2 ¯ , (2.3)
where t “ xx,x1y{ p}x} }x1}q.

heading: 2.4 INTEGRAL OPERATOR
text: 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 L2τ 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 L2τ pXq by
Lκpfqpxq “ ż
X
κpx,yqfpyqdτ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.

heading: 3 MAIN RESULTS
text: 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 Sd. 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.

heading: 3.1 CONVERGENCE ANALYSIS OF GRADIENT DESCENT
text: 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λiuiě1 with λ1 ě λ2 ě ¨ ¨ ¨ be the strictly positive eigenvalues of Lκ, and φ1p¨q, φ2p¨q, . . . be the corresponding orthonormal eigenfunctions. Set vi “ n´1{2pφipx1q, . . . , φipxnqqJ, 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 rk as the sum of the multiplicities of the first k distinct eigenvalues of Lκ. Define Vrk “ pv1, . . . ,vrkq. By definition, vi, i P rrks are rescaled restrictions of orthonormal functions in L2τ pSdq on the training examples. Therefore we can expect them to form a set of almost orthonomal bases in the vector space Rn. The following lemma follows by standard concentration inequality. Lemma 3.1. Suppose that |φipxq| ďM for all x P Sd and i P rrks. For any δ ą 0, with probability at least 1´ δ,
}VJrkVrk ´ I}max ď CM 2 a logprk{δq{n, where C is an absolute constant.
Denote y “ py1, . . . , ynqJ and pyptq “ θ ¨ pfWptqpx1q, . . . , fWptqpxnqq, t “ 0, . . . , T . Then Lemma 3.1 shows that the convergence rate of }VJrkpy ´ py
ptqq}2 roughly represents the speed gradient descent learns the components of the target function corresponding to the first rk eigenvalues. The following theorem gives the convergence guarantee of }VJrkpy ´ py
ptqq}2. Theorem 3.2. Suppose |φjpxq| ď M for j P rrks and x P Sd. For any , δ ą 0 and integer k, if n ě rΩp ´2 ¨maxtpλrk ´ λrk`1q´2,M4r2kuq, m ě rΩppolypT, λ´1rk ,
´1qq, then with probability at least 1´ δ, Algorithm 1 with η “ rOppmθ2q´1q, θ “ rOp q satisfies
n´1{2 ¨ }VJrkpy ´ py pT qq}2 ď 2p1´ λrkqT ¨ n´1{2 ¨ }VJrky}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.

heading: 3.2 SPECTRAL ANALYSIS OF NEURAL TANGENT KERNEL FOR UNIFORM DISTRIBUTION
text: 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,x1 P Sd Ă Rd`1, we have the Mercer decomposition of the neural tangent kernel κ : Sd ˆ Sd Ñ R,
κ ` x,x1 ˘ “ 8 ÿ
k“0 µk
Npd,kq ÿ
j“1 Yk,j pxqYk,j
` x1 ˘ , (3.1)
where Yk,j for j “ 1, ¨ ¨ ¨ , Npd, kq are linearly independent spherical harmonics of degree k in d`1 variables with Npd, kq “ 2k`d´1k ` k`d´2 d´1 ˘ and orders of µk are given by
µ0 “ µ1 “ Ωp1q, µk “ 0, k “ 2j ` 1, µk “ Ω ` max dd`1kk´1pk ` dq´k´d, dd`1kkpk ` dq´k´d´1, dd`2kk´2pk ` 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 L2τdpS dq defined by
Lκpfqpyq “ ż
Sd κpx,yqfpxqdτdpxq, f P L2τdpS dq,
where τd is the uniform probability measure on unit sphere Sd. Therefore the λrk 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`1qOpkq log p}f˚}2{ q under the over-parameterization conditionm “ pd`1qOpkqpolyp}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´1q. The order of eigenvalues we present appears as µk “ Ωpmaxpk´d´1, d´k`1qq. This is better when d " k, which is closer to the practical setting.

heading: 3.3 EXPLICIT CONVERGENCE RATE FOR UNIFORMLY DISTRIBUTED DATA
text: 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 txiuni“1 follows the uniform distribution τd on the unit sphere Sd. For any , δ ą 0 and integer k, if n ě rΩp ´2 ¨ maxtk2d`2, k2d´2r2kuq, m ě rΩppolypT, kd`1, ´1qq, then with probability at least 1 ´ δ, Algorithm 1 with η “ rOppmθ2q´1q, θ “ rOp q satisfies
n´1{2 ¨ }VJrkpy ´ py pT qq}2 ď 2 ` 1´ Ω ` k´d´1 ˘˘T ¨ n´1{2 ¨ }VJrky}2 ` ,
where rk “ řk´1 k1“0Npd, k1q and Vrk “ pn´1{2φjpxiqqnˆrk with φ1, . . . , φrk being a set of orthonomal spherical harmonics of degrees up to k ´ 1. Corollary 3.8. Suppose that d " k, and the sample txiuni“1 follows the uniform distribution τd on the unit sphere Sd. For any , δ ą 0 and integer k, if n ě rΩp ´2d2k´2r2kq, m ě rΩppolypT, dk´2, ´1qq, then with probability at least 1 ´ δ, Algorithm 1 with η “ rOppmθ2q´1q, θ “ rOp q satisfies
n´1{2 ¨ }VJrkpy ´ py pT qq}2 ď 2 ` 1´ Ω ` d´k`2 ˘˘T ¨ n´1{2 ¨ }VJrky}2 ` ,
where rk “ řk´1 k1“0Npd, k1q and Vrk “ pn´1{2φjpxiqqnˆrk with φ1, . . . , φrk 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 λrk , Vrk 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 ě rk “ k´1 ÿ
k1“0 Npd, k1q “
k´1 ÿ
k1“0
2k1 ` d´ 1 k1 ` k1`d´2 d´1 ˘ “ k´1 ÿ
k1“0
2k1 ` d´ 1 k1 ` k1`d´2 k1´1 ˘ “ Ωpdk´1q.
Similar arguments can apply to the requirement of m and the k " d setting.

heading: 4 EXPERIMENTS
text: 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 R10.

heading: 4.1 LEARNING COMBINATION OF SPHERICAL HARMONICS
text: 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 “ a1 ¨ P1pxζ1,xyq ` a2 ¨ P2pxζ2,xyq ` a4 ¨ P4pxζ4,xyq,
where the Pkptq is the Gegenbauer polynomial, and ζk, k “ 1, 2, 4 are fixed vectors that are independently generated from uniform distribution on unit sphere in R10 in our experiments. Note that according to the addition formula
řNpd,kq j“1 Yk,jpxqYk,jpyq “ Npd, kqPkpxx,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 vk “ n´1{2pPkpx1q, . . . , Pkpxnqq. By Lemma 3.2 vk’s are almost orthonormal with high probability. So we can define the (approximate) projection length of residual rptq onto vk at step t as
pak “ |vJk rptq|,
where rptq “ pf˚px1q´θfWptqpx1q, . . . , f˚pxnq´θfWptqpxnqq and fWptqpxq is the neural network function. Remark 4.1. Here pak is the projection length onto an approximate vector. In the function space, we can also project the residual function rpxq “ f˚pxq ´ θfWptqpxq onto the orthonormal Gegenbauer functions Pkpxq. Replacing the training data with randomly sampled data points xi 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.

heading: 4.2 LEARNING FUNCTIONS OF SIMPLE FORM
text: Apart from the synthesized low frequency function, we also showed the dynamics of normal functions’ projection to Pkpxq. 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 cospaixζ,xyq or f˚pxq “ ř ixζ,xypi , 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 P1pxq. To show a general tendency it is better to restrict the target function in the even function space.

heading: 5 CONCLUSION AND DISCUSSION
text: 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 Sd. 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.

heading: A REVIEW ON SPHERICAL HARMONICS
text: 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 Sd “ x P Rd`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. For any k ě 1, we consider a set of spherical harmonics !
Yk,j : Sd Ñ R|1 ď j ď Npd, kq “ 2k`d´1k ` k`d´2 d´1 ˘
)
. They form an orthonormal basis and
satisfy the following equation xYki, YsjySd “ ş Sd YkipxqYsjpxqdτdpxq “ δijδsk. Moreover, since they are homogeneous functions of degree k, it is clear that Ykpxq has the same parity as k. We have the addition formula
Npd,kq ÿ
j“1 Yk,jpxqYk,jpyq “ Npd, kqPkpxx,yyq, (A.1)
where Pkptq is the Legendre polynomial of degree k in d ` 1 dimensions, explicitly given by (Rodrigues’ formula)
Pkptq “ ˆ ´1 2 ˙k Γ ` d 2 ˘ Γ `
k ` d2 ˘
` 1´ t2 ˘
2´d 2
ˆ
d
dt
˙k `
1´ t2 ˘k` d´22 .
We can also see that Pkptq, the Legendre polynomial of degree k shares the same parity with k. By the orthogonality and the addition formula (A.1) we have,
ż
Sd Pjpxw,xyqPkpxw,yyqdτdpwq “ δjk Npd, kqPkpxx,yyq. (A.2)
Further we have the recurrence relation for the Legendre polynomials,
tPkptq “ k 2k ` d´ 1Pk´1ptq ` k ` d´ 1 2k ` d´ 1Pk`1ptq, (A.3)
for k ě 1 and tP0ptq “ P1ptq for k “ 0. The Hecke-Funk formula is given for a spherical harmonic Yk of degree k
ż
Sd fpxx,yyqYkpyqdt1dpyq “ ωd´1 ωd Ykpxq ż 1 ´1 fptqPkptqp1´ t2qpd´2q{2dt.

heading: B PROOF OF MAIN THEOREMS

heading: B.1 PROOF OF THEOREM 3.2
text: 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 Kp0q “ m´1px∇WfWp0qpxiq,∇WfWp0qpxjqyqnˆn, Kp8q “ pκpxi,xjqqnˆn “ limmÑ8K
p0q. Let tpλiuni“1, pλ1 ě ¨ ¨ ¨ ě pλn be the eigenvalues of n´1K8, and pv1, . . . , pvn be the corresponding eigenvectors. Set pVrk “ ppv1, . . . , pvrkq, pVKrk “ ppvrk`1, . . . , pvnq.
For notation simplicity, we denote ∇WfWp0qpxiq “ r∇WfWpxiqs ˇ ˇ W“Wp0q , ∇WlfWp0qpxiq “ r∇WlfWpxiqs ˇ ˇ
W“Wp0q , 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 |φipxq| ď M for all x P Sd. There exist absolute constants C,C 1, c2 ą 0, such that for any δ ą 0 and integer k with rk ď n, if n ě Cpλrk ´ λrk`1q´2 logp1{δq, then with probability at least 1´ δ,
}VJrk pV K rk }F ď C 1
1 λrk ´ λrk`1 ¨ c logp1{δq n ,
}VrkVJrk ´ pVrk pV J rk }2 ď C2
„
1 λrk ´ λrk`1 ¨ c logp1{δq n `M2rk c logprk{δ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 Wp0q, . . . ,Wptq are inside the ball BpWp0q, ωq. If ω ď Oprlogpmqs´3{2q, then with probability at least 1´Opn2q ¨ expr´Ωpmω2{3qs,
y ´ pypt 1`1q “ rI´ pηmθ2{nqK8spy ´ pypt 1qq ` eptq, }ept 1q}2 ď rOpω1{3ηmθ2q ¨ }y ´ pypt 1q}2
for all t1 “ 0, . . . , t´ 1, where y “ py1, . . . , ynqJ, pypt 1q “ θ ¨ pfWpt1qpx1q, . . . , fWpt1qpxnqqJ.
Lemma B.4. Suppose that the iterates of gradient descent Wp0q, . . . ,Wptq are inside the ball BpWp0q, ωq. If ω ď rOpmintrlogpmqs´3{2, λ3rk , pηmq´3uq and n ě rOpλ´2rk q, then with probability at least 1´Opt2n2q ¨ expr´Ωpmω2{3qs,
}ppVKrkq Jpy ´ pypt 1qq}2 ď }ppVKrkq Jpy ´ pyp0qq}2 ` t1 ¨ ω1{3ηmθ2 ¨
? n ¨ rOp1` ω?mq (B.1)
}pVJrkpy ´ py pt1qq}2 ď p1´ ηmθ2λrk{2qt 1 }pVJrkpy ´ py p0qq}2 ` t1λ´1rk ¨ ω 2{3ηmθ2 ¨
? n ¨ rOp1` ω?mq
` λ´1rk ¨ rOpω1{3q ¨ }ppVKrkqJpy ´ pyp0qq}2 (B.2) }y ´ pypt 1q}2 ď rOp ? nq ¨ p1´ ηmθ2λrk{2qt 1 ` rOp?n ¨ pηmθ2λrkq´1q
` λ´1rk t 1ω1{3 ¨
? n ¨ rOp1` ω?mq (B.3)
for all t1 “ 0, . . . , t´ 1.
Now we are ready to prove Theorem 3.2.
Proof of Theorem 3.2. Define ω “ CT {pλrk ? mq for some small enough absolute constant C. Then by union bound, as long as m ě rΩppolypT, λ´1rk , ´1qq, the conditions on ω given in Lemmas D.2, D.4, D.5, B.3 and B.4 are all satisfied.
We first show that all the iterates Wp0q, . . . ,WpT q are inside the ball BpWp0q, ωq. We prove this result by inductively show that Wptq P BpWp0q, ωq, t “ 0, . . . , T . First of all, it is clear that Wp0q P BpWp0q, ωq. Suppose that Wp0q, . . . ,Wptq P BpWp0q, ωq. Then the results of Lemmas D.2, D.4,
D.5, B.3 and B.4 hold for Wp0q, . . . ,Wptq. Denote uptq “ y ´ pyptq, t P T . Then we have
}Wpt`1ql ´W p0q l }F ď
t ÿ
t1“0 }Wpt 1`1q l ´W pt1q l }F
“ η t ÿ
t1“0
›
›
›
›
›
1
n
n ÿ i“1 pyi ´ θ ¨ fWptqpxiqq ¨ θ ¨∇WlfWptqpxiq
›
›
›
›
›
F
ď ηθ t ÿ
t1“0
1
n
n ÿ i“1 |yi ´ θ ¨ fWptqpxiq| ¨ }∇WlfWptqpxiq}F
ď C1ηθ ? m t ÿ
t1“0
1
n
n ÿ i“1 |yi ´ θ ¨ fWptqpxiq|
ď C1ηθ a m{n t ÿ
t1“0 }y ´ pypt 1q}2,
where the second inequality follows by Lemma D.4. By Lemma B.4, we have t ÿ t1“0 }y ´ pypt 1q}2 ď rOp ? n{pηmθ2λrkqq ` rOpT ? n{pηmθ2λrkqq ` λ´1rk T 2ω1{3 ? n ¨ rOp1` ω?mq. It then follows by the choice ω “ CT {pθλrk ? mq, η “ rOppmθ2λrkq´1q, θ “ rOp q and the assumption m ě rOppolypT, λ´1rk , ´1qq that }W pt`1q l ´W p0q l }F ď ω, l “ 1, 2. Therefore by induction, we see that with probability at least 1´OpT 3n2q¨expr´Ωpmω2{3qs, Wp0q, . . . ,WpT q P BpWp0q, ωq . Applying Lemma B.4 then gives
n´1{2 ¨ }pVJrkpy ´ py pT qq}2 ď p1´ ηmθ2λrk{2qT ¨ n´1{2 ¨ }pVJrkpy ´ py p0qq}2 ` Tλ´1rk ¨ ω
2{3ηmθ2 ¨ rOp1` ω?mq ` λ´1rk ¨ rOpω1{3q ¨ n´1{2 ¨ }ppVKrkqJpy ´ pyp0qq}2.
Now by ω “ CT {pλrk ? mq, η “ rOpθ2mq´1 and the assumption that m ě m˚ “ rOpλ´14rk ¨ ´6q, we obtain
n´1{2 ¨ }pVJrkpy ´ py pT qq}2 ď p1´ λrkqT ¨ n´1{2 ¨ }pVJrkpy ´ py p0qq}2 ` {16. (B.4)
By Lemma 3.1, θ “ rOp q and the assumptions n ě rΩpmaxt ´1pλrk ´ λrk`1q´1, ´2M2r2kuq, the eigenvalues of VJrkVrk are all between 1{ ? 2 and ? 2. Therefore by Lemma B.2 we have
}pVJrkpy ´ py pT qq}2 “ }pVrk pVJrkpy ´ py pT qq}2 ě }VrkVJrkpy ´ py pT qq}2 ´ }pVrkVJrk ´ pVrk pV J rk qpy ´ pypT qq}2
ě }VJrkpy ´ py pT qq}2{
? 2´ ? n ¨O ˆ
1 λrk ´ λrk`1 ¨ c logp1{δq n `Mrk c logprk{δq n ˙
ě }VJrkpy ´ py pT qq}2{
? 2´ ? n{16.
Similarly,
}pVJrkpy ´ py p0qq}2 ď ? 2 ¨ }VJrkpy ´ py p0qq}2 ` ? n{16
ď ? 2 ¨ }VJrky}2 ` ? 2 ¨ }VJrkpy p0q}2 ` ? n{16.
By Lemma 3.1, with probability at least 1 ´ δ, }VJrk}2 ď 1 ` CrkM 2 a logprk{δq{n. Combining this result with Lemma D.3 gives }VJrkpy p0q}2 ď θOp a n log pn{δqq ď ? n{8. Plugging the above estimates into (B.4) gives
n´1{2 ¨ }VJrkpy ´ py pT qq}2 ď 2p1´ λrkqT ¨ n´1{2 ¨ }VJrky}2 ` .
Applying union bounds completes the proof.

heading: B.2 PROOF OF THE THEOREM 3.4
text: 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 : Sd Ñ R, by denoting g0pxq “ ş Sd gpyqdτdpyq, it can be decomposed as
gpxq “ 8 ÿ
k“0 gkpxq “
8 ÿ
k“0
Npd,kq ÿ
j“1
ż
Sd YkjpyqYkjpxqgpyqdτdpyq
“ 8 ÿ
k“0 Npd, kq
ż
Sd gpyqPkpxx,yyqdτdpyq, (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,x1q : Sd ˆ Sd Ñ R which has the form κpx,x1q “ pκpxx,x1yq for pκ : r´1, 1s Ñ R, we can present a decomposition by (B.5) if we consider gpxq “ φpxx, zyq for z P Sd and φ : r´1, 1s Ñ R,
κpx,x1q “ 8 ÿ
k“0 Npd, kq
ż
Sd pκpxy,x1yqPkpxy,xyqdτdpyq
“ 8 ÿ
k“0 Npd, kqωd´1 ωd Pkpxx,x1yq
ż 1
´1 pκptqPkptqp1´ t2qpd´2q{2dt,
where we apply the Hecke-Funk formula and addition formula. By denoting λk “ pωd´1{ωdq ş1 ´1 pκptqPkptqp1´ t 2qpd´2q{2dt and the addition formula, we have
κpx,x1q “ 8 ÿ
k“0 µkNpd, kqPkpxx,x1yq “
8 ÿ k“0 µk Npp,kq ÿ j“1 Yk,jpxqYk,jpx1q. (B.6)
This formula (B.6) is the Mercer decomposition for the kernel function κpx,x1q and µk is exactly the eigenvalue of the integral operator LK on L2pSdq defined by
Lκpfqpyq “ ż
Sd κpx,yqfpxqdτdpxq, f P L2pSdq.
By using same technique as κpx,x1q, we can derive a similar expression for σpxw,xyq “ max txw,xy, 0u and σ1pxw,xyq “ 1txw,xy ą 0u, since they are essentially dot-product function on L2pSdq. We deliver the expression below without presenting proofs.
σ1pxw,xyq “ 8 ÿ
k“0 β1,kNpd, kqPkpxw,xyq, (B.7)
σpxw,xyq “ 8 ÿ
k“0 β2,kNpd, kqPkpxw,xyq, (B.8)
where β1,k “ pωd´1{ωdq ş1 ´1 σptqPkptqp1´t 2qpd´2q{2dt and β2,k “ pωd´1{ωdq ş1 ´1 σ 1ptqPkptqp1´ t2qpd´2q{2dt. 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 Pkptq is orthogonal to any other polynomials of degree less than k with respect to the density function pptq “ p1 ´ t2qpd´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
κ1px,x1q “ Ew„Np0,Iq “ σ1pxw,xyqσ1pxw,x1yq ‰
“ Ew„Np0,Iq “ σ1pxw{ }w} ,xyqσ1pxw{ }w} ,x1yq ‰ “ ż
Sd σ1pxv,xyqσ1pxv,x1yqdτdpvq. (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
κ2px,x1q “ pd` 1q ż
Sd σpxv,xyqσpxv,x1yqdτdpvq. (B.10)
By combing (A.2), (B.7), (B.8), (B.9) and (B.10), we can get
κ1px,x1q “ 8 ÿ
k“0 β21,kNpd, kqPkpxx,x1yq, (B.11)
and
κ2px,x1q “ pd` 1q 8 ÿ
k“0 β22,kNpd, kqPkpxx,x1yq. (B.12)
Comparing (B.6), (B.11) and (B.12), we can easily show that
µ1,k “ β21,k and µ2,k “ pd` 1qβ22,k. (B.13) In Bach (2017), explicit expressions for β1,k and β2,k for k ě α` 1 are presented by
βα`1,k “ d´ 1
2π
α!p´1qpk´1´αq{2 2k Γpd{2qΓpk ´ αq
Γpk´α`12 qΓp k`d`α`1 2 q .
By Stirling formula Γpxq « xx´1{2e´x ? 2π, we have following expression of βα`1,k for k ě α`1
βα`1,k “ Cpαq pd´ 1qd d´12 pk ´ αqk´α´ 12
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α`12 qΓp d2 q Γp d`α`22 q , β1,1 “
d´1 2dπ and β2,1 “ d´1 4πd Γp 12 qΓp d`22 q Γp d`32 q . Thus combine (B.13) we know that µα`1,k “ Ω ` dd`1`αkk´α´1pk ` dq´k´d´α ˘
. By considering (A.3) and (B.6), we have
µ0 “ µ1,1 ` 2µ2,0,
µk1 “ 0, k1 “ 2j ` 1, j P N`, and
µ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 ‰ k1. From the discussion above, we thus know exactly that for k ě 1 µk “ Ω ` max dd`1kk´1pk ` dq´k´d, dd`1kkpk ` dq´k´d´1, dd`2kk´2pk ` dq´k´d´1 (˘ .
This finishes the proof.

heading: B.3 PROOF OF THE COROLLARIES 3.7 AND 3.8
text: Proof of the Corollaries 3.7 and 3.8. We only need to bound |φjpxq| for j P rrks to finish the proof. Since now we assume input data follows uniform distribution on the unit sphere Sd, φjpxq would be spherical harmonics of order at most k for j P rrks. For any spherical harmonics Yk of order k and any point on Sd, we have an upper bound (Proposition 4.16 in Frye and Efthimiou (2012))
|Ykpxq| ď ˆ Npd, kq ż
Sd Y 2k pyqdτdpyq
˙ 1 2
.
Thus we know that |φjpxq| ď a Npd, kq. For k " d, we have Npd, kq “ 2k`d´1k ` k`d´2 d´1 ˘ “ Opkd´1q. For d " k, we have Npd, kq “ 2k`d´1k ` k`d´2 d´1 ˘ “ Opdkq. This completes the proof.

heading: C PROOF OF TECHNICAL LEMMAS

heading: C.1 PROOF OF LEMMA B.2
text: 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 Vrk “ pVrkA` pVKrkB, where A P R
rkˆrk , B P Rpn´rkqˆrk . Let ξ1 “ C 1pλrk ´ λrk`1q´1 ¨ a logp1{δq{n, ξ2 “ C3M2 a
logprk{δq{n be the bounds given in the first inequality and Lemma 3.1. By the first inequality, we have
}B}F “ }BJ}F “ }VJrk pV K rk }F ď ξ1.
Moreover, since VJrkVrk “ A JA`BJB, by Lemma 3.1 we have
}AAJ ´ I}2 “ }AJA´ I}2 ď }VJrkVrk ´ I}2 ` }B JB}2 ď rkξ2 ` ξ21 .
Therefore
}VrkVJrk ´ pVrk pV J rk }2
“ }pVrkAAJ pVJrk ` pVrkAB JppVKrkq J ` pVKrkBA J pVJrk ` pV K rk BBJppVKrkq J ´ pVrk pVJrk}2 ď }pVrkpAAJ ´ IqpVJrk}2 `Op}B}2q “ }AAJ ´ I}2 `Op}B}2q ď Oprkξ2 ` ξ1q
Plugging in the definition of ξ1 and ξ2 completes the proof.

heading: C.2 PROOF OF LEMMA B.3
text: Proof of Lemma B.3. The gradient descent update formula gives
Wpt`1q “Wptq ` 2η n
n ÿ i“1 pyi ´ θfWptqpxiqq ¨ θ∇WfWptqpxiq. (C.1)
For any j P rns, subtracting Wptq and applying inner product with θ∇WfWptqpxjq on both sides gives
θx∇WfWptqpxjq,Wpt`1q ´Wptqy “ 2ηθ2
n
n ÿ i“1 pyi ´ pyptqi q ¨ x∇WfWptqpxjq,∇WfWptqpxiqy.
Further rearranging terms then gives
yj ´ ppypt`1qqj “ yj ´ ppyptqqj ´ 2ηmθ2
n
n ÿ i“1 pyi ´ θfWptqpxiqq ¨K8i,j ` I1,j,t ` I2,j,t ` I3,j,t,
(C.2)
where
I1,j,t “ ´ 2ηθ2
n
n ÿ i“1 pyi ´ θfWptqpxiqq ¨ rx∇WfWptqpxjq,∇WfWptqpxiqy ´mKp0qi,j s,
I2,j,t “ ´ 2ηmθ2
n
n ÿ i“1 pyi ´ θfWptqpxiqq ¨ pK p0q i,j ´K 8 i,jq,
I3,j,t “ ´θ ¨ rfWpt`1qpxjq ´ fWptqpxjq ´ x∇WfWptqpxjq,Wpt`1q ´Wptqys. For I1,j,t, by Lemma D.6, we have
|I1,j,t| ď Opω1{3ηmθ2q ¨ 1
n
n ÿ i“1 |yi ´ θfWptqpxiq| ď Opω1{3ηmθ2q ¨ }y ´ pyptq}2{ ? n
with probability at least 1´Opnq ¨ expr´Ωpmω2{3qs. For I2,j,t, by Bernstein inequality and union bound, with probability at least 1´Opn2q ¨ expp´Ωpmω2{3qq, we have
ˇ ˇK8i,j ´K p0q i,j ˇ ˇ ď Opω1{3q
for all i, j P rns. Therefore
|I2,j,t| ď Opω1{3ηmθ2q ¨ 1
n
n ÿ i“1 |yi ´ θfWptqpxiq| ď Opω1{3ηmθ2q ¨ }y ´ pyptq}2{ ? n.
For I3,j,t, we have
I3,j,t ď rOpω1{3 ? mθq ¨ }Wpt`1q1 ´W ptq 1 }2
ď rOpω1{3?mθq ¨ 2η n n ÿ
i“1 |yi ´ θfWptqpxiq| ¨ θ ¨ }∇W1fWptqpxiq}2
ď rOpω1{3ηmθ2q ¨ 1 n
n ÿ i“1 |yi ´ θfWptqpxiq|
ď rOpω1{3ηmθ2q ¨ }y ´ pyptq}2{ ? n,
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 eptq as I1,j,t` I2,j,t` I3,j,t and writing (C.2) into matrix form completes the proof.

heading: C.3 PROOF OF LEMMA B.4
text: Proof of Lemma B.4. Denote uptq “ y ´ pyptq, t P T . Then we have
}ppVKrkq Jupt 1`1q}2 ď }ppVKrkq JrI´ pηmθ2{nqK8supt 1q}2 ` rOpω1{3ηmθ2q ¨ }upt 1q}2
ď }ppVKrkq Jupt 1q}2 ` rOpω1{3ηmθ2q ¨ ? n ¨ rOp1` ω?mq,
where the first inequality follows by Lemma B.3, and the second inequality follows by Lemma D.5. Therefore we have
}ppVKrkq Jupt 1q}2 ď }ppVKrkq Jup0q}2 ` t1 ¨ ω1{3ηmθ2 ¨
? n ¨ rOp1` ω?mq,
for t1 “ 0, . . . , t. This completes the proof of (B.1). Similarly, we have
}pVJrku pt1`1q}2 ď }pVJrk rI´ pηmθ 2{nqK8supt 1q}2 ` rOpω1{3ηmθ2q ¨ }upt 1q}2 ď p1´ ηmθ2pλrkq}pVJrku pt1q}2 ` rOpω1{3ηmθ2q ¨ p}pVJrkupt 1q}2 ` }ppVKrkq Jupt 1q}2q
ď p1´ ηmθ2λrk{2q}pVJrku pt1q}2 ` rOpω1{3ηmθ2q ¨ }ppVKrkqJupt 1q}2 ď p1´ ηmθ2λrk{2q}pVJrku pt1q}2 ` t1 ¨ pω1{3ηmθ2q2 ¨ ? n ¨ rOp1` ω?mq
` rOpω1{3ηmθ2q ¨ }ppVKrkqJup0q}2 for t1 “ 0, . . . , t ´ 1, where the third inequality is by Lemma B.1 and the assumption that ω ď rOpλ3rkq, n ě rOpλ´2rk q, and the fourth inequality is by (B.1). Therefore we have
}pVJrku pt1q}2 ď p1´ ηmθ2λrk{2qt 1 }pVJrku p0q}2 ` t1 ¨ pηmθ2λrk{2q´1 ¨ pω1{3ηmθ2q2 ¨ ? n ¨ rOp1` ω?mq
` pηmθ2λrk{2q´1 ¨ rOpω1{3ηmθ2q ¨ }ppVKrkqJup0q}2 “ p1´ ηmθ2λrk{2qt 1 }pVJrku p0q}2 ` t1λ´1rk ¨ ω 2{3ηmθ2 ¨ ? n ¨ rOp1` ω?mq
` λ´1rk ¨ rOpω1{3q ¨ }ppVKrkqJup0q}2 ď p1´ ηmθ2λrk{2qt 1 }pVJrku p0q}2 ` t1λ´1rk ¨ ω 2{3ηmθ2 ¨ ? n ¨ rOp1` ω?mq
` λ´1rk ¨ rOpω1{3q ¨ }ppVKrkqJup0q}2.
This completes the proof of (B.2). Finally, for (B.3), by assumption we have ω1{3ηmθ2 ď rOp1q. Therefore }upt 1`1q}2 ď }rI´ pηmθ2{nqK8spVrk pVJrku pt1q}2 ` }rI´ pηmθ2{nqK8spVKrkppV K rk qJupt
1q}2 ` rOpω1{3ηmθ2q ¨ }pVJrkupt 1q}2 ` rOpω1{3ηmθ2q ¨ }ppVKrkqJupt 1q}2
ď p1´ ηmθ2pλrkq}pVJrku pt1q}2 ` rOpω1{3ηmθ2q ¨ }pVJrkupt 1q}2 ` rOp1q ¨ }ppVKrkqJupt 1q}2 ď p1´ ηmθ2λrk{2q}pVJrku pt1q}2 ` rOp1q ¨ }ppVKrkqJupt
1q}2 ď p1´ ηmθ2λrk{2q}pVJrku pt1q}2 ` rOp1q ¨ }ppVKrkqJup0q}2 ` t1ω1{3ηmθ2 ? n ¨ rOp1` ω?mq
for t1 “ 0, . . . , t ´ 1, where the third inequality is by Lemma B.1 and the assumption that ω ď rOpλ3rkq, and the fourth inequality follows by (B.1). Therefore we have }upt 1q}2 ď Op ? nq ¨ p1´ ηmθ2λrk{2qt 1 ` rOppηmθ2λrkq´1q ¨ }ppVKrkqJup0q}2 ` λ´1rk t1ω1{3 ? n ¨ rOp1` ω?mq.
This finishes the proof.

heading: D AUXILIARY LEMMAS
text: 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).

heading: D.1 AUXILIARY LEMMAS
text: Denote
Di “ diag ` 1tpW1xiq1 ą 0u, . . . ,1tpW1xiqm ą 0u ˘ ,
D p0q i “ diag ` 1tpWp0q1 xiq1 ą 0u, . . . ,1tpW p0q 1 xiqm ą 0u ˘ .
Lemma D.1 (Allen-Zhu et al. (2018)). If ω ď Oprlogpmqs´3{2q, then with probability at least 1´Opnq ¨ expr´Ωpmω2{3qs,
}Di ´Dp0qi }0 ď Opω2{3mq for all W P BpWp0q, ω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{3qs over the randomness of Wp1q, for all i P rns and W,W1 P BpWp0q, ωq with ω ď κrlogpmqs´3{2, it holds uniformly that |fW1pxiq ´ fWpxiq ´ x∇WfWpxiq,W1 ´Wy| ď O ´ ω1{3 a m logpmq ¯ ¨ }W11 ´W1}2.
Lemma D.3 (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´ δ, |fWp0qpxiq| ď 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{3qs, for all i P rns, l P rLs and W P BpWp0q, ωq with ω ď Crlogpmqs´3, it holds uniformly that
}∇WlfWpxiq}F ď Op ? mq.
The following lemma provides a uniform bound of the neural network function value over BpWp0q, ωq. Lemma D.5. Suppose that m ě Ωpω´2{3 logpn{δqq and ω ď Oprlogpmqs´3q. Then with probability at least 1´ δ, |fWpxiq| ď Op a logpn{δq ` ω ? mq for all W P BpWp0q, ωq i P rns.
Lemma D.6. If ω ď Oprlogpmqs´3{2q, then with probability at least 1´Opnq ¨ expr´Ωpmω2{3qs, }∇WfWpxiq ´∇WfWp0qpxiq}F ď Opω1{3 ? mq,
|x∇WfWpxiq,∇WfWpxjqy ´ x∇WfWp0qpxiq,∇WfWp0qpxjqy| ď Opω1{3mq for all W P BpWp0q, ωq and i P rns.

heading: D.2 PROOFS OF LEMMAS D.5 AND D.6
text: Proof of Lemma D.5. By Lemmas D.2 and D.4, we have
|fWpxiq ´ fWp0qpxiq| ď }∇W1fWp0qpxiq}F }W1 ´Wp0q1 }F ` }∇W2fWp0qpxiq}F }W2 ´W p0q 2 }F
`Opω1{3 a m logpmqq ¨ }W1 ´Wp0q1 }2 ď Opω?mq,
where the last inequality is by the assumption ω ď rlogpmqs´3. Applying triangle inequality and Lemma D.3 then gives
|fWpxiq| ď |fWp0qpxiq| ` |fWpxiq ´ fWp0qpxiq| ď 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
∇W1fWp0qpxiq “ ? m ¨Dp0qi W p0qJ 2 x J i ,∇W1fWpxiq “ ? m ¨DiWJ2 xJi .
Therefore we have }∇W1fWpxiq ´∇W1fWp0qpxiq}F “ ? m ¨ }DiWJ2 xJi ´D p0q i W p0qJ 2 x J i }F
“ ? m ¨ }xiW2Di ´ xiWp0q2 D p0q i }F “ ? m ¨ }W2Di ´Wp0q2 D p0q i }F ď ? m ¨ }Wp0q2 pD p0q i ´Diq}F ` ? m ¨ }pWp0q2 ´W2qDi}F
By Lemma 7.4 in Allen-Zhu et al. (2018) and Lemma D.1, with probability at least 1 ´ n ¨ expr´Ωpmqs, ? m ¨ }Wp0q2 pD p0q i ´ Diq}F ď Opω1{3 ? mq for all i P rns. Moreover, clearly }pWp0q2 ´W2qDi}F ď }W p0q 2 ´W2}F ď ω. Therefore
}∇W1fWpxiq ´∇W1fWp0qpxiq}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
∇W2fWp0qpxiq “ ? m ¨ rσpWp0q1 xiqsJ,∇W2fWpxiq “ ? m ¨ rσpW1xiqsJ
It therefore follows by the 1-Lipschitz continuity of σp¨q that
}∇W2fWpxiq ´∇W2fWp0qpxiq}F ď ? m ¨ }W1xi ´Wp0q1 xi}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∇WfWpxiq,∇WfWpxjqy ´mKp0q| ď |x∇WfWpxiq ´∇WfWp0qpxiq,∇WfWpxjqy| ` |x∇WfWp0qpxiq,∇WfWpxjq ´∇WfWp0qpxjqy|
ď Opω1{3mq. This finishes the proof.

heading: E ADDITIONAL EXPERIMENTAL RESULTS

heading: E.1 ESTIMATING THE PROJECTION LENGTH IN FUNCTION SPACE
text: As mentioned in Section 4.1, when using freshly sampled points, we are actually estimating the projection length of residual function rpxq “ f˚pxq ´ θfWptqpxq onto the given Gegenbauer polynomial Pkpxq. 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.

heading: E.2 NEAR-LINEAR CONVERGENCE BEHAVIOR
text: 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.

Review summaries:
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.