Frequency Bias in Neural Networks for Input of Non-Uniform Density

Introduction

A key question in understanding the success of neural networks is: what makes over-parameterized networks generalize so well, avoiding solutions that overfit the training data? In search of an explanation, a number of recent papers (Farnia et al., 2018; Rahaman et al., 2019; Xu et al., 2019) have suggested that training with gradient descent (GD) (as well as SGD) yields a frequency bias – in early epochs training a neural net yields a low frequency fit to the target function, while high frequencies are learned only in later epochs, if they are needed to fit the data (see Figure 1(top)).

This frequency bias has been carefully analyzed in the case of over-parameterized, two-layer networks with Rectified Linear Unit (ReLU) activation, when only the first layer is trained. The dynamics of GD in this case was shown to match the dynamics of GD for the corresponding Neural Tangent Kernel (NTK) (Arora et al., 2019b; Du et al., 2019; Jacot et al., 2018). Assuming the training data is distributed uniformly on a hypersphere, the NTK matrix forms a convolution on the sphere. Its eigenvectors consist of the spherical harmonic functions (Basri et al., 2019; Xie et al., 2017), and its eigenvalues shrink monotonically with frequency, yielding longer convergence times for high frequency components. Specifically, for training data on the circle, high frequencies are learned quadratically slower than low frequencies, and this frequency-dependent gap increases exponentially with dimension (Basri et al., 2019; Bietti & Mairal, 2019; Cao et al., 2019).

All this previous work assumed that training data is distributed uniformly. However, realistic training datasets are distributed with a non-uniform density. A natural question therefore is to what extent frequency bias is exhibited for such datasets? Below we provide evidence that frequency bias interacts with density. We show that in any region of the input space with locally constant density, low frequencies are still learned much faster than high frequencies, but the rate of learning also depends linearly on the density. This phenomenon is demonstrated in Figure 1(bottom).

Our paper contains both theoretical and empirical results. We first focus on analyzing the NTK model for two-layer networks with ReLU activation and 2D input, normalized to lie on the unit circle, allowing for input drawn from a non-uniform density that is piecewise constant. For this model we derive closed form expressions for its eigenfunctions and eigenvalues. These eigenfunctions contain functions of piecewise constant local frequency, with higher frequencies where the density of the training data is higher. This implies that we learn high frequency components of a target function faster in regions of higher density. This also allows us to prove that a pure 1-dimensional sine function of frequency $\kappa$ is learned in time $O(\kappa^{2}/p^{*})$, where $p^{*}$ denotes the minimum density in the input space. Our experiments illustrate these results and further suggest that for input on a $d-1$-dimensional hypersphere, spherical harmonics are learned in time $O(\kappa^{d}/p^{*})$.

We next examine the NTK for deep, fully connected (FC) networks. We first prove that given a target function $y(\mathbf{x})$, training networks of finite width with GD converges to $y$ at a speed that depends on the projection of $y$ over the eigenvectors of the NTK, extending previous results proved for two-layer networks (Arora et al., 2019b; Cao et al., 2019). We further show that for uniform data the eigenfunctions of NTK consist of the spherical harmonics. We complement these observations with several empirical findings. (1) We show that for uniformly distributed data the eigenvalues decay with frequency, suggesting that frequency bias exists also in deep FC networks. Moreover, similar to two-layer networks, a pure harmonic function of frequency $\kappa$ is learned in time $O(\kappa^{d})$ asymptotically in $\kappa$. However, deeper networks appear to learn frequencies of lower $k$ faster than shallow ones. (2) For training data drawn from non-uniform densities the eigenfunctions of NTK appear indistinguishable from those obtained for two-layer networks, indicating that with deep nets learning a harmonic of frequency $\kappa$ should also require $O(\kappa^{d}/p^{*})$ iterations.

Our results have several implications. First, we extend results that have been proven for training data with a uniform density to the more realistic case of non-uniform density, also extending results for shallow networks to deep, fully connected networks. These results support the idea that real neural networks have a frequency bias that can explain their ability to avoid overfitting. Second, while it is not surprising that networks fit functions of all frequencies more slowly in regions with low data density, we demonstrate that this is the case and quantify this effect. Our results have an interesting implication for training that uses early stopping to regularize the solution. Suppose the signal one wishes to fit is low frequency, and it is corrupted by high frequency noise. Because a network learns low frequency signals more slowly in regions of low density, by the time the signal is learned in these regions, the network will also have learned high frequency components of the noise in regions of high density. This is illustrated in Figure 1(bottom).

Motivating example: Target function made of low frequency + high frequency noise (of small amplitude). Data is composed, say, of two constant densities. Show fit at different epochs. Essentially we want to show that network cannot fit the low frequency in all space at any given time. i.e. to get the low frequency at the sparse part you already fit the noise in the dense part [Ronen: Should we show in contrast that this is possible with uniform density? Maybe not..]

2 layers, NTK: the eigenfunctions obtained for a certain density. Also for 2D data.

2 layers, NTK: a plot of the eigenvalues + normalized by Z to show they all coincide.. Also for 2D data.

2 layers network: convergence times for several densities + normalized so that all parabolas coincide

Inverse linear relation of convergence time and density. Also for 2D data.

Deep NTK: eigenfunctions for uniform and non-uniform densities. (Maybe unnecessary because they are the same as the shallow case, or maybe plot just the ones for a deep net?)

Deep, NTK: exponent as a function of number of layers for 1D, 2D and maybe 3D.

