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.
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.