The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies

Introduction

Neural networks have proven effective even though they often contain a large number of trainable parameters that far exceeds the training data size. This defies conventional wisdom that such overparameterization would lead to overfitting and poor generalization. The dynamics of neural networks trained with gradient descent can help explain this phenomenon. If networks explore simpler solutions before complex ones, this would explain why even overparameterized networks settle on simple solutions that do not overfit. It will also imply that early stopping can select simpler solutions that generalize well, . This is demonstrated in Figure 2-left.

We analyze the dynamics of neural networks using a frequency analysis (see also , discussed in Section 2). Building on (and under the same assumptions) we show that when a network is trained with a regression loss to learn a function over data drawn from a uniform distribution, it learns the low frequency components of the function significantly more rapidly than the high frequency components (see Figure 2).

Specifically, show that the time needed to learn a function, $f$, is determined by the projection of $f$ onto the eigenvectors of a matrix $H^{\infty}$, and their corresponding eigenvalues. had previously noted that for uniformly distributed training data, the eigenvectors of this matrix are spherical harmonic functions (analogs to the Fourier basis on hyperspheres). This work makes a number of strong assumptions. They analyze shallow, massively overparameterized networks with no bias. Data is assumed to be normalized.

Building on these results, we compute the eigenvalues of this linear system. Our computation allows us to make specific predictions about how quickly each frequency of the target function will be learned. For example, for the case of 1D functions, we show that a function of frequency $k$ can be learned in time that scales as $k^{2}$. We show experimentally that this prediction is quite accurate, not only for the simplified networks we study analytically, but also for realistic deep networks.

Bias terms in the network may be neglected without affecting previous theoretical results. However, we show that without bias, two-layer neural networks cannot learn or even represent functions with odd frequencies. This means that in the limit of large data, the bias-free networks studied by cannot learn certain simple, low-frequency functions. We show experimentally that a real shallow network with no bias cannot learn such functions in practice. We therefore modify the model to include bias. We show that with bias added, the eigenvectors remain spherical harmonics, and that odd frequencies can be learned at a rate similar to even frequencies.

Our results show that essentially a network first fits the training data with low frequency functions and then gradually adds higher and higher frequencies to improve the fit. Figure 2-right shows a rather surprising consequence of this. A deep network is trained on the black data points. The orange curve shows the function the network learns. Notice that where there is data missing, the network interpolates with a low frequency function, rather than with a more direct curve. This is because a more straightforward interpolation of the data, while fairly smooth, would contain some high frequency components. The function that is actually learned is almost purely low frequency show a related figure. In the context of meta-learning they show that a network trained to regress to sine waves can learn a new sine wave from little training data. Our figure shows a different phenomenon, that, when possible, a generic network will fit data with low-frequency sine waves..

This example is rather extreme. In general, our results help to explain why networks generalize well and don’t overfit. Because networks learn low frequency functions faster than high frequency ones, if there is a way to fit the data with low-frequency, the network will do this instead of overfitting with a complex, high-frequency function.

Prior Work

Some prior work has examined the way that the dynamics or architecture of neural networks is related to the frequency of the functions they learn. bound the Fourier transform of the function computed by a deep network and of each gradient descent (GD) update. Their method makes the strong assumption that the network produces zeros outside a bounded domain. A related analysis for shallow networks is presented in . Neither paper makes an explicit prediction of the speed of convergence. derive bounds that show that for band limited functions two-layer networks converge to a generalizable solution. show that deeper networks can learn high frequency functions that cannot be learned by shallow networks with a comparable number of units. analyzes the ability of networks to learn based on the frequency of functions computed by their components.

Recent papers study the relationship between the dynamics of gradient descent and the ability to generalize. shows that in logistic regression gradient descent leads to max margin solutions for linearly separable data. shows that with the hinge loss a two layer network provably finds a generalizeable solution for linearly separable data. provide related results. studies the effect of gradient descent on the alignment of the weight matrices for linear neural networks. uses the model discussed in this paper to study generalization.

It has been shown that the weights of heavily overparameterized networks change little during training, allowing them to be accurately approximated by linear models that capture the nonlinearities caused by ReLU at initialization . These papers and others analyze neural networks without an explicit bias term . As points out, bias can be ignored without loss of generality for these results, because a constant value can be appended to the training data after it is normalized. However, we show that bias has a significant effect on the eigenvalues of these linear systems.

