Title: ON THE SPECTRAL BIAS OF NEURAL NETWORKS

Abstract: Neural networks are known to be a class of highly expressive functions able to fit even random input-output mappings with 100% accuracy. In this work we present properties of neural networks that complement this aspect of expressivity. By using tools from Fourier analysis, we show that deep ReLU networks are biased towards low frequency functions, meaning that they cannot have local fluctuations without affecting their global behavior. Intuitively, this property is in line with the observation that over-parameterized networks find simple patterns that generalize across data samples. We also investigate how the shape of the data manifold affects expressivity by showing evidence that learning high frequencies gets easier with increasing manifold complexity, and present a theoretical understanding of this behavior. Finally, we study the robustness of the frequency components with respect to parameter perturbation, to develop the intuition that the parameters must be finely tuned to express high frequency functions.

1. INTRODUCTION:

While universal approximation properties of neural networks have been known since the early 90s (Hornik et al., 1989; Cybenko, 1989; Leshno et al., 1993; Barron, 1993) , recent research has shed light on the mechanisms underlying such expressivity (Montufar et al., 2014; Raghu et al., 2016; Poole et al., 2016) . At the same time, deep neural networks, despite being massively overparameterized, have been remarkably successful at generalizing to natural data. This fact is at odds with the traditional notions of model complexity and their empirically demonstrated ability to fit arbitrary random data to perfect accuracy (Zhang et al., 2017a; Arpit et al., 2017) . It has prompted the recent investigations of possible implicit regularization mechanisms inherent in the learning process, inducing biases towards low complexity solutions (Soudry et al., 2017; Poggio et al., 2018; Neyshabur et al., 2017) .

In this work, our main goal is to expose one such bias by taking a closer look at neural networks through the lens of Fourier analysis1 . We focus the discussion on ReLU networks, whose piecewise linear structure enables an analytic treatment. While they can approximate arbitrary functions, we find that these networks favour low frequency ones; in other words, they exhibit a bias towards smooth functions, a phenomenon we call the spectral bias2 . We find that this bias manifests itself not just in the process of learning, but also in the parameterization of the model itself: in fact we show that the lower frequencies of trained networks are more robust with respect to random parameter perturbations. Finally, we also exhibit and analyze a rather intricate interplay between the spectral bias and the geometry of the data manifold: we show that high frequencies get easier to learn when the data lies on a lower dimensional manifold of complex shape embedded in the input space. CONTRIBUTIONS 1. We exploit the piecewise-linear structure of ReLU networks to evaluate and bound its Fourier spectrum.

2. We demonstrate the peculiar behaviour of neural networks with illustrative and minimal experiments and find evidence of a spectral bias: i.e. lower frequencies are learned first.

3. We illustrate how the manifold hypothesis adds a layer of subtlety by showing how the geometry of the data manifold attenuates the spectral bias in a non-trivial way. We present a theoretical analysis of this phenomenon and derive conditions on the manifolds that facilitate learning higher frequencies.

4. Given a trained network, we investigate the relative robustness of the lower frequencies with respect to random perturbations of the network parameters.

The paper is organized as follows. In Section 2, we derive the Fourier spectrum of deep ReLU networks. Section 3 presents minimal experiments that demonstrate the spectral bias of ReLU networks. In Section 4, we study and discuss the role of the geometry of the data manifold. In Section 5, we empirically illustrate and theoretically explain our robustness result.

2. FOURIER ANALYSIS OF RELU NETWORKS:



2.1. PRELIMINARIES:

Consider the class of scalar functions f : R d → R defined by a ReLU network with L hidden layers of widths d 1 , • • • d L and a single output neuron:

EQUATION

where each T (k) : R d k-1 → R d k is an affine function (d 0 = d and d L+1 = 1) and σ(u) i = max(0, u i ) denotes the ReLU activation function acting elementwise on a vector u = (u 1 , • • • u n ).

In the standard basis, T (k) (x) = W (k) x + b (k) for some weight matrix W (k) and bias vector b (k) .

ReLU networks are known to be continuous piece-wise linear (CPWL) functions, where the linear regions are convex polytopes (Raghu et al., 2016; Montufar et al., 2014; Zhang et al., 2018; Arora et al., 2018) . Remarkably, the converse is also true: every CPWL function can be represented by a ReLU network (Arora et al., 2018, Theorem 2.1) , which in turn endows ReLU networks with universal approximation properties. Given the ReLU network f from Eqn. 1, we can make the piecewise linearity explicit by writing,

EQUATION

where is an index for the linear regions P and 1 P is the indicator function on P . As shown in Appendix C in more detail, each region corresponds to an activation pattern3 of all hidden neurons of the network, which is a binary vector with components conditioned on the sign of the input of the respective neuron. The 1 × d matrix W is given by

EQUATION

where W (k) is obtained from the original weight W (k) by setting its j th column to zero whenever the neuron j of the k th layer is inactive.

We will henceforth assume that the input data lies in a bounded domain of R d , say X = [-A, A] d for some A > 0 and thus restrict ourselves to ReLU networks with bounded support4 .

2.2. FOURIER SPECTRUM:

In the following, we study the structure of ReLU networks in the Fourier domain, which is defined as:

f (x) = (2π) d/2 f (k) e ik•x dk, f (k) := f (x) e -ik•x dx (4)

where dx, dk are the uniform Lebesgue measure on R d and f denotes the Fourier transform of f (see Appendix B for a short recap of the Fourier transform). Lemmas 1 and 2 (proved in appendix D) yield the explicit form of the Fourier components. Lemma 1. The Fourier transform of ReLU networks decomposes as,

EQUATION

where k = k and 1P (k) = P e -ik•x dx is the Fourier transform of the indicator function of P .

The Fourier transform of a polytope appearing in Eqn. 5 is a fairly intricate mathematical object; Diaz et al. (2016) develop an elegant procedure for evaluating it in arbitrary dimensions via a recursive application of Stokes theorem. We describe this procedure in detail in Appendix D.2, and present here its main corollary.

Lemma 2. Let P be a full dimensional polytope in R d . The Fourier spectrum of its indicator function 1P satisfies the following:

| 1P (k)| = O 1 k ∆ (P ) k (6)

where

EQUATION

∆ (P )

k = j when k lies orthogonal to some (d -j)-dimensional face of P . Note that since a polytope has a finite number of facets (of any dimension), the k's for which ∆ (P ) k = j for some j < d lie on a finite union of j-dimensional subspaces of R d . The Lebesgue measure of all such lower dimensional subspaces for all such j equals 0, leading us to the conclusion that the spectrum decays as O(k -d ) for almost all directions k of the frequency vector k in R d .

Lemmas 1, 2 together yield the main result of this section. Given a ReLU network f , its linear regions form a cell decomposition of R d as union of polytopes; we denote by F the set of faces (of any dimension) of all such polytopes. For k ∈ R d , let ∆ k be the minimum integer 1 ≤ j ≤ d such that k lies orthogonal to some (d -j)-dimensional face in F. Theorem 1. The Fourier components of the ReLU network f satisfy the following:

