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. While universal approximation properties of neural networks have been known since the early 90s (Hornik et al., 1989; BID6 Leshno et al., 1993; BID2 , 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; BID1 . 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 analysis 1 . 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 bias 2 . 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. 1 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.2 A similar result has been independently found and reported in Xu et al. (2018). 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. 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: DISPLAYFORM0 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 |f ki |. Finally, we plot in figure 1 the normalized magnitudes |f k 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 FIG10 , 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. 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, BID8 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: DISPLAYFORM0 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: DISPLAYFORM1 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 function1 P satisfies the following: DISPLAYFORM2 where 1 ≤ ∆ k ≤ n, and ∆ k = j for k on a finite union of j-dimensional subspaces of R n .
We investigate ReLU networks in the Fourier domain and demonstrate peculiar behaviour. Fourier analysis of ReLU network, finding that they are biased towards learning low frequency  This paper has theoretical and empirical contributions on topic of Fourier coefficients of neural networks