Some recent work (e.g., , ) raises questions about the relevance of this lazy training to practical systems. Interestingly, our experiments indicate that our theoretical predictions, based on lazy training, fit the behavior of real, albeit simple, networks. The relevance of results based on lazy training to large-scale real-world systems remains an interesting topic for future research.

Background

We begin with a brief review of ’s linear dynamics model. We consider a network with two layers, implementing the function

where we initialize the network with $\mathbf{w}_{r}(0)\sim{\cal N}(0,\kappa^{2}I)$. We further set $a_{r}\sim\text{Uniform}\{-1,1\}$ and maintain it fixed throughout the training.

For the dynamic model we define the $(d+1)m\times n$ matrix

Next we define the main object of analysis, the $n\times n$ matrix $H^{\infty}$, defined as the expectation of $H$ over the possible initializations. Its entries are given by

Thm. 4.1 in relates the convergence of training a shallow network with GD to the eigenvalues of $H^{\infty}$. For a network with $m=\Omega\left(\frac{n^{7}}{\lambda_{0}^{4}\kappa^{2}\epsilon^{2}\delta}\right)$ units, $\kappa=O\left(\frac{\epsilon\delta}{\sqrt{n}}\right)$ and learning rate $\eta=O\left(\frac{\lambda_{0}}{n^{2}}\right)$ ($\lambda_{0}$ denotes the minimal eigenvalue of $H^{\infty}$), then with probability $1-\delta$ over the random initializations

where $\mathbf{v}_{1},...,\mathbf{v}_{n}$ and $\lambda_{1},...,\lambda_{n}$ respectively are the eigenvectors and eigenvalues of $H^{\infty}$.

As is noted in , when the training data distributes uniformly on a hypersphere the eigenvectors of $H^{\infty}$ are the spherical harmonics. In this case $H^{\infty}$ forms a convolution matrix. A convolution on a hypersphere is defined by

These results in the previous section imply that we can determine how quickly a network can learn functions of varying frequency by finding the eigenvalues of the eigenvectors that correspond to these frequencies. In this section we address this problem both theoretically and experimentallyCode for experiments shown in this paper can be found at https://github.com/ykasten/Convergence-Rate-NN-Different-Frequencies.. Interestingly, as we establish in Theorem 2 below, the bias-free network defined in (1) is not universal as it cannot represent functions that contain odd frequencies greater than one. As a consequence the odd frequencies lie in the null space of the kernel $K^{\infty}$ and cannot be learned – a significant deficiency in the model of . We have the following:

In the harmonic expansion of $f(\mathbf{x})$ in (1), the coefficients corresponding to odd frequencies $k\geq 3$ are zero.

We show this for $d\geq 2$. The theorem also applies to the case that $d=1$ with a similar proof. Consider the output of one unit, $g(\mathbf{x})=\sigma(\mathbf{w}^{T}\mathbf{x})$ and assume first that $w=(0,...,0,1)^{T}$. In this case $g(\mathbf{x})=\max\{x_{d+1},0\}$ and it is a linear combination of just the zonal harmonics. The zonal harmonic coefficients of $g(x)$ are given by

$\Gamma$ is Euler’s gamma function. Eq. (7) can be written as

For odd $k$, $P_{k,d}(t)$ is antisymmetric. Therefore, for such $k$

This is nothing but the (scaled) inner product of the first order harmonic $t$ with a harmonic of degree $k$, and due to the orthogonality of the harmonic functions this integral vanishes for all odd values of $k$ except $k=1$. This result remains unchanged if we use a general weight vector for $\mathbf{w}$, as it only rotates $g(\mathbf{x})$, resulting in a phase shift of the first order harmonic. Finally, $f$ is a linear combination of single unit functions, and consequently its harmonic coefficients at odd frequencies $k\geq 3$ are zero. ∎

In Figure 3 we use a bias-free, two-layer network to fit data drawn from the function $\cos(3\theta)$. Indeed, as the network cannot represent odd frequencies $k\geq 3$ it fits the data points perfectly with combinations of even frequencies, hence yielding poor generalization.