| f (k)| = O N f L f k ∆ k +1 (7)

where N f is the number of linear regions and L f = max W 2 is the Lipschitz constant of f .

Several remarks are in order:

(a) The spectral decay of ReLU networks is highly anisotropic in large dimensions. In almost all directions k of R d , we have ∆ k = d, i.e. a O(k -d-1 ) decay. However, the decay can be as slow as O(k -2 ) in specific directions orthogonal to the facets bounding linear regions5 . As we prove in Appendix D.3, the Lipschitz constant L f can be bounded as,

EQUATION

)

where • is the spectral norm, W is the ravelled parameter vector of the network and • ∞ is the max-norm. This makes the bound on L f scale exponentially in depth and polynomial in width.

As for the number N f of linear regions, Montufar et al. (2014) and Raghu et al. (2016) obtain tight bounds that exhibit the same scaling behaviour (Raghu et al., 2016, Theorem 1) . This makes the overall bound in Eqn. 7 -and with it, the ability to express larger frequencies -scale exponentially in depth and polynomially in width6 . This result complements the well-known universal approximation property of neural networks by explicitly incorporating a control on the capacity7 of the network, namely the width, depth and the norm of parameters. Architecture dependent controls Gist: We find that even when higher frequencies have larger amplitudes, the model prioritizes learning lower frequencies first. We also find that the spectral norm of weights increases as the model fits higher frequency, which is what we expect from Theorem 1.

on approximation have been formalized in the literature through approximation bounds and depth separation results, see e.g Barron (1993) ; Telgarsky (2016) ; Eldan & Shamir (2016) .

(b) For a given architecture (i.e. fixed width and depth), the high frequency contributions of the network can be increased by increasing the norm of the parameters. Assuming the weight norm increases with training iterations, this suggests that the training of ReLU networks might be biased towards lower frequencies. We investigate this fact empirically in the next section.

3. LOWER FREQUENCIES ARE LEARNED FIRST:

In this section and the ones that follow, we present experiments that illustrate the peculiar behaviour of deep ReLU networks in the Fourier domain. We begin with an experiment to demonstrate that networks tend to fit lower frequencies first during training. We refer to this phenomenon as the spectral bias, and discuss it in light of the results of Section 2. Experiment 1. The setup is as follows8 : Given frequencies κ = (k 1 , k 2 , ...) with corresponding amplitudes α = (A 1 , A 2 , ...), and phases φ = (ϕ 1 , ϕ 2 , ...), we consider the mapping λ : [0, 1] → R given by λ(z)

EQUATION

A 6-layer deep 256-unit wide ReLU network f θ is trained to regress λ with κ = (5, 10, ..., 45, 50) and N = 200 input samples spaced equally over [0, 1]; its spectrum fθ (k) in expectation over ϕ i ∼ U (0, 2π) is monitored as training progresses. In the first setting, we set equal amplitude A i = 1 for all frequencies and in the second setting, the amplitude increases from A 1 = 0.1 to A 10 = 1. 

EQUATION

where the second equality follows from Plancherel theorem. We make two observations -first, the square error in input space translates into square error in Fourier domain, with a priori no structural bias towards any particular frequency component9 , i.e. all frequencies are weighted the same. Since the same cannot be said about e.g. cross-entropy loss, we use the MSE loss in most of our experiments to avoid a potential confounding factor. Second, the parameterization of the network can be exploited by considering the gradient of the MSE loss w.r.t. parameters,

EQUATION

where Re(z) denotes the real part of z. We find that a bias naturally emerges as a consequence of the spectral decay rate found in Theorem 1, in the sense that the magnitude of the residual | fθ (k)-λ(k)| contributes less to the net gradient for large k. This generalizes the argument made in Xu (2018) for two layer sigmoid networks by observing that the gradient w.r.t parameters of the network function inherits the spectral decay rate of the function itself10 . In Section 5, we use that the integral of fθ w.r.t. the standard measure in parameter space dθ also inherits the spectral decay rate of f to make a statement about the robustness of fθ (k) against random parameter perturbations.

4. NOT ALL MANIFOLDS ARE LEARNED EQUAL:

In this section, we investigate the subtleties that arise when the data lies on a lower dimensional manifold embedded in the higher dimensional input space of the model (Goodfellow et al., 2016) . We find that the shape of the data-manifold impacts the learnability of high frequencies in a nontrivial way. As we shall see, this is because low frequencies functions in the input space may have high frequency components when restricted to lower dimensional manifolds of complex shapes.

To systematically investigate the impact of manifold shape on the spectral bias, we demonstrate results in an illustrative minimal setting11 free from unwanted confounding factors. We also present a mathematical exposition of the relationship between the Fourier spectrum of the network, the spectrum of the target function defined on the manifold, and the geometry of the manifold itself. Manifold hypothesis. We consider the case where the data lies on a lower dimensional data manifold M ⊂ R d embedded in input space, which we assume to be the image γ([0, 1] m ) of some injective mapping γ : [0, 1] m → R d defined on a lower dimensional latent space [0, 1] m . Under this hypothesis and in the context of the standard regression problem, a target function τ : M → R defined on data manifold can identified with a function λ = τ • γ defined on the latent space.

Regressing τ is therefore equivalent to finding f : R d → R such that f • γ matches λ. Further, assuming that the data probability distribution µ supported on M is induced by γ from the uniform distribution U in the latent space [0, 1] m , the mean square error can be expressed as,

EQUATION

) Observe that there is a vast space of degenerate solutions f that minimize the mean squared errornamely all functions on R d that yield the same function when restricted to the data manifold M.

Our findings from the previous section suggest that neural networks are biased towards expressing a particular subset of such solutions, namely those that are low frequency. It is also worth noting that there exist methods that restrict the space of solutions: notably adversarial training (Goodfellow et al., 2014) and Mixup (Zhang et al., 2017b) .

Experimental set up. The experimental setting is designed to afford control over both the shape of the data manifold and the target function defined on it. We will consider the family of curves in R 2 generated by mappings γ

EQUATION

Here, γ L ([0, 1]) defines the data-manifold and corresponds to a flower-shaped curve with L petals, or a unit circle when L = 0 (see e.g. Fig 2 ). Given a signal λ : [0, 1] → R defined on the latent space [0, 1], the task entails learning a network f : R 2 → R such that f • γ L matches the signal λ.

Experiment 2. The set-up is similar to that of Experiment 1, and λ is as defined in Eqn. 9 with frequencies κ = (20, 40, ..., 180, 200) , and amplitudes Discussion. These experiments hint towards a rich interaction between the shape of the manifold and the effective difficulty of the learning task. The key technical reason underlying this phenomenon (as we formalize below) is that the relationship between frequency spectrum of the network f and that of the fit f • γ L is mediated by the embedding map γ L . In particular, we will argue that a given signal defined on the manifold is easier to fit when the coordinate functions of the manifold embedding itself has high frequency components. Thus, in our experimental setting, the same signal embedded in a flower with more petals can be captured with lower frequencies of the network.