Deep network: actual convergence times for 3, 5 and 7 layers. Show a fit to the previous figure. Also for 2D input.

Eigen functions under the uniform density are spherical harmonics and are ordered according to frequency.

Complexity (exponent) of convergence rate under the uniform density as a function of depth and dimension (graph).

Run experiments to fit this graph (using Yoni’s code).

Non-uniform for deep FC + experiment. Also Resnet?

Verify theory for non-uniform. Are the eigenvalues identical to the uniform case?

Probably not in this round: NTK for Resnet

Prior work

Many recent papers attempt to explain the generalization ability of overparameterized nets. Perhaps the most convincing relate overparameterized networks to kernel methods. (Jacot et al., 2018) identified a family of kernels, termed Neural Tangent Kernels, and showed that neural networks behave like these kernels, in the limit of infinite widths. Related work investigated variants of these kernels, showing that networks of finite, albeit very large widths converge to zero training error almost always and deriving generalization bounds for such networks. These analyses were applied to two-layer networks (Bach, 2017; Bietti & Mairal, 2019; Du et al., 2019; Vempala & Wilmes, 2018; Xie et al., 2017), multilayer perceptrons (i,e. fully connected), residual and convolutional networks (Allen-Zhu et al., 2018, 2019; Arora et al., 2019a; Huang & Yau, 2019; Lee et al., 2019).

However, these kernel models have been criticised for requiring unrealistically wide networks. Additionally, it is still debated if such linear dynamics (referred to as “lazy training”) fully explain the performance of neural networks. Recent theoretical and empirical results suggest that NTK models still somewhat underperform common nonlinear networks (Arora et al., 2019a; Chizat et al., 2019; Novak et al., 2019; Woodworth et al., 2019).

Other work suggested that networks are biased to learn simple functions, and in particular that GD proceeds by first fitting a low frequency function to the target function, and only fits the higher frequencies in later epochs (Rahaman et al., 2019; Xu et al., 2019; Farnia et al., 2018). Additional work (Bach, 2017; Basri et al., 2019; Bietti & Mairal, 2019; Cao et al., 2019) proved the existence of frequency bias in NTK models of two-layer networks and derived convergence rates of training as a function of target frequency. All of these works assumed that training data is distributed uniformly. (Canu & Elisseef, 1999) proposed loss functions that allow higher frequency fit in regions where training data is dense, and only low frequency fit in the sparse regions. Our results suggest that such a penalization may be implicitly enforced in NTK models.

Classical work on kernel methods acknowledged the importance of understanding the eigenfunctions and eigenvalues of kernels for non-uniform data distributions, but focused mainly on bounding the difference between the empirical kernel matrix and the theoretical kernel for the given distribution (e.g., (Shawe-Taylor et al., 2005; Williams & Seeger, 2000)). (Liang & Lee, 2013) derived analytic expressions for the eigenfunctions of polynomial kernels. (Goel & Klivans, 2017) investigated the gram matrix of the data distribution and showed that sufficiently fast decay of its eigenvalues allows learnability by neural networks. We are unaware of works that derive analytic expressions for the eigenfunctions of NTK under non-uniform distributions.