Since both $K^{\infty}$ and $\bar{K}^{\infty}$ form convolution kernels on the circle, their eigenfunctions include the Fourier series. For the bias-free kernel, $K^{\infty}$, the eigenvalues for frequencies $k\geq 0$ are derived using $a_{k}^{1}=\frac{1}{z_{k}}\int_{-\pi}^{\pi}K^{\infty}(\theta)\cos(k\theta)d\theta$ where $z_{0}=2\pi$ and $z_{k}=\pi$ for $k>0$. (Note that since $K^{\infty}$ is an even function its integral with $\sin(\theta)$ vanishes.) This yields

$H^{\infty}$ is a discrete matrix that represents convolution with $K^{\infty}$. It is circulant symmetric (when constructed with points sampled with uniform spacing) and its eigenvectors are real. Each frequency except the DC is represented by two eigenvectors, one for $\sin(k\theta)$ and the other $\cos(k\theta)$.

(16) allows us to make two predictions. First, the eigenvalues for the even frequencies $k$ shrink at the asymptotic rate of $1/k^{2}$. This suggests, as we show below, that high frequency components are quadratically slower to learn than low frequency components. Secondly, the eigenvalues for the odd frequencies (for $k\geq 3$) vanish. A network without bias cannot learn or even represent these odd frequencies. Du et al.’s convergence results critically depend on the fact that for a finite discretization $H^{\infty}$ is positive definite. In fact, $H^{\infty}$ does contain eigenvectors with small eigenvalues that match the odd frequencies on the training data, as shown in Figure 5, which shows the numerically computed eigenvectors of $H^{\infty}$. The leading eigenvectors include $k=1$ followed by the low even frequencies, whereas the eigenvectors with smallest eigenvalues include the low odd frequencies. However, a bias-free network can only represent those functions as a combination of even frequencies. These match the odd frequencies on the training data, but have wild behavior off the training data (see Fig. 3). In fact, our experiments show that a network cannot even learn to fit the training data when labeled with odd frequency functions with $k\geq 3$.

With bias, the kernel $\bar{K}^{\infty}$ passes all frequencies, and the odd frequencies no longer belong to its null space. The Fourier coefficients for this kernel are

Figure 5 shows that with bias, the highest eigenvectors include even and odd frequencies.

Thm. 4.1 in tells us how fast a network learning each Fourier component should converge, as a function of the eigenvalues computed in (21). Let $\mathbf{y}_{i}$ be an eigenvector of $\bar{H}^{\infty}$ with eigenvalue $\bar{\lambda}_{i}$ and denote by $t_{i}$ the number of iterations needed to achieve an accuracy $\bar{\delta}$. Then, according to (5), $(1-\eta\bar{\lambda}_{i})^{t_{i}}<\bar{\delta}+\epsilon$. Noting that since $\eta$ is small, $\log(1-\eta\bar{\lambda}_{i})\approx-\eta\bar{\lambda}_{i}$, we obtain that $t_{i}>\frac{-\log(\bar{\delta}+\epsilon)}{\eta\bar{\lambda}_{i}}.$ Combined with (21) we get that asymptotically in $k$ the convergence time should grow quadratically for all frequencies.

We perform experiments to compare theoretical predictions to empirical behavior. We generate uniformly distributed, normalized training data, and assign labels from a single harmonic function. We then train a neural network until the error is reduced to 5% of its original value, and count the number of epochs needed. For odd frequencies and bias-free 2-layer networks we halt training when the network fails to significantly reduce the error in a large number of epochs. We run experiments with shallow networks and with deep fully connected networks and deep networks with skip connections. We primarily use an $L_{2}$ loss, but in supplementary material we show results with a cross-entropy loss. Quadratic behavior is observed in all these cases, see Figure 6. The actual convergence times may vary with the details of the architecture and initialization. For very low frequencies the run time is affected more strongly by the initialization, yielding slightly slower convergence times than predicted.

Thm. 5.1 in further allows us to bound the generalization error incurred when learning band limited functions. Suppose $\mathbf{y}=\sum_{k=0}^{\bar{k}}\alpha_{k}e^{2\pi ikx}$. According to this theorem, and noting that the eigenvalues of $(\bar{H}^{\infty})^{-1}\approx\pi k^{2}$, with sufficiently many iterations the population loss $L_{\cal D}$ computed over the entire data distribution is bounded by