A i = 1 ∀ i. The model f is trained on the dataset {γ L (z i ), λ(z i )} N i=1 with N = 1000 uniformly spaced samples z i between 0 and 1. The spectrum of f • γ L in expectation over ϕ i ∼ U (0,

To understand this mathematically, we address the following questions: given a target function λ, how small can the frequencies of a solution f be such that f • γ = λ? And further, how does this relate to the geometry of the data-manifold M induced by γ? To find out, we write the Fourier transform of the composite function,

EQUATION

The kernel P γ depends on only γ and elegantly encodes the correspondence between frequencies k ∈ R d in input space and frequencies l ∈ R m in the latent space [0, 1] m . Following a procedure from Bergner et al., we can further investigate the behaviour of the kernel in the regime where the stationary phase approximation is applicable, i.e. when l 2 + k 2 → ∞ (cf. section 3.2. of Bergner et al.) . In this regime, the integral P γ is dominated by critical points z of its phase, which satisfy

l = J γ (z) k (15) where J γ (z) ij = ∇ i γ j (z) is the m × d Jacobian matrix of γ.

Non-zero values of the kernel correspond to pairs (l, k) such that Eqn 15 has a solution. Further, given that the components of γ (i.e. its coordinate functions) are defined on an interval [0, 1] m , one can use their Fourier series representation together with Eqn 15 to obtain a condition on their frequencies (shown in appendix D.4). More precisely, we find that the i-th component of the RHS in Eqn 15 is proportional to pγ i [p]k i where p ∈ Z m is the frequency of the coordinate function γ i . This yields that we can get arbitrarily large frequencies l i if γi [p] is large13 enough for large p, even when k i is fixed. This is precisely what Experiments 2 and 3 demonstrate in a minimal setting. From Eqn 13, observe that the coordinate functions have a frequency mode at L. For increasing L, it is apparent that the frequency magnitudes l (in the latent space) that can be expressed with the same frequency k (in the input space) increases with increasing L. This allows the remarkable interpretation that the neural network function can express large frequencies on a manifold (l) with smaller frequencies w.r.t its input domain (k), provided that the coordinate functions of the data manifold embedding itself has high-frequency components14 .

5. LOWER FREQUENCIES ARE MORE ROBUST:

The goal of this section is to show that lower frequency components of trained networks are more robust than their higher frequency counterparts with respect to random perturbations in parameter space. More precisely, we observe that in the neighbourhood of a solution in parameter space, the high frequency components decay faster than the low frequency ones. This property does not directly depend on the training process, but rather on the parametrization of the trained model. We present empirical evidence and a theoretical explanation of this phenomenon. Experiment 4. The set up is the same as in Experiment 1, where λ is given by Eqn. 9. Training is performed for the frequencies κ = (10, 15, 20, ..., 45, 50) and amplitudes A i = 1 ∀ i. After convergence to θ * , we consider random (isotropic) perturbations θ = θ * + δ θ of given magnitude δ, where θ ∼ U (S dim(θ * ) ) is a unit vector. We evaluate the network function f θ at the perturbed parameters, and compute the magnitude of its discrete Fourier transform at frequencies k i , | fθ (k i )|. We also average over 100 samples of θ to obtain | fEθ (k i )|, which we normalize by | fθ * (k i )|. The result, shown in Figure 5 , demonstrate that higher frequencies are significantly less robust than the lower ones.

Discussion. The interpretation is as follows: parameters that contribute towards expressing highfrequency components occupy a small volume in the parameter space. To formalize this intuition, given a bounded domain Θ of parameter space, let us define,

Ξ (k) = {θ ∈ Θ|∃k , k > k, | fθ (k )| > }

to be the set of parameters such that f θ has Fourier components larger than for some k with larger norm than k. Then the following Proposition holds (proved in appendix E). Proposition 1. The volume ratio,

EQUATION

inherits the spectral decay rate of | fθ (k)|, given by Theorem 1.

Intuitively, expressing larger frequencies requires the parameters to be finely-tuned to work together.

6. RELATED WORK:

While we focus on showing the spectral bias of deep ReLU networks towards learning functions with dominant lower frequency components, most of existing work has focused on showing that in theory, these networks are capable of learning arbitrarily complex functions. Hornik et al. (1989) ; Cybenko (1989) ; Leshno et al. (1993) have shown that neural networks can be universal approximators when given sufficient width; more recently, Lu et al. (2017) proved that this property holds also for width-bounded networks. Montufar et al. (2014) showed that the number of linear regions of deep ReLU networks grows polynomially with width and exponentially with depth; Raghu et al. (2016) generalized this result and provided asymptotically tight bounds. There have been various results of the benefits of depth for efficient approximation (Poole et al., 2016; Telgarsky, 2016; Eldan & Shamir, 2016) . These analysis on the expressive power of deep neural networks can in part explain why over-parameterized networks can perfectly learn random input-output mappings (Zhang et al., 2017a) . Our Fourier analysis of deep ReLU networks also reflects the width and depth dependence of their expressivity, but more interestingly reveals their spectral bias towards learning simple functions. Thus our work may be seen as a formalization of the findings of Arpit et al. (2017) , where it is empirically shown that deep networks prioritize learning simple functions during training.

A few other works studied neural networks through the lens of harmonic analysis. For example, Candès (1999) used the ridgelet transform to build constructive procedures for approximating a given function by neural networks, in the case of oscillatory activation functions. This approach has been recently generalized to unbounded activation functions by Sonoda & Murata (2017) . Eldan & Shamir (2016) use insights on the support of the Fourier spectrum of two-layer networks to derive a worse-case depth-separation result. Barron (1993) In light of our findings, it is worth comparing the case of neural networks and other popular algorithms such that kernel machines (KM) and K-nearest neighbor classifiers. We refer to the Appendix F for a detailed discussion and references. In summary, our discussion there suggests that 1. DNNs strike a good balance between function smoothness and expressivity/parameter-efficiency compared with KM; 2. DNNs learn a smoother function compared with KNNs since the spectrum of the DNN decays faster compared with KNNs in the experiments shown there.

7. CONCLUSION:

We studied deep ReLU networks through the lens of Fourier analysis. Several conclusions can be drawn from our analysis. While neural networks can approximate arbitrary functions, we find that they favour low frequency ones -hence they exhibit a bias towards smooth functions -a phenomenon that we called spectral bias. We also illustrated how the geometry of the data manifold impacts expressivity in a non-trivial way, as high frequency functions defined on complex manifolds can be expressed by lower frequency network functions defined in input space. Finally, we found that the parameters contributing towards expressing lower frequencies are more robust to random perturbations than their higher frequency counterparts.

We view future work that explore the properties of neural networks in Fourier domain as promising. For example, the Fourier transform affords a natural way of measuring how fast a function can change within a small neighborhood in its input domain ; as such, it is a strong candidate for quantifying and analyzing the sensitivity of a model -which in turn provides a natural measure of complexity (Novak et al., 2018) . We hope to encourage more research in this direction. We fit a 6 layer ReLU network with 256 units per layer f θ to the target function λ, which is a superposition of sine waves with increasing frequencies:

λ : [0, 1] → R, λ(z) = i A i sin(2πk i z + ϕ i )

where k i = (5, 10, 15, ..., 50), and ϕ i is sampled from the uniform distribution U (0, 2π). In the first setting, we set equal amplitude for all frequencies, i.e. A i = 1 ∀ i, while in the second setting we assign larger amplitudes to the higher frequencies, i.e. A i = (0.1, 0.2, ..., 1). We sample λ on 200 uniformly spaced points in [0, 1] and train the network for 80000 steps of full-batch gradient descent with Adam (Kingma & Ba, 2014). Note that we do not use stochastic gradient descent to avoid the stochasticity in parameter updates as a confounding factor. We evaluate the network on the same 200 point grid every 100 training steps and compute the magnitude of its (single-sided) discrete fourier transform at frequencies k i which we denote with | fki |. Finally, we plot in figure 1 the normalized magnitudes

| fk i |

Ai averaged over 10 runs (with different sets of sampled phases ϕ i ). We also record the spectral norms of the weights at each layer as the training progresses, which we plot in figure 1 for both settings (the spectral norm is evaluated with 10 power iterations). In figure 6, we show an example target function and the predictions of the network trained on it (over the iterations), and in figure 7 we plot the loss curves.

A.2 EXPERIMENT 2:

We use the same 6-layer deep 256-unit wide network and define the target function where k i = (20, 40, ..., 180, 200), A i = 1 ∀ i and ϕ ∼ U (0, 2π). We sample φ on a grid with 1000 uniformly spaced points between 0 and 1 and map it to the input domain via γ L to obtain a dataset {(γ L (z j ), λ(z j ))} 999 j=0 , on which we train the network with 50000 full-batch gradient descent steps of Adam. On the same 1000-point grid, we evaluate the magnitude of the (single-sided) discrete Fourier transform of f θ • γ L every 100 training steps at frequencies k i and average over 10 runs (each with a different set of sampled z i 's). We make the following observations. The above observations are all consistent with Theorem 1, and further show that lower frequencies are learned first (i.e. the spectral bias, cf. Experiment 1).

λ : D → R, z → λ(z) = i A i sin(2πk i z + ϕ i )

A.4 MNIST: A PROOF OF CONCEPT:

In the following experiment, we show that given two manifolds of the same dimension -one flat and the other not -the task of learning random labels is harder to solve if the input samples lie on the same manifold. We demonstrate on MNIST under the assumption that the manifold hypothesis is true, and use the fact that the spectrum of the target function we use (white noise) is constant in expectation, and therefore independent of the underlying coordinate system when defined on the manifold. Experiment 6. In this experiment, we investigate if it is easier to learn a signal on a more realistic data-manifold like that of MNIST (assuming the manifold hypothesis is true), and compare with a flat manifold of the same dimension. To that end, we use the 64-dimensional feature-space E of a denoising15 autoencoder as a proxy for the real data-manifold of unknown number of dimensions. The decoder functions as an embedding of E in the input space X = R 784 , which effectively amounts to training a network on the reconstructions of the autoencoder. For comparision, we use an injective embedding16 of a 64-dimensional hyperplane in X. This result complements the findings of Arpit et al. (2017) and Zhang et al. (2017a) , which show that it's easier to fit random labels to random inputs if the latter is defined on the full dimensional input space (i.e. the dimension of the flat manifold is the same as that of the input space, and not that of the underlying data-manifold being used for comparison). A.5 CIFAR-10: IT'S ALL CONNECTED

We have seen that deep neural networks are biased towards learning low frequency functions. This should have as a consequence that isolated bubbles of constant prediction are rare. This in turn implies that given any two points in the input space and a network function that predicts the same class for the said points, there should be a path connecting them such that the network prediction does not change along the path. In the following, we present an experiment where we use a path finding method to find such a path between all Cifar-10 input samples indeed exist. Experiment 7. Using AutoNEB Kolsbjerg et al. ( 2016), we construct paths between (adversarial) Cifar-10 images that are classified by a ResNet20 to be all of the same target class. AutoNEB bends a linear path between points in some space R m so that some maximum energy along the path is minimal. Here, the space is the input space of the neural network, i.e. the space of 32 × 32 × 3 images and the logit output of the ResNet20 for a given class is minimized. We construct paths between the following points in image space:

• From one training image to another,

• from a training image to an adversarial,

• from one adversarial to another.

We only consider pairs of images that belong to same class c (or, for adversarials, that originate from another class = c, but that the model classifies to be of the specified class c). For each class, we randomly select 50 training images and select a total of 50 random images from all other classes and generate adversarial samples from the latter. Then, paths between all pairs from the whole set of images are computed.

The AutoNEB parameters are chosen as follows: We run four NEB iterations with 10 steps of SGD with learning rate 0.001 and momentum 0.9. This computational budget is similar to that required to compute the adversarial samples. The gradient for each NEB step is computed to maximize the logit output of the ResNet-20 for the specified target class c. We use the formulation of NEB without springs Draxler et al. (2018) .

The result is very clear: We can find paths between all pairs of images for all CIFAR10 labels that do not cross a single decision boundary. This means that all paths belong to the same connected component regarding the output of the DNN. This holds for all possible combinations of images in the above list. Figure 15 shows connecting training to adversarial images and Figure 14 paths between pairs of adversarial images. Paths between training images are not shown, they provide no further insight. Note that the paths are strikingly simple: Visually, they are hard to distinguish from the linear interpolation. Quantitatively, they are essentially (but not exactly) linear, with an average length (3.0 ± 0.3)% longer than the linear connection.

B BRIEF RECAPITULATION OF FOURIER ANALYSIS:

The Fourier transform is a powerful mathematical tool used to represent functions as a weighted sum of oscillating functions, given that the function satisfies certain conditions. In the realm of signal processing and beyond, it is used to represent a time (space) domain signal f as a sum of sinusoids of various (spatial) frequencies k, where the weights are referred to as the Fourier coefficients f (k). "(cat)") that are classified as a particular class ("airplane") are connected to actual training samples from that class (left, "airplane") such that all samples along that path are also predicted by the network to be of the same class.

Let f : R n → R be a squared-integrable function17 , i.e. such that

x∈R n |f (x)| 2 dx is finite, or f ∈ L 2 (R n ).

With the Fourier inversion theorem, it holds:

EQUATION

Informally, equation 17 expresses the function f (x) as a weighted sum (the integral) of plane waves e ±ik•x of the angular wavenumber k, where the unit vector k gives the direction of the corresponding wave in n-D space and the magnitude k is inversely proportional to the wavelength. Equation 18gives the expression for f (k), which is called the Fourier transform or the Fourier spectrum or simply the spectrum of f . The 1 2π coefficient and sign in the exponential functions are matters of convention.

The asymptotic behaviour of f for k → ∞ is a measure of smoothness of f . In Bachmann-Landau or asymptotic notation18 , we say f = O(k -1 ) if for k → ∞, the function f decays at least as fast as

1 k . A function whose spectrum is O(k -2

) is in a sense smoother than one whose spectrum is O(k -1 ), while the spectrum of an infinitely differentiable (or smooth) function must decay faster than any rational function of k, assuming the function is integrable, i.e. the integral of its absolute value over its domain is finite (or the function is L 1 ). Intuitively, the higher-frequency oscillations in a smoother function must vanish faster. Formally, this is a straightforward consequence of the Riemann-Lebesgue lemma, stating that the spectrum of any L 1 function must vanish at infinity (potentially arbitrarily slowly), taken together with the well known property of the Fourier transform that it diagonalizes the differential operator i.e.

[ ∇ x f ](k) = k f (k).

C THE CONTINUOUS PIECEWISE LINEAR STRUCTURE OF DEEP RELU NETWORKS:

We consider the class of ReLU network functions f : R d → R defined by Eqn. 1. Following the terminology of Raghu et al. (2016); Montufar et al. (2014) , each linear region of the network then corresponds to a unique activation pattern, wherein each hidden neuron is assigned an activation variable ∈ {-1, 1}, conditioned on whether its input is positive or negative. ReLU networks can be explictly expressed as a sum over all possible activation patterns, as in the following lemma.

Lemma 3. Given L binary vectors (1) , • • • (L) with (k) ∈ {-1, 1} d k , let T (k) (k) : R d k-1 → R d k the affine function defined by T (k) (k) (u) i = (T (k) (u)) i if ( k ) i = 1,

and 0 otherwise. ReLU network functions, as defined in Eqn. 1, can be expressed as

EQUATION

where 1 P denotes the indicator function of the subset P ⊂ R d , and P f, is the polytope defined as the set of solutions of the following linear inequalities (for all k = 1, • • • , L):

( k ) i (T (k) • T (k-1) (k-1) • • • • • T (1) (1) )(x) i ≥ 0, i = 1, • • • d k (20)

f is therefore affine on each of the polytopes P f, , which finitely partition the input space R d to convex polytopes. Remarkably, the correspondence between ReLU networks and CPWL functions goes both ways: Arora et al. (2018) show that every CPWL function is be represented by a ReLU network, which in turn endows ReLU networks with the universal approximation property.

Finally, in the standard basis, each affine map

T (k) : R d k-1 → R d k is specified by a weight matrix W (k) ∈ R d k-1 × R d k and a bias vector b (k) ∈ R d k .

In the linear region P f, , f can be expressed as f (x) = W x + b , where in particular

EQUATION

where W (k) is obtained from W (k) by setting its jth column to zero whenever ( k ) j = -1.

D FOURIER ANALYSIS OF RELU NETWORKS:

D.1 PROOF OF LEMMA 1

Proof. The vector-valued function kf (x)e ik•x is continuous everywhere and has well-defined and continuous gradients almost everywhere. So by Stokes' theorem (see e.g Spivak ( 2018)), the integral of its divergence is a pure boundary term. Since we restricted to functions with compact support, the theorem yields

EQUATION

)