Left outs: Papers showing implicit regularization (https://arxiv.org/abs/1810.01075). Convergence results for two-layers (like Arora fine grained) + spherical harmonics for uniform distribution (https://arxiv.org/pdf/1912.01198.pdf) The dynamics of gradient descent bias the model towards simple solutions - initialization separates deep and shallow (https://arxiv.org/pdf/1909.12051.pdf)

Preliminaries

We consider in this work NTK models for fully connected neural networks with rectified linear unit (ReLU) activations. These kernels are defined through the following formula

We first consider a two layer network with bias:

We then consider deep fully-connected networks with $L+1>2$ layers. For such networks we forgo the bias since our empirical results (Section 5) indicate that they are universal even without bias. These networks are expressed as

For our analysis, to simplify the NTK expressions, in the case of a two-layer network we only train the weights and bias of the first layer (as in (Arora et al., 2019b; Du et al., 2019)). We initialize these weights from a normal distribution $\mathbf{w}_{r}^{(0)},b_{r}^{(0)}\sim{\cal N}(0,\tau^{2}I)$. We further initialize $a_{r}$ from a uniform distribution on $\{-1,1\}$ and keep those weights fixed. In the case of deep networks we train all the weights, initializing by $\mathbf{w}\sim{\cal N}(0,I)$.

We next provide expressions for the corresponding neural tangent kernels. For a two-layer network with bias where only the first layer weights are trained the corresponding NTK takes the form (Basri et al., 2019)

For a deep FC network the NTK is expressed by the following recursion (Arora et al., 2019a; Jacot et al., 2018)

Here $\dot{\sigma}(\cdot)$ denotes the step function (i.e., the derivative of the ReLU function). The covariance matrices have the form $\Lambda=\begin{bmatrix}1&\rho\\ \rho&1\end{bmatrix}$ with $|\rho|\leq 1$, and the expectations have the following closed form expressions

The eigenfunctions of NTK for two-layer networks for non-uniform distributions

implying the eigenfunctions exist and $\lambda$ is real.

We next parameterize the unit circle by angles, and denote by $x,z$ any two angles. We can therefore express (7) as

where the kernel in (5) expressed in terms of angles reads

Both $p(x)$ and $f(x)$ are periodic with a period of $2\pi$ since $x$ lies on the unit circle.

Below we solve (9) and derive an explicit expression for the eigenfunctions $f(x)$. Our derivation assumes that $p(x)$ is piecewise constant. While this assumption limits the scope of our solution, empirical results suggest that when $p(x)$ changes continuously the eigenfunctions are modulated continuously, consistently with our solution. We summarize:

In other words, over the region $R_{j}$, this is a cosine function with frequency proportional to $\sqrt{p_{j}}$. A plot of eigenfunctions for a piecewise constant distribution is shown in Fig. 3.

The proof of the proposition relies on a lemma, proved in supplementary material, stating that the solution to (9) satisfies the following second order ordinary differential equation (ODE)

In a nutshell, the lemma proved by applying a sequence of six derivatives to (9) with respect to $x$, along with some algebraic manipulations, yielding a sixth order ODE for $f(x)$. Assuming that $p(x)$ is piecewise constant simplifies the ODE. Then (13) is obtained by restricting $p(x)$ to have a period of $\pi$, but this restriction can be lifted by preprocessing the data in a straightforward way without changing the function that needs to be learned.

Eq. (13) has the following general solutions

such that the derivative of $\Psi$ is $\Psi^{\prime}(x)=\sqrt{p(x)}$, resulting in real eigenfunctions of the form

As with the uniform distribution, due to periodic boundary conditions there is a countable number of eigenvalues, and those can be determined (up to scale) using the known eigenvalues for the uniform case (Basri et al., 2019). With this we obtain

$q$ is integer, and there is one eigenfunction for $q=0$ and two eigenfunctions for every $q>0$. Figure 4 shows a plot of the eigenvalues computed for various densities.

The amplitudes and phase shifts are determined by requiring the eigenfunctions to be continuous and differentiable everywhere. We show in supplementary material that for two neighboring regions, $j,j+1$ it holds that if $p_{j}\leq p_{j+1}$ then the ratio of the amplitudes is bounded (tightly) for different values of $p_{j}$ and $p_{j+1}$ as follows:

Figure 3 shows the eigenvectors and eigenvalues for an example of a piecewise constant distribution. It can be seen that each eigenfunction consists of a piecewise sine function; i.e., the eigenfunctions in every region where $p(x)$ is constant form pure sine functions with frequency that changes from one region to the next. As we inspect eigenfunctions with decreasing eigenvalues we find, as our theory shows (see Figure 3), that the frequencies increase in all regions, but for all eigenfunctions they maintain constant ratios that are equal to the ratios between the square roots of the corresponding densities. Finally, Figure 5 shows the eigenvectors of $H^{p}$ for a continuous distribution, showing similar behaviour to our analytic expressions.

2 Time to convergence

Proving this theorem is complicated by the fact that (1) the frequency of the target function may not be exactly represented in the eigenfunctions of the kernel, due to the discrete number of eigenfunctions, and (2) the eigenfunctions restricted to any given region $R_{j}$ are not orthogonal. These two properties may result in non-negligible correlations of $g(x)$ with eigenfunctions of yet smaller eigenvalues. Therefore, to prove Theorem 1 we first inspect the projections of $g(x)$ onto the eigenfunctions corresponding to such small eigenvalues and prove a bound on this tail. Subsequently we use this bound to prove the convergence rate in the theorem. The proofs are provided in the supplementary material.

In Figure 7 we used the target function $g(x)=\sin(\kappa x)$ for different values of $\kappa$ to train a 2-layer network. The data was sampled from a non-uniform distribution with three constant regions of densities $3/(2\pi)(1/7,2/7,4/7)$. It can be seen that runtime increases for each region in proportion to $\kappa^{2}$, and the network converged faster at denser regions (in proportion to $p(x)$).

3 Higher dimension

Deep networks

We next extend our discussion to NTK models of deep, fully connected networks. We first prove that the eigenvectors of NTK indeed characterize the convergence of GD of highly overparmeterized networks of finite width. We then empirically investigate the eigenvectors and eigenvalues of NTK for data drawn from either uniform or non-uniform distributions and show convergence times for pure sine and harmonic target functions.

We begin by showing that the eigenvectors of NTK characterize the dynamics of overparameterized FC networks of finite width. Our theorem extends Thm. 4.1 in (Arora et al., 2019b) (see also (Cao et al., 2019)), which has dealt with two-layer networks, to deep nets. Consider a FC network of depth $L$ and width $m$ in each layer, and suppose the network is trained with $n$ pairs $\{(\mathbf{x}_{i},y_{i})\}_{i=1}^{n}$. Denote the vector of target values by $\mathbf{y}=(y_{1},...,y_{n})$ and the network predictions for these values at time $t$ by $\mathbf{u}^{(t)}$. In our theorem, Thm. 2, we use a slightly different model than the model stated above (3). First, we assume that the first and last layers are initialized and then held fixed throughout training, and the last layer is initialized randomly $\sim\mathcal{N}(0,\tau^{2}I)$. The NTK for this training data is summarized in an $n\times n$ matrix $H^{\infty}$, whose entries are set to $H^{\infty}_{ij}=k(\mathbf{x}_{i},\mathbf{x}_{j})$ where $k$ is defined in (1). Let $\mathbf{v}_{i}$ and $\lambda_{i}$ respectively denote the eigenvectors of $H^{\infty}$ and their corresponding eigenvalues. The next Theorem establishes that the convergence rate of training this deep (finite width) network depends on the decomposition of the target values $\mathbf{y}$ over the eigenvectors of $H^{\infty}$.

For any $\epsilon\in(0,1]$ and $\delta\in(0,O(\frac{1}{L})]$, let $\tau=\Theta(\frac{\epsilon\hat{\delta}}{n})$, $m\geq\Omega\left(\frac{n^{24}L^{12}\log^{5}m}{\delta^{8}\tau^{6}}\right)$, $\eta=\Theta\left(\frac{\delta}{n^{4}L^{2}m\tau^{2}}\right)$. Then, with probability of at least $1-\hat{\delta}$ over the random initialization after $t$ GD iterations we have that

The proof is provided in the supplementary material. Below, we give a brief proof sketch. First, we show that for any number of layers and at any iteration $t$ the following relation holds

where $H_{ij}(t)=\left<\frac{\partial f(\mathbf{x}_{i},\mathbf{w}(t))}{\partial\mathbf{w}},\frac{\partial f(\mathbf{x}_{j},\mathbf{w}(t))}{\partial\mathbf{w}}\right>,$ and the residual $\epsilon(t)$ due to the GD steps is relatively small. Then, based on several results due to (Allen-Zhu et al., 2019; Arora et al., 2019a), we show that $H(t)$ can be approximated by $H^{\infty}$, yielding, by applying recursion to (23)

where $\|\xi(t)\|\leq O(\epsilon)$. Next we show that under the setting of $\tau$, $\|\mathbf{u}^{(0)}\|\leq O(\epsilon)$. Finally, by applying the spectral decomposition to $H^{\infty}$ we obtain (50).

Finally, for data drawn from a non-uniform distribution the eigenfunctions of NTK for deep networks appear to be indistinguishable from those obtained for two-layer networks. Figure 3 shows a plot of the local frequencies obtained with NTK for a network of depth 10. It can be seen that the local frequencies are identical to those obtained with NTK for a two-layer network. The eigenvalues are similar to those obtained with the uniform density, up to a normalizing scale which depends on the distribution. Similarly to the two-layer case, learning a harmonic function of frequency $\kappa$ is therefore expected to require $O(\kappa^{d}/p^{*})$ iterations.

Conclusion

The main contribution of our work is to show that insights about neural networks that have been derived with the assumption of uniformly distributed training data also apply, in interesting ways, to more realistic, non-uniform data. Prior work has shown that the Neural Tangent Kernel provides a model of real, overparameterized neural networks that is tractable to analyze and that matches real experiments. Our work shows that NTK has a frequency bias for non-uniform data distributions as well as for uniform ones. This strengthens the case that this frequency bias may play an important role in real neural networks.

We also quantify this frequency bias. We derive an expression for the eigenfunctions of NTK, showing that for piecewise constant data distributions the eigenfunctions consist of piecewise harmonic functions. The frequency of these piecewise functions increases linearly with the square root of the local density of the data. As a consequence, for 1D inputs, networks modeled by NTK learn harmonic functions with a speed that increases quadratically in their frequency and decreases linearly with the local density. Experiments indicate that these results generalize naturally to higher dimensions. These results support the idea that overparameterized networks avoid overfitting because they fit target functions with smooth functions, and are slow to add high frequency components that could overfit.

Acknowledgements

This material is based partly 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. We would like to thank the Quantifying Ensemble Diversity for Robust Machine Learning (QED for RML) program from DARPA for their support of this project.

References

Appendix A Eigenfunctions of NTK for a two layer-network for data drawn from a piecewise constant distribution

Combining Eqs. (9) and (10) in the paper we have

Next, we simplify and rearrange. We omit dependence on $x$, note that $f(x-\pi)=f(x+\pi)$ and $p(x-\pi)=p(x+\pi)$ and respectively denote them by $\bar{f}$ and $\bar{p}$.

Assume next that $p(x)$ is constant around $x$ and $x-\pi$, so its derivatives at these points vanish. Then,

We next make the assumption that $p(x)$ has a period of $\pi$ (so $p=\bar{p}$) in which case $f(x+\pi)=-f(x)$ (i.e., $\bar{f}=-f$). These assumptions will be removed later. With these assumptions we have

It can be readily verified that this equation is solved by (25).

Finally, if $p(x)$ does not have a period of $\pi$ we can preprocess the data in a straightforward way to make $p$ have a period of $\pi$ (by mapping the interval $[0,4\pi)$ to $[0,2\pi)$) without changing the function that needs to be learned. ∎

Appendix B The amplitudes of the eigenfunctions in different regions

In this section for the NTK of a 2-layer network for which only the first layer is trained we compute bounds on the amplitudes of its eigenfunctions. We first bound the ratios between the amplitudes in two neighboring regions, and use this in the following section to bound the amplitude in any one region.

where $a_{j}\geq 0$. In this part we characterize the amplitudes the different regions $a_{j}$ for $j=1,...,l$.

We notice that the eigenfunctions appear to be continuous and differentiable. Without loss of generality, assume that the boundary between region $j$ to region $j+1$ happens at $x=0$. Then the eigenfunction in the vicinity of 0 is defined as follows:

These allow us to bound the ratio $a_{j}/a_{j+1}$. We have

On the other hand, from (28) we know that

WLOG assume that $p_{j+1}/p_{j}\geq 1$ then

For a lower bound note that the denominator in (31) satisfies

where the inequality is due to the assumption that $p_{j+1}\geq p_{j}$. Consequently, $(a_{j+1}/a_{j})^{2}\geq 1$. In summary, we have bounded the ratios between the amplitudes of neighboring regions by

We next note that these bounds are tight and are obtained in the following setup. Assume we have an even number of regions of constant density $l$ each with equal size. Suppose that in each region the eigenfunction includes an integer number of cycles. For each $q$ we construct an eigenfunction, by choosing a phase $b_{j}=0$ for $j=1,...,l$, and it holds that the border between region $l/2$ and $l/2+1$ lies at $x=0$. As a result, at this point we have

But since each region contains an integer number of cycles we get for $j=1,...,l$

As a result, for each $q$ we get one eigenfunction (up to a global scale)

We next construct a second eigenfunction for each $q$. Since there is an integer number of cycles in each region, to keep the second eigenfunction of each $q$ orthogonal to the first one, we choose a phase of $-\pi/2$:

Next, to maintain differentiability, the derivative at the border between regions $R_{j}$ and $R_{j+1}$ must be equal. So at $x=2\pi j/l-\pi$ we have for $j=1,...,l-1$

And we can choose for the second eigenfunction for each $q$ (up to a global scale)

In Figure 13 we show an example for this setup.

Assuming $p(x)$ is constant in $l$ regions and that WLOG up to a global scale, the minimal amplitude is $a_{\min}=1$. Then for two neighboring regions $R_{j}$ and $R_{j+1}$ if $p_{j}\geq p_{j+1}\Rightarrow\frac{a_{j+1}}{a_{j}}\leq\sqrt{\frac{p_{j}}{p_{j+1}}}\leq\sqrt{\frac{p_{\max}}{p_{\min}}}$ and if $p_{j+1}\geq p_{j}$ $\Rightarrow\frac{a_{j}}{a_{j+1}}\geq 1\Rightarrow\frac{a_{j+1}}{a_{j}}\leq 1\leq\sqrt{\frac{p_{\max}}{p_{\min}}}$. As a result in each transition between two regions we have

Starting from a minimal amplitude of magnitude $1$. For $l$ regions there are no more than $l$ transitions so each amplitude is (loosely) bounded as follows

Next we bound the global scale factor. Let $s=\int_{-\pi}^{\pi}(f(x))^{2}dx$. Then we have that after normalizing the global scale factor

To simplify notation we denote the frequency of each region by $q_{j}=\frac{\sqrt{p_{j}}q}{Z}$. Then for $s$ we have:

So we get $s\geq\sum_{j=1}^{l}\frac{\pi}{l}-\frac{1}{2q_{j}}=\pi-\frac{1}{2}\sum_{j=1}^{l}\frac{1}{q_{j}}=\pi-\frac{1}{2}\sum_{j=1}^{l}\frac{Z}{\sqrt{p_{j}}q}$.

As a result all the amplitudes in an eigenfunction of order $q$ are bounded by

Appendix C Local convergence rate as a function of frequency

To derive the rate of convergence as a function of frequency and density we assume that $p(x)$ forms a piecewise-constant distribution (PCD) with a fixed number of pieces $l$ of equal sizes, $p(x)=p_{j}$ in $R_{j}$, ${1\leq j\leq l}$. Our proof will rely on a lemma that states informally that not too many eigenfunctions need to be taken into account for convergence – more precisely, only a number linear in $k$ and inversely linear in $\sqrt{p^{*}}$, where $p^{*}>0$ denotes the minimal density. Convergence rate is then determined by the eigenfunction with highest eigenvalue included in the approximation for $g(x)$.

Let $p(x)$ be PCD. For any $\epsilon>0$, there exist $n_{k}$ such that $\sum_{j={n_{k}+1}}^{\infty}g_{i}^{2}<\epsilon^{2}$, where $g_{i}=\int_{-\pi}^{\pi}v_{i}(x)g(x)p(x)dx$ and $n_{k}$ is bound as in (39) below.

Given a target function $g(x)=\cos(kx)$ and a basis function $v_{i}(x)=a(x)\cos(\frac{q_{i}\sqrt{p(x)}x}{Z}+b(x))$ where $q_{i}=\lfloor i/2\rfloor$. (We will assume $a=1$ for now.) Their inner product can be written as

where $q_{ij}=q_{i}\sqrt{p_{j}}/Z$ denotes the local frequency of $v_{i}(x)$ at $R_{j}$. Next, to derive a bound we will restrict our treatment to $q_{ij}\geq 2k$ (and by that bound $n_{k}$ from below). With this assumption we obtain

Let $p^{*}=\min_{j}p_{j}$ and let $q_{i}^{*}=q_{i}\sqrt{p^{*}}/Z$, $q_{i}^{*}$ denotes the frequency associated with the corresponding region (which is the lowest within $v_{i}$). Our requirement that $q_{ij}>2k$ for all $1\leq j\leq l$ implies that $q_{i}^{*}>2k$, and therefore

where we denote by $B=\sum_{j=1}^{l}a_{j}p_{j}$ and the equality on the right is obtained by plugging in the definition of $q_{i}^{*}$. Note that $\sum_{j=1}^{l}p_{j}=l/(2\pi)$ (since $1=\int_{-\pi}^{\pi}p(x)dx=\sum_{j=1}^{l}2\pi p_{j}/l$), implying that $B\leq la^{*}/(2\pi)$, where $a^{*}=\max_{j}a_{j}$ and $a^{*}$ is bounded by (36).

Next, for a given $\epsilon>0$ we wish to bound the sum $\sum_{i=n_{k}}^{\infty}g_{i}^{2}$ by starting from a sufficiently high index $n_{k}$, i.e.,

By the definition of $q_{i}$, $n_{k}\geq 2q_{n_{k}}$, so

Let $n_{k}$ be chosen as in Lemma 2 with $\epsilon=\delta/2$, i.e.

Using (Arora et al., 2019b)’s Theorem 4.1 adapted to continuous operators

Assuming $k/l$ is integer then $\sin\left(\frac{2\pi k}{l}\right)=0$ and $\cos\left(\frac{2\pi k}{l}\right)=1$, so

In principle in every region $R_{j}$ we should have $|d_{j}|\leq\sqrt{p_{j}}/(2Z)$. Since

Appendix D Spectral convergence analysis for deep networks - proof of Theorem 2

where $\sigma$ stands for element wise RELU activation function. For a tuple $W=(W_{1},...,W_{L})$ of matrices, we let $\left\lVert W\right\rVert_{2}=\max_{l\in[L]}\left\lVert W_{l}\right\rVert_{2}$ and $\left\lVert W\right\rVert_{F}=(\sum_{l=1}^{L}\left\lVert W_{l}\right\rVert_{F}^{2})^{1/2}$.

The parameters are initialized randomly from a normal distribution according to

where similarly to (Allen-Zhu et al., 2019) the layers $A$ and $B$ are initialized and held fixed.

The network functionality is summarized as follows

We write the eigen-decomposition of $H^{\infty}=\sum_{i=1}^{n}\lambda_{i}\mathbf{v}_{i}\mathbf{v}_{i}^{T}$, where $\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$ are the eigenvectors of $H^{\infty}$ and $\lambda_{1},\ldots,\lambda_{n}$ are their corresponding eigenvalues. The minimal eigenvalue is denoted by $\lambda_{0}=\min(\lambda(H^{\infty}))$.

For any $\epsilon\in(0,1]$ and $\delta\in(0,O(\frac{1}{L})]$, let $\tau=\Theta(\frac{\epsilon\hat{\delta}}{n})$, $m\geq\Omega\left(\frac{n^{24}L^{12}\log^{5}m}{\delta^{8}\tau^{6}}\right)$, $\eta=\Theta\left(\frac{\delta}{n^{4}L^{2}m\tau^{2}}\right)$. Then, with probability of at least $1-\hat{\delta}$ over the random initialization after $t$ iterations of GD we have that

D.2 Proof strategy

The proof of Thm. 4 relies on a theorem, provided by (Allen-Zhu et al., 2019), stated in Thm. 5, and an observation, based the on the derivation of the proof to that theorem, which we state in Lemma 4.

Thm. 5 assumes that the data is normalized, so that $\left\lVert\mathbf{x}_{i}\right\rVert=1$, and there exists $\delta\in(0,O(\frac{1}{L})]$ such that for every pair $i,j\in[n]$, we have $\left\lVert\mathbf{x}_{i}-\mathbf{x}_{j}\right\rVert\geq\delta$ and also it holds that $\left|y_{i}\right\rvert\leq O(1)$.

In addition, we prove Lemma 3, which is the basis for the proof of our Theorem.

Suppose $\delta\in(0,O(\frac{1}{L})]$, $m\geq\Omega\left(\frac{n^{24}L^{12}\log^{5}m}{\delta^{8}\tau^{2}}\right)$, $\eta=\Theta\left(\frac{\delta}{n^{4}L^{2}m\tau^{2}}\right)$ and also let $\omega=O(\frac{n^{3}\log m}{\delta\tau\sqrt{m}})$. Then, with probability at least $1-e^{-\Omega(m\omega^{2/3}L)}$ over the randomness of $A,B$ and $W^{(0)}$ we have

The proof of the Lemma is deferred, and will be given after the proof of the theorem.

D.3 Proof of Thm 4

By Lemma 3 we have the following relation

Adding and subtracting $\eta H^{\infty}(\mathbf{u}(t-1)-\mathbf{y})$ we have

where we denote $\xi(t)=\eta(H^{\infty}-H(t))(\mathbf{u}(t)-\mathbf{y})+\epsilon(t)$. Then, by applying (52) recursively, we obtain

We first bound the quantity $\left\lVert\xi(t-1-i)\right\rVert_{2}$

Using Lemma 14 which states that $\left\lVert H(t)-H^{\infty}\right\rVert_{2}\leq O(\frac{\delta^{2}m\tau^{3}}{n^{6}})$.

Using the bound in Lemma 3, for $\epsilon(t-1-i)$

Using bound over the loss by, Lemma 4 (b).

By Lemma 11 the loss at initialization is bounded by $O(n)$.

Using the bound, derived above, (53) yields

$\left\lVert I-\eta H^{\infty}\right\rVert_{2}$ is bounded by the maximal eigenvalue of the positive definite matrix $(I-\eta H^{\infty})$, i.e, $(1-\eta\lambda_{0})$.

$(1-\eta\lambda_{0})^{i}\left(1-\Omega\left(\frac{\tau^{2}\eta\delta m}{n^{2}}\right)\right)^{\frac{(t-1-i)}{2}}\leq 1$

By Theorem 5, $t\leq O(\frac{n^{6}L^{2}}{\delta^{2}})$

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

For the first term we use lemma 11 which states that $\left\lVert\mathbf{u}(0)\right\rVert\leq\frac{\sqrt{n}\tau}{\hat{\delta}}$, and by our choice of $\tau$ we obtain

Finally, by our choice of $\eta,m,\tau$ it holds that

D.4 Supporting Lemmas

We denote $-\eta\nabla\Phi(W^{(t)})$ by $W^{\prime}=(W_{1}^{{}^{\prime}},...,W_{L}^{{}^{\prime}})$, yielding

Now, we derive a bound for $\left|\epsilon_{i}(t)\right\rvert$. We start by subtracting and adding the same term, yielding

To construct the bound for $\left|\epsilon_{i}(t)\right\rvert$, we separately bound each of the above two terms. For the first term

We subtract and add the same term, use triangle inequality and the result provided in Lemma 10, $\left\lVert h_{i,l-1}^{(t+1)}\right\rVert=O(1)$.

Subtract and add $D_{i,l}^{(0)}$ from each coefficient that multiply $W_{l}^{(t)}$.

Due to Lemma 4, it holds that $||W^{(t)}-W^{(0)}||\leq\omega$. This enables us to use Lemma 6, implying that $\|D_{i,l}^{(t)}-D_{i,l}^{(0)}\|_{0}\leq s=O(m\omega^{2/3}L)$. Moreover, in conjunction with Lemma 5, this yields $\left\lVert D_{i,l}^{(t)}+D_{i,l}^{\prime\prime}-D_{i,l}^{(0)}\right\rVert_{0}\leq s$. Having that, we can apply Lemma 7, to obtain a bound for the first term.

As in the previous derivation, using Lemma 7.

Plug in $\omega=\frac{n^{3}\log m}{\delta\tau\sqrt{m}}$.

Since $W^{\prime}=-\eta\nabla\Phi(W^{(t)})$, we can get a bound for $\left\lVert W^{\prime}\right\rVert_{2}$ using Lemma 9, yielding $\left\lVert W^{\prime}\right\rVert_{2}\leq\eta O(\tau\sqrt{nm}\sqrt{\Phi(W^{(t)})})$.

Taking into account the two bounds, and summing over the all layers and data points we obtain that

Using our choice of $\eta$ and the value of $\omega$, we finally get

For any $\epsilon\in(0,1]$ and $\delta\in(0,O(\frac{1}{L})]$, let $m\geq\Omega\left(\frac{n^{24}L^{12}\log^{5}m}{\delta^{8}\tau^{2}}\right)$, $\eta=\Theta\left(\frac{\delta}{n^{4}L^{2}m\tau^{2}}\right)$ and $W^{(0)},A,B$ are at random initialization (49). Then, starting from Gaussian initialization, with probability at least $1-e^{-\Omega(log^{2}m)}$, gradient descent with learning rate $\eta$ achieves

Under the assumptions of Thm. 5, it holds that for every $t=0,1,..,T-1$

Furthermore we have $\left\lVert h^{(t+1)}_{i,l}-h^{(t)}_{i,l}\right\rVert\leq O(L^{1.5})\left\lVert W^{\prime}\right\rVert_{2}$ and $\left\lVert Bh^{(t+1)}_{i,l}-Bh^{(t)}_{i,l}\right\rVert\leq O(L\tau\sqrt{m})\left\lVert W^{\prime}\right\rVert_{2}$ and $\left\lVert D_{i,l}^{\prime\prime}\right\rVert_{0}\leq O(m\omega^{2/3}L)$

(This Lemma follows Lemma 8.2 from (Allen-Zhu et al., 2019)) Suppose $\omega\leq\frac{1}{CL^{9/2}log^{3}m}$ for some sufficiently large constant $C>1$. With probability at least $1-e^{-\Omega(m\omega^{2/3}L)}$ for every $(W^{(t)}-W^{(0)})$ satisfying $\left\lVert W^{(t)}-W^{(0)}\right\rVert_{2}\leq\omega$,

(This Lemma follows Lemma 8.7 from (Allen-Zhu et al., 2019)) For $s=O(mw^{2/3}L)$, with probability at least $1-e^{-\Omega(s\log m)}$ over the randomness of $W^{(0)},A,B$

for every diagonal matrices $D_{i,0}^{\prime\prime\prime},\cdots,D_{i,L}^{\prime\prime\prime}\in^{m\times m}$ with at most s non-zero entries

it holds $\left\lVert B(D_{i,L}^{(0)}+D^{\prime\prime\prime}_{i,L})(W_{L}^{(0)}+W_{L}^{\prime\prime})\cdots(W_{a+1}^{(0)}+W_{a+1}^{\prime\prime})(D_{i,a}^{(0)}+D^{\prime\prime\prime}_{i,a})-BD_{i,L}^{(0)}W_{L}^{(0)}\cdots W_{a+1}^{(0)}D_{i,a}^{(0)}\right\rVert_{2}\leq O(\tau\omega^{1/3}L^{2}\sqrt{m\log m})$

(This Lemma follows Lemma 7.4b from (Allen-Zhu et al., 2019)) Suppose $m\geq\Omega(nL\log(nL)).$ If $s=O(m\omega^{2/3}L)$ then with probability at least $1-e^{-\Omega(s\log m)}$ for all $i\in[n],a\in[L+1]$ it holds that $\left\lVert v^{T}BD_{i,L}^{(0)}W_{L}^{(0)}\cdots D_{i,a}^{(0)}W_{a}^{(0)}\right\rVert\leq O(\tau\sqrt{m})\left\lVert v\right\rVert$.

(This Lemma follows Theorem 3 from (Allen-Zhu et al., 2019)) Let $\omega=O(\frac{\delta^{3/2}}{n^{9/2}L^{6}\log^{3}m})$. With probability at least $1-e^{-\Omega(m\omega^{2/3}L)}$ over the randomness of $W^{0},A,B$, it satisfies for every $l\in[L]$ and $W$ with $\left\lVert W-W^{(0)}\right\rVert_{2}\leq\omega$ that

(This Lemma is based on Lemma 7.1 and Lemma 8.2c from (Allen-Zhu et al., 2019)) With high probability over the randomness of $A,W$ we have

Let $\delta>0$ and $m\geq\Omega(L\log(nL/\delta)$ then with probability at least $1-\delta$ it holds that $||u(0)||\leq\sqrt{n}\tau/\delta$ and as a consequence by using the triangle inequality $\Phi(W(0))=\frac{1}{2}\left\lVert\mathbf{y}-\mathbf{u}(0)\right\rVert^{2}\leq O(n)$

Conditioned on $W,A$ it holds that $u_{i}(0)\backsim N(0,\tau^{2}\left\lVert h_{i,L}\right\rVert^{2})$ and since by Lemma 10 we have that $\left\lVert h_{i,L}\right\rVert=O(1)$, this yields $E(\left\lVert\mathbf{u}(0)\right\rVert^{2})=O\left(n\tau^{2}\right)$. Then by Markov’s inequality, $\left\lVert\mathbf{u}(0)\right\rVert^{2}\leq n\tau^{2}/\delta^{2}$ with probability $1-\delta$. ∎

(Based on Theorem 3.1 (Arora et al., 2019a))The formulation given in (Arora et al., 2019a) considers training w.r.t all layers. The proof can be extended trivially to the case where the first and last layers are held fixed. Fix $\epsilon>0$ and $\delta\in(0,1)$ and assume $m\geq\Omega(\frac{L^{6}}{\epsilon^{4}}log(\frac{L}{\delta}))$. Then for any pair of inputs $\mathbf{x}_{i},\mathbf{x}_{j}$ such that $\|\mathbf{x}_{i}\|\leq 1,\|\mathbf{x}_{j}\|\leq 1$ with probability $1-\delta$ we have

(Based on Theorem 5c (Allen-Zhu et al., 2019)) Let $W^{(0)},A,B$ be at random initialization. For any pair of inputs $\mathbf{x}_{i},\mathbf{x}_{j}$ and parameter $\omega\leq O(\frac{1}{L^{9}log^{3/2}m})$ with probability at least $1-e^{-\Omega(m\omega^{2/3}L)}$ over $W^{(0)},A,B$ with $\left\lVert W^{(0)}-W^{(t)}\right\rVert_{2}\leq\omega$ we have

Let $\hat{\delta}\in(0,1]$ and $W^{(0)},A,B$ be at random initialization. Then, for $m\geq\Omega\left(\frac{n^{24}L^{12}\log^{5}m}{\delta^{8}\tau^{6}}\right)$ and parameter $\omega=O\left(\frac{n^{3}}{\delta\tau\sqrt{m}}\log m\right)$ with probability of at least $1-\hat{\delta}$ over $W^{(0)},A,B$ with $\left\lVert W^{(0)}-W^{(t)}\right\rVert_{2}\leq\omega$ it holds that

$\left\lVert H(t)-H(0)\right\rVert_{2}\leq O(\frac{n^{3}log^{5/6}m}{\delta\tau})m^{5/6}$

$\left\lVert H(0)-H^{\infty}\right\rVert_{2}\leq O(\frac{\delta^{2}m\tau^{3}}{n^{6}})$

$\left\lVert H^{\infty}-H(t)\right\rVert_{2}\leq O(\frac{n^{3}log^{5/6}m}{\delta\tau})m^{5/6}+O(\frac{\delta^{2}m\tau^{3}}{n^{6}})\leq O(\frac{\delta^{2}m\tau^{3}}{n^{6}})$

We prove the first claim. Then, the second claim is obtained by plugging $m$ into Lemma 12. The third claim is a direct consequence of the two claims using triangle inequality.

By the definition of $H_{ij}(0)$ we have that

where the last inequality is obtained by applying Lemma 8 and Lemma 10. Applying the obtained bound for $H_{ii}(0)$ and $H_{jj}(0)$ yields a bound for $\left|H_{ij}(t)-H_{ij}(0)\right\rvert$, using (58). Finally, $\left\lVert H(t)-H(0)\right\rVert\leq O(\frac{n^{3}log^{5/6}m}{\delta\tau})m^{5/6}$. ∎

Appendix E Experiment setup

Below we provide our experimental setup for all the figures in the paper.

Figure 7. Convergence times are measured by training a two-layer network with bias. The weights of the second layer are set randomly to $-1$ or $1$ (with probability $0.5$) and remain fixed throughout training. The bias is initialized to zero. The network parameters are set to $m=4000$, $\eta=0.004$, $n=734$, and $\tau=0.2$. Convergence for region $R_{j}$ is declared when $\frac{1}{2\left|R_{j}\right\rvert}\sum_{i\in R_{j}}^{n}\left(f(x_{i};w)-u_{i}\right)^{2}<\frac{\delta}{n}$ with $\delta=0.05$.

Figure 9. We used the same setup as in Figure 7 with the parameters: $m=8000$, $tau=0.2$, and $\eta=0.004$. Here $n$ varies between the three plots. We sampled 300 points from a uniform distribution on one hemisphere, and $300p_{2}/p_{1}$ points on the other hemisphere, where $p_{2}/p_{1}\in\{2,3,4\}$.