As expected, the lower the frequency is, the lower the generalization bound is. For a pure sine wave the bound increases linearly with frequency $k$.

To analyze the eigenvectors of $H^{\infty}$ when the input is higher dimensional, we must make use of generalizations of the Fourier basis and convolution to functions on a high dimensional hypersphere. Spherical harmonics provide an appropriate generalization of the Fourier basis (see as a reference for the following discussion). As with the Fourier basis, we can express functions on the hypersphere as linear combinations of spherical harmonics. Since the kernel is rotationally symmetric, and therefore a function of one variable, it can be written as a linear combination of the zonal harmonics. For every frequency, there is a single zonal harmonic which is also a function of one variable. The zonal harmonic is given by the Gegenbauer polynomial, $P_{k,d}$ where $k$ denotes the frequency, and $d$ denotes the dimension of the hypersphere.

We have already defined convolution in (6) in a way that is general for convolution on the hypersphere. The Funk-Hecke theorem provides a generalization of the convolution theorem for spherical harmonics, allowing us to perform a frequency analysis of the convolution kernel. It states:

(Funk-Hecke) Given any measurable function $K$ on $$, such that the integral:$\int_{-1}^{1}\|K(t)\|(1-t^{2})^{\frac{d-2}{2}}dt<\infty$, for every spherical harmonic$H(\sigma)$of frequency$k$, we have:

The eigenvalues of convolution with $K^{\infty}$ vanish when they correspond to odd harmonics with $k\geq 3$.

where $\mathbf{g}(\mathbf{x})=y(\mathbf{x})\mathbf{x}$. $\mathbf{g}(\mathbf{x})$ is a $(d+1)$-vector whose $l^{\text{th}}$ coordinate is $g^{l}(\mathbf{x})=x^{l}y(x)$. We first note that $g^{l}(\mathbf{x})$ has no DC component. This is because $g^{l}$ is the product of two harmonics, the scaled first order harmonic, $x^{l}$, and the odd harmonic $y(\mathbf{x})$ (with $k>1$), so their inner product vanishes.

Next we will show that the kernel $\mathds{I}(\mathbf{w}^{T}\mathbf{x}>0)$ annihilates the even harmonics, for $k>1$. Note that the odd/even harmonics can be written as a sum of monomials of odd/even degrees. Since $g$ is the sum of even harmonics (the product of $x^{l}$ and an odd harmonic) this will imply that (23) vanishes. Using the Funk-Hecke theorem, the even coefficients of the kernel (with $k>1$) are

When we align the kernel with the zonal harmonic, $\mathbf{w}^{T}\mathbf{x}=t$, justifying the second equality. The third equality is due to the symmetry of the even harmonics, and the last equality is because the harmonics of $k>0$ are zero mean. ∎

Next we compute the eigenvalues of both $K^{\infty}$ and $\bar{K}^{\infty}$ (for simplicity we show only the case of even $d$, see supplementary material for the calculations). We find for networks without bias:

Adding bias to the network, the eigenvalues for $\bar{K}^{\infty}$ are:

Discussion

We have developed a quantitative understanding of the speed at which neural networks learn functions of different frequencies. This shows that they learn high frequency functions much more slowly than low frequency functions. Our analysis addresses networks that are heavily overparameterized, but our experiments suggest that these results apply to real neural networks.

This analysis allows us to understand gradient descent as a frequency based regularization. Essentially, networks first fit low frequency components of a target function, then they fit high frequency components. This suggests that early stopping regularizes by selecting smoother functions. It also suggests that when a network can represent many functions that would fit the training data, gradient descent causes the network to fit the smoothest function, as measured by the power spectrum of the function. In signal processing, it is commonly the case that the noise contains much larger high frequency components than the signal. Hence smoothing reduces the noise while preserving most of the signal. Gradient descent may perform a similar type of smoothing in neural networks.