The integrand is (k

• (∇ x f )(x) -ik 2 f (x))e -ik•

x , so we deduce,

f (k) = 1 -ik 2 k • (∇ x f )(x) e -ik•x (23)

Now, within each polytope of the decomposition (19), f is affine so its gradient is a constant vector, ∇ x f = W T , which gives the desired result (1). 1. If Proj F (k) = 0, then φ k (x) = Φ k is constant on F , and we have:

F = vol F (F )e iΦ k (24)

2. But if Proj F (k) = 0, then:

F = i G∈∂F Proj F (k) • N F (G) Proj F (k) 2 G(k) (25) D.2.2 DISCUSSION

The above theorem provides a recursive relation for computing the Fourier transform of an arbitrary polytope. More precisely, the Fourier transform of a m-dimensional polytope is expressed as a sum of fourier transforms over the m -1 dimensional boundaries of the said polytope (which are themselves polytopes) times a O(k -1 ) weight term (with k = k ). The recursion terminates if Proj F (k) = 0, which then yields a constant.

To structure this computation, Diaz et al. (2016) introduce a book-keeping device called the face poset of the polytope. It can be understood as a weighted tree diagram with polytopes of various dimensions as its nodes. We start at the root node which is the full dimensional polytope P (i.e. we initially set m = n). For all of the codimension-one boundary faces F of P , we then draw an edge from the root P to node F and weight it with a term given by:

EQUATION

and repeat the process iteratively for each F . Note that the weight term is O(k -1 ) where Proj F (k) = 0. This process yields tree paths T : P → F 1 → ... → F q where each F i+1 ∈ ∂F i has one dimension less than F i . For a given path and k, the terminal node for this path, F q , is the first polytope for which Proj Fq (k) = 0. The final Fourier transform is obtained by multiplying the weights along each path and summing over all tree paths:

EQUATION

)

where we wrote F 0 = P . Together with Lemma 1, this gives the closed form expression of the Fourier transform of ReLU networks.

For a generic vector k, all paths terminate at the zero-dimensional vertices of the original polytope, i.e. dim(F q ) = 0, implying the length of the path q equals the number of dimensions d, yielding a O(k -d ) spectrum. The exceptions occur if a path terminates prematurely, because k happens to lie orthogonal to some d -r-dimensional face F r in the path, in which case we are left with a O(k -r ) term (with r < d) which dominates asymptotically. Note that all vectors orthogonal to the d -r dimensional face F r lie on a r-dimensional subspace of R d . Since a polytope has a finite number of faces (of any dimension), the k's for which the Fourier transform is O(k

-r ) (instead of O(k -d ))

lies on a finite union of closed subspaces of dimension r (with r < d). The Lebesgue measure of all such lower dimensional subspaces for all such r is 0, leading us to the conclusion that the spectrum decays as O(k -d ) for almost all k's. We formalize this in the following corollary.

Corollary 1. Let P be a full dimensional polytope in R n . The Fourier spectrum of its indicator function 1P satisfies the following:

| 1P (k)| = O 1 k ∆ k (28)

where 1 ≤ ∆ k ≤ n, and ∆ k = j for k on a finite union of j-dimensional subspaces of R n .

D.3 PROOF OF THE LIPSCHTIZ BOUND:

Proposition 2. The Lipschitz constant L f of the ReLU network f is bound as follows (for all ):

EQUATION

Proof. The first equality is simply the fact that L f = max W , and the second inequality follows trivially from the parameterization of a ReLU network as a chain of function compositions 19 , together with the fact that the Lipschitz constant of the ReLU function is 1 (cf. Miyato et al. (2018) , equation 7). To see the third inequality, consider the definition of the spectral norm of a I × J matrix W :