Acknowledgments. The authors thank Adam Klivans, Boaz Nadler, and Uri Shaham for helpful discussions. This material is based upon work supported by the National Science Foundation under Grant No. DMS1439786 while the authors were in residence at the Institute for Computational and Experimental Research in Mathematics in Providence, RI, during the Computer Vision program. This research is supported by the National Science Foundation under grant no. IIS-1526234.

References

Appendix

Appendix A Cross entropy loss

While this is outside the scope of the theoretical results in the paper, we tested the convergence rate of a network with a single hidden layer with the cross entropy loss. We used a binary classification task. To construct our target classes, for every integer $k>0$ we produced data on the 1D circle according to the function $\cos(k\theta)$, and then thresholded it, assigning class 1 if $\cos(k\theta)>2/3$, -1 if $\cos(k\theta)<2/3$ and omitted points for which $|\cos(k\theta)|\leq 2/3$. As with the MSE loss, here too we see a near quadratic convergence rate, see Figure 8.

Using the Funk-Hecke theorem, we can find the eigenvalues of $H^{\infty}$ in the continuous limit by integrating the product of the convolution kernel with spherical harmonics. We first collect together a number of formulas and integrals that will be useful. We then show how to use the Funk-Hecke theorem to formulate the relevant integrals, and finally compute the results.

$\int_{0}^{\pi}\cos^{n}\theta d\theta$ is $\pi$ for $n=0$ and 0 for $n=1$. For $n>1$ we use integration by parts

$\int_{0}^{\pi}\sin^{n}\theta d\theta$ is $\pi$ for $n=0$ and 2 for $n=1$. For $n>1$ we integrate by parts

Next we wish to compute $\int_{0}^{\pi}\theta cos^{n}\theta\sin\theta d\theta$ for $n\geq 1$. Integrating by parts

The first term vanishes and we obtain from (30)

since this is a product of an odd and even functions.

B.2 The Kernel

for $\theta$ the angle between $x_{i}$ and $x_{j}$ and we use the notation $t=\cos\theta$. For the case of $x_{i}$ uniformly sampled on the hypersphere, this amounts to convolution by the kernel:

The absolute value disappears because on the hypersphere, $\theta$ varies between 0 and $\pi$.

We can divide the integrals we need to compute into four parts. We denote:

This gives us $K^{\infty}=K_{1}+K_{2}$. We denote $K^{b}=K_{3}+K_{4}$. This is the new component introduced by bias. Then we have $\bar{K}^{\infty}=\frac{1}{2}(K^{\infty}+K^{b})=\frac{1}{2}(K_{1}+K_{2}+K_{3}+K_{4})$. We will use $a_{k}^{d}$ to denote the coefficient for frequency $k$ of the harmonic transform of $K^{\infty}$, in dimension $d$. We use $b_{k}^{d}$ to denote the coefficient of the transform for just the bias term, $K^{b}$. And finally, $c_{k}^{d}$ denotes the coefficient for the complete kernel with bias, $\bar{K}^{\infty}$, so that $c_{k}^{d}=a_{k}^{d}+b_{k}^{d}$.

B.3 Application of the Funk Hecke theorem

and $P_{k,d}(t)$ denotes the Gegenbauer polynomial, given by the formula:

$\Gamma$ is Euler’s gamma function whose formulas for integer values of $n$ are:

To simplify the expressions we obtain, we will assume $d$ is even in what follows. For the cases with and without bias we first compute the DC component of the parts of the kernels, and then compute the coefficients for $k>0$.

B.4 Calculating the coefficients: no bias

First we consider $K_{1}$ (49). Using (44) we have

Next, we consider $K_{2}$ (50). Using (39) we have

where we denote $p=k+\frac{d-2}{2}$, noting that $p\geq k$. Using (41)

Combining equations (68), (69), and (70) we obtain:

As is proven in Thm. 3 in the paper, the coefficients for the odd frequencies in (71) (with the exception of $k=1$) vanish.

B.5 Coefficients with bias

Denote the harmonic coefficients of $K^{b}=K_{3}+K_{4}$ by $b_{k}^{d}$ then

The term associated with $K_{3}$ vanishes, since ($p>k-1$)

where $p=k+\frac{d-2}{2}$. Replacing $t=\cos\theta$ and using (37)

where $a_{k}^{d}$ is given in (71), resulting in