W = max h =1 W h (30) Now, W h = i |w i • h|

, where w i is the i-th row of the weight matrix W and i = 1, ..., I.

Further, if h = 1, we have |w i • h| ≤ w i h = w i . Since w i = j |w ij | (with j = 1, ..., J) and |w ij | ≤ θ ∞ , we find that w i ≤ √ J θ ∞ . Consequently, i |w i • h| ≤ √

IJ θ ∞ and we obtain:

EQUATION

Now for W = W (k) , we have I = d k-1 and J = d k . In the product over k, every d k except the first and the last occur in pairs, which cancels the square root. For k = 1, d k-1 = d (for the d input neurons) and for k = L + 1, d k = 1 (for a single output neuron). The final inequality now follows.

D.4 THE FOURIER TRANSFORM OF A FUNCTION COMPOSITION:

Consider Equation 14. The general idea is to investigate the behaviour of P γ (l, k) for large frequencies l on manifold but smaller frequencies k in the input domain. In particular, we are interested in the regime where the stationary phase approximation is applicable to P γ , i.e. when l 2 +k 2 → ∞ (cf. section 3.2. of Bergner et al.) . In this regime, the integrand in P γ (k, l) oscillates fast enough such that the only constructive contribution originates from where the phase term u(z) = k • γ(z) -l • z does not change with changing z. This yields the condition that ∇ z u(z) = 0, which translates to the condition (with Einstein summation convention implied and

EQUATION

Now, we impose periodic boundary conditions20 on the components of γ, and without loss of generality we let the period be 2π. Further, we require that the manifold be contained in a box21 of some size in R d . The µ-th component γ µ can now be expressed as a Fourier series:

EQUATION

Equation 34 can be substituted in equation 32 to obtain:

EQUATION

where we have split k µ and l ν in to their magnitudes k and l and directions kν and lµ (respectively).

We are now interested in the conditions on γ under which the RHS can be large in magnitude, even when k is fixed. Recall that γ is constrained to a box -consequently, we can not arbitrarily scale up γµ . However, if γµ [p] decays slowly enough with increasing p, the RHS can be made arbitrarily large (for certain conditions on z, lµ and kν ).

E VOLUME IN PARAMETER SPACE AND PROOF OF PROPOSITION 1:

For a given neural network, we now show that the volume of the parameter space containing parameters that contribute -non-negligibly to frequency components of magnitude k above a certain cut-off k decays with increasing k. For notational simplicity and without loss of generality, we absorb the direction k of k in the respective mappings and only deal with the magnitude k.

Definition 1. Given a ReLU network f θ of fixed depth, width and weight clip K with parameter vector θ, an > 0 and Θ = B ∞ K (0) a L ∞ ball around 0, we define:

Ξ (k) = {θ ∈ Θ|∃k > k, | fθ (k )| > }

as the set of all parameters vectors θ ∈ Ξ (k) that contribute more than an in expressing one or more frequencies k above a cut-off frequency k.

Remark 1. If k 2 ≥ k 1 , we have Ξ (k 2 ) ⊆ Ξ (k 1 ) and consequently vol(Ξ (k 2 )) ≤ vol(Ξ (k 1 )),

where vol is the Lebesgue measure. 

F KERNEL MACHINES AND KNNS:

In this section, in light of our findings, we want to compare DNNs with K-nearest neighbor (k-NN) classifier and kernel machines which are also popular learning algorithms, but are, in contrast to DNNs, better understood theoretically.

F.1 KERNEL MACHINES VS DNNS:

Given that we study why DNNs are biased towards learning smooth functions, we note that kernel machines (KM) are also highly Lipschitz smooth (Eg. for Gaussian kernels all derivatives are bounded). However there are crutial differences between the two. While kernel machines can approximate any target function in principal (Hammer & Gersmann, 2003) , the number of Gaussian kernels needed scales linearly with the number of sign changes in the target function (Bengio et al., 2009) . Ma & Belkin (2017) have further shown that for smooth kernels, a target function cannot be approximated within precision in any polynomial of 1/ steps by gradient descent.

Deep networks on the other hand are also capable of approximating any target function (as shown by the universal approximation theorems Hornik et al. (1989) ; Cybenko (1989) ), but they are also parameter efficient in contrast to KM. For instance, we have seen that deep ReLU networks separate the input space into number of linear regions that grow polynomially in width of layers and exponentially in the depth of the network (Montufar et al., 2014; Raghu et al., 2016) . A similar result on the exponentially growing expressive power of networks in terms of their depth is also shown in (Poole et al., 2016) . In this paper we have further shown that DNNs are inherently biased towards lower frequency (smooth) functions over a finite parameter space. This suggests that DNNs strike a good balance between function smoothness and expressibility/parameter-efficiency compared with KM.

F.2 K-NN CLASSIFIER VS. DNN CLASSIFIER K-nearest neighbor (KNN) also has a historical importance as a classification algorithm due to its simplicity. It has been shown to be a consistent approximator Devroye et al. (1996) , i.e., asymptotically its empirical risk goes to zero as K → ∞ and K/N → 0, where N is the number of training samples. However, because it is a memory based algorithm, it is prohibitively slow for large datasets. Since the smoothness of a KNN prediction function is not well studied, we compare the smoothness between KNN and DNN. For various values of K, we train a KNN classifier on a k = 150 frequency signal (which is binarized) defined on the L = 20 manifold (see section 4), and extract probability predictions on a box interval in R 2 . On this interval, we evaluate the 2D FFT and integrate out the angular components to obtain ζ(k):

EQUATION

Finally, we plot ζ(k) for various K in figure 16e . Furthermore, we train a DNN on the very same dataset and overlay the radial spectrum of the resulting probability map on the same plot. We find that while DNN's are as expressive as a K = 1 KNN classifier at lower (radial) frequencies, the frequency spectrum of DNNs decay faster than KNN classifier for all values of K considered, indicating that the DNN is smoother than the KNNs considered. We also repeat the experiment corresponding to Fig. 4 with KNNs (see Fig. 16 ) for various K's, to find that unlike DNNs, KNNs do not necessarily perform better for larger L's, suggesting that KNNs do not exploit the geometry of the manifold like DNNs do. 

:

The Fourier transform affords a natural way of measuring how fast a function can change within a small neighborhood in its input of a model. See Appendix B for a brief recap of Fourier analysis.

A similar result has been independently found and reported inXu et al. (2018).

We adopt the terminology ofRaghu et al. (2016);Montufar et al. (2014).

Note that there is no loss of generality here: given any ReLU network f , its restriction f |X to X can always be extended to a continuous piece-wise linear function on R d with bounded support; this function, in turn, is representable by a ReLU network. This argument also shows that ReLU networks with bounded support are universal approximators of functions on X.

Note that such a rate is not guaranteed by piecewise smoothness alone. For instance, the function |x| is continuous and smooth everywhere except at x = 0, yet it decays as k -1.5 in the Fourier domain.

A qualitative ablation study can be found in Appendix A.3.

Note that the bound is relaxed with increasing capacity. In the limit of capacity to infinity, any constraint on universal approximation is dissolved.

More experimental details and additional plots are provided in Appendix A.1.

Note that the finite range in frequencies is due to sampling

Observe that the partial derivative w.r.t. θ can be swapped with the integrals in Eqn 4.

We include experiments on MNIST and CIFAR-10 in appendices A.4 and A.5.

We use Pytorch's BCEWithLogitsLoss. Internally, it takes a sigmoid of the network's output (the logits) before evaluating the cross-entropy.

Consider that the data-domain is bounded, implying that γ cannot be arbitrarily scaled.

Informally, we allow ourselves the intuition that it's easy for neural networks to fit wiggly functions if they are defined on wiggly manifolds.

This experiment yields the same result if variational autoencoders are used instead.

The xy-plane is R 3 an injective embedding of a subset of R 2 in R 3 .

On a formal note, the squared integrability is only required for the inverse Fourier transform to exist; for the forward transform, integrability is enough. Moreover, the Fourier transform can be generalized to tempered distributions, which allow for evaluating the Fourier coefficients of non-integrable e.g. non-zero constant functions.

Formally, f = O(g) =⇒ lim sup x→∞ f (x) g(x) < ∞.

Recall that the Lipschitz constant of a composition of two or more functions is the product of their respective Lipschtiz constants.

20 This is possible whenever γ is defined on a bounded domain, e.g. on[0, 1]

m . 21 This is equivalent to assuming that the data lies in a bounded set.

Note that in theorem 1, ∆ k depends only on the direction of k, which we absorb in the definition of ∆.

Figures and Tables:

Figure 1: Left (a, b): Evolution of the spectrum (x-axis for frequency) during training (y-axis). The colors show the measured amplitude of the network spectrum at the corresponding frequency, normalized by the target amplitude at the same frequency (i.e. | fk i |/Ai) and the colorbar is clipped between 0 and 1. Right (a, b): Evolution of the spectral norm (y-axis) of each layer during training (x-axis). Figure-set (a) shows the setting where all frequency components in the target function have the same amplitude, and (b) where higher frequencies have larger amplitudes.Gist: We find that even when higher frequencies have larger amplitudes, the model prioritizes learning lower frequencies first. We also find that the spectral norm of weights increases as the model fits higher frequency, which is what we expect from Theorem 1.

Figure 2: Functions learned by two identical networks (up to initialization) to classify the binarized value of a sine wave of frequency k = 200 defined on a γL=20 manifold. Both yield close to perfect accuracy for the samples defined on the manifold (scatter plot), yet they differ significantly elsewhere. The shaded regions show the predicted class (Red or Blue) whereas contours show the confidence (absolute value of logits).

Figure 3: (a,b,c,d): Evolution of the network spectrum (x-axis for frequency, colorbar for magnitude) duringtraining (y-axis) for the same target functions defined on manifolds γL for various L. Since the target function has amplitudes Ai = 1 for all frequencies ki plotted, the colorbar is clipped between 0 and 1. (e): Corresponding learning curves. Gist: Some manifolds (here with larger L) make it easier for the network to learn higher frequencies than others.

Figure 4: Heatmap of training accuracies of a network trained to predict the binarized value of a sine wave of given frequency (x-axis) defined on γL for various L (y-axis).

Figure5: Normalized spectrum of the model (x-axis for frequency, colorbar for magnitude) with perturbed parameters as a function of parameter perturbation (y-axis). The colormap is clipped between 0 and 1. Observe that the lower frequencies are more robust to parameter perturbations than the higher frequencies.

makes use of Fourier space properties of the target function to derive an architecture-dependent approximation bound. In a work done independently from ours, and made available online almost at the same time, Xu et al. (2018) make the same observation that lower frequencies are learned first. The subsequent work by Xu (2018) proposes a theoretical analysis of the phenomenon in the case of 2-layer networks with sigmoid activation, based on the spectrum of the sigmoid function.

Figure 6: The learnt function (green) overlayed on the target function (blue) as the training progresses. The target function is a superposition of sinusoids of frequencies κ = (5, 10, ..., 45, 50), equal amplitudes and randomly sampled phases.

Figure 7: Loss curves averaged over multiple runs. (cf. Experiment 1)

(a) Sampled δ-function at x = 0.5. (b) Constant Spectrum of the δ-function.

Figure 8: The target function used in Experiment 5.

Figure 9: Evolution with training iterations (y-axis) of the Fourier spectrum (x-axis for frequency, and colormap for magnitude) for a network with varying depth, width = 16 and weight clip = 10. The spectrum of the target function is a constant 0.005 for all frequencies.

Fig 3 shows the evolution of the spectrum as training progresses for L = 0, 4, 10, 16, and Fig 3e shows the corresponding loss curves. A.3 QUALITATIVE ABLATION OVER ARCHITECTURES Theorem 1 exposes the relationship between the fourier spectrum of a network and its depth, width and max-norm of parameters. The following experiment is a qualitative ablation study over these variables. Experiment 5. In this experiment, we fit various networks to the δ-function at x = 0.5 (see Fig 8a). Its spectrum is constant for all frequencies (Fig 8b), which makes it particularly useful for testing how well a given network can fit large frequencies. Fig 11 shows the ablation over weight clip (i.e. max parameter max-norm), Fig 9 over depth and Fig 10 over width. Fig 12 exemplarily shows how the network prediction evolves with training iterations. All networks are trained for 60K iterations of full-batch gradient descent under identical conditions (Adam optimizer with lr = 0.0003, no weight decay).

(a) Fig 9 shows that increasing the depth (for fixed width) significantly improves the network's ability to fit higher frequencies (note that the depth increases linearly). (b) Fig 10 shows that increasing the width (for fixed depth) also helps, but the effect is considerably weaker (note that the width increases exponentially). (c) Fig 11 shows that increasing the weight clip (or the max parameter max-norm) also helps the network fit higher frequencies.

Figure 10: Evolution with training iterations (y-axis) of the Fourier spectrum (x-axis for frequency, and colormap for magnitude) for a network with varying width, depth = 3 and weight clip = 10. The spectrum of the target function is a constant 0.005 for all frequencies.

Figure 11: Evolution with training iterations (y-axis) of the Fourier spectrum (x-axis for frequency, and colormap for magnitude) for a network with varying weight clip, depth = 6 and width = 64. The spectrum of the target function is a constant 0.005 for all frequencies.

Figure 12: Evolution with training iterations (y-axis) of the network prediction (x-axis for input, and colormap for predicted value) for a network with varying weight clip, depth = 6 and width = 64. The target function is a δ peak at x = 0.5.

The latter is equivalent to sampling 784-dimensional vectors from U ([0, 1]) and setting all but the first 64 components to zero. The target function is white-noise, sampled as scalars from the uniform distribution U ([0, 1]). Two identical networks are trained under identical conditions, and Fig 13 shows the resulting loss curves, each averaged over 10 runs.

Figure 13: Loss curves of two identical networks trained to regress white-noise under identical conditions, one on MNIST reconstructions from a DAE with 64 encoder features (blue), and the other on 64-dimensional random vectors (green).

Figure 14: Path between CIFAR-10 adversarial examples (e.g. "frog" and "automobile", such that all images are classified as "airplane").

airplane

Figure 15: Each row is a path through the image space from an adversarial sample (right) to a true training image (left). All images are classified by a ResNet-20 to be of the class of the training sample on the right with at least 95% softmax certainty. This experiment shows we can find a path from adversarial examples (right, Eg."(cat)") that are classified as a particular class ("airplane") are connected to actual training samples from that class (left, "airplane") such that all samples along that path are also predicted by the network to be of the same class.

FOURIER TRANSFORM OF POLYTOPES D.2.1 THEOREM 1 OF DIAZ ET AL. (2016) Let F be a m dimensional polytope in R d , such that 1 ≤ m ≤ d. Denote by k ∈ R d a vector in the Fourier space, by φ k (x) = -k • x the linear phase function, by F the Fourier transform of the indicator function on F , by ∂F the boundary of F and by vol m the m-dimensional (Hausdorff) measure. Let Proj F (k) be the orthogonal projection of k on to F (obtained by removing all components of k orthogonal to F ). Given a m -1 dimensional facet G of F , let N F (G) be the unit normal vector to G that points out of F . It then holds:

Let 1 k (θ) be the indicator function on Ξ (k). Then:∃ κ > 0 : ∀k ≥ κ, 1 k (θ) = 0 Proof. From theorem 1, we know that 22 | fθ (k)| = O(k -∆-1 ) for an integer 1 ≤ ∆ ≤ d. In the worse case where ∆ = 1, we have that ∃M < ∞ : | fθ (k)| < M k 2 . Now, simply select a κ > M such that M κ 2 < . This yields that | fθ (κ)| < M κ 2 < , and given that M κ 2 ≤ M k 2 ∀ k ≥ κ, we find | fθ (k)| < ∀ k ≥ κ. Now by definition 1, θ ∈ Ξ (κ), and since Ξ (k) ⊆ Ξ (κ) (see remark 1), we have θ ∈ Ξ (k), implying 1 k (θ) = 0 ∀ k ≥ κ. Remark 2. We have 1 k (θ) ≤ | fθ (k)| for large enough k (i.e. for k ≥ κ), since | fθ (k)| ≥ 0. Proposition 1. The relative volume of Ξ (k) w.r.t. Θ is O(k -∆-1 ) where 1 ≤ ∆ ≤ d.Proof. The volume is given by the integral over the indicator function, i.e. vol(Ξ (k)) = θ∈Θ 1 k (θ)dθ For a large enough k, we have from remark 2, the monotonicity of the Lebesgue integral and theorem 1 that: vol(Ξ (k)) = θ∈Θ 1 k (θ)dθ ≤ θ∈Θ | fθ (k)|dθ = O(k -d+∆-1 )vol(Θ) =⇒ vol(Ξ (k)) vol(Θ) = O(k -∆-1 )

Figure 16: (a,b,c,d): Heatmaps of training accuracies (L-vs-k) of KNNs for various K. When comparing with figure 4, note that the y-axis is flipped. (e): The frequency spectrum of KNNs with different values of K, and a DNN. The DNN learns a smoother function compared with the KNNs considered since the spectrum of the DNN decays faster compared with KNNs.

Peer review (iclr2019):
 Summary. This paper has theoretical and empirical contributions on topic of Fourier coefficients of neural networks. First is upper bound on Fourier coefficients in terms of number of affine pieces and Lipschitz constant of network. Second is collection of synthetic data and trained networks whereupon is argued that neural networks focus early effort upon low Fourier coefficients. Brief evaluation. Pros: + This paper attacks important and timely topic: identifying and analyzing implicit bias of neural networks paired with standard training methods. Cons: - "Implicit bias" hypothesis has been put forth by many authors for many years, and this paper does not provide compelling argument that Fourier coefficients provide good characterization of this bias. - Regarding "many authors for many years", this paper fails to cite and utilize vast body of prior work, as detailed below. - Main theorem here is loose upper bound primarily derived from prior work, and no lower bounds are given. Prior work does assess lower bounds. - Experiments are on synthetic data; prior work on implicit regularization does check real data. Detailed evaluation. * "Implicit bias" hypothesis appears in many places, for instance in work of Nati Srebro and colleagues ("The Implicit Bias of Gradient Descent on Separable Data" (and follow-ups), "Exploring generalization in deep learning" (and follow-ups), and others); it can also be found in variety of recent generalization papers, for instance again the work of Srebro et al, but also Bartlett et al, Arora et al. E.g., Arora et al do detailed analysis of favorable biases in order to obtain refined generalization bound. Consequently I expect this paper to argue to me, with strong theorems and experiments, that Fourier coefficients are a good way to assess implicit bias. * Theorem 1 is proved via bounds and tools on the Fourier spectra of indicators of polytopes due to Diaz et al, and linearity of the Fourier transform. It is only upper bound (indeed one that makes no effort to deal with cancellations and thus become tight). By contrast, the original proofs of depth separation for neural networks (e.g., Eldan and Shamir, or Telgarsky, both 2015), provide lower bounds and metric space separation. Indeed, the work of Eldan&Shamir extensively uses Fourier analysis, and the proof develops a refined understanding of why it is hard for a ReLU network to approximate a Fourier transform of even simple functions: it has to approximate exponentially many tubes in Fourier space, which it can only do with exponentially many pieces. While the present paper aims to cover some material not in Eldan&Shamir --- e.g., the bias with training --- this latter contribution is argued via synthetic data, and overall I feel the present work does not meet the (high) bar set by Eldan&Shamir. * I will also point out that prior work of Barron, his "superposition" paper from 1993, is not cited. That paper presents upper bounds on approximation with neural networks which depends on the Fourier transform. There is also follow-up by Arora et al with "Barron functions". * For experiments, I would really like to see experiment showing Fourier coefficients at various stages of training of standard network on standard data and standard data but with randomized labels (or different complexity in some other way). These Fourier coefficients could also be compared to other "implicit bias" quantities; e.g., various norms and complexity measures. In this way, it would be demonstrated that (a) spectral bias happens in practice, (b) spectral bias is a good way of measuring implicit bias. Admittedly, this is computationally expensive experiment. * Regarding my claim that Theorem 1 is "loose upper bound": the slope of each piece is being upper bounded by Lipschitz constant, which will be far off in most regions. Meanwhile, Lemma 1, "exact characterization", does not give any sense of how the slopes relate to weights of network. Improving either issue would need to deal with "cancellations" I mention, and this is where it is hard to get upper and lower bounds to match. I feel this paper could be made much stronger by carefully using the results of all this prior work; these are not merely citation omissions, but indeed there is good understanding and progress in these papers.