Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks
Authors: Zhi-Qin John Xu
Yaoyu Zhang
Tao Luo
Yanyang Xiao
Zheng Ma
Venue:  (2020)
Keywords: deep learning
training behavior
Fourier analysis
generalization

Abstract: We study the training process of Deep Neural Networks (DNNs) from the Fourier analysis perspective. We demonstrate a very universal Frequency Principle (F-Principle) --- DNNs often fit target functions from low to high frequencies --- on high-dimensional benchmark datasets, such as MNIST/CIFAR10, and deep networks, such as VGG16. This F-Principle of DNNs is opposite to the learning behavior of most conventional iterative numerical schemes (e.g., Jacobi method), which exhibits faster convergence for higher frequencies, for various scientific computing problems. With a naive theory, we illustrate that this F-Principle results from the regularity of the commonly used activation functions. The F-Principle implies an implicit bias that DNNs tend to fit training data by a low-frequency function. This understanding provides an explanation of good generalization of DNNs on most real datasets and bad generalization of DNNs on parity function or randomized dataset.

Under review as a conference paper at ICLR 2020
FREQUENCY PRINCIPLE: FOURIER ANALYSIS SHEDS LIGHT ON DEEP NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We study the training process of Deep Neural Networks (DNNs) from the Fourier analysis perspective. We demonstrate a very universal Frequency Principle (F- (anciple)-DNN. DNNs often fit target functions from low to high frequencies high-dimensional benchmark datasets such as MNIST/CIFAR 10 and deep neural networks such as VGG16. This F-Principle of DNNS is opposite to the behavior most conventional iterative numerical schemes (c.g., Jacobi method), which exhibit faster convergence for higher frequencies for various scientific computing problems. With theories under an idealized setting, we illustrate that this F-Principle results from the smoothness/regulariyy of the commonly used activation functions. The F-Principle implies an implicit bias that DNNs tend to fit training data by low-frequency function. This understanding provides explanation of good generalization of DNNs on most real datasets and bad generalization of DNNs on parity function or a randomized dataset.
on
INTRODUCTION
Understanding the training process of Deep Neural Networks (DNNs) is fundamental problem in the area of deep learning. We find a common behavior of the gradient- based training process of DNNs, that is, Frequency Principle (F-Principle):
DNNs often fit target functions from low high frequencies during the training process.
In another word, at the early stage of training, the low-frequencies are fitted and as iteration steps of training increase, the high-frequed freueereqeesses are fitted. For example, when DNN is trained to fit y = sin(x) + sin(2x), its output would be close to sin(x) at early stage and as training goes on, its output would be close to sin(x:) + sin(2x). F-Principle was observed empirically in synthetic low-dimensional data with MSE loss during DNN training (Xu et al. 2018 Rahaman et al. 2018). However, in deep learning, empirical phenomena could vary from network structure another, from one dataset to another and could exhibit significant difference between synthetic data and high- dimensional real data. Therefore, the universality of the F-Principle remains important problem for further study. Especially for nigh-dimensiooal real problems, because the computational cost of nigh-dimensional Fourier transform is prohibitive in practice, it of great challenge demonstrate the F-Prncciple. On the other hand, the mechanism underlying the F-Principle and its implication to the application of DNNs, e.g., design of DNN-based PDE solver, as well as their generalization ability are also important open problems to be addressed.
In this work, we design two methods, i... projection and filtering methods, show that the F- Principle exists in the training process of DNNs for high-dimensional benchmarks, i.e., MNIST (LeCun) 1998), CIFAR1O (Krizhevsky et al. 2010). The settings we have considered are i) different DNN architectures, c.g., fully- fully-connected network, comvolutional neural network (CNN), and VGG16 (Simonyan & Zisserman| 2014); ii) different activation functions, e.g., tanh and rectified linear unit (ReLUU; lii) different loss functions, e.g., cross entropy, mean squared error (MSE), and loss energy functional in variational problems. These results demonstrate the universality of the F-Principle.
To facilitate the designs and applications of DNN-based schemes, characterize a stark difference between DNNs and conventional numerical schemes on various scientific computing problems, where opposite convergence behavior most of the conventional methods (e.g., Jacobi method) exhibit the

---

Under review as a conference paper at ICLR 2020
faster convergence for higher frequencies. This difference implies that DNN can be adopted to accelerate the convergence of low frequencies for computational problems.
We also intuitively explain with theories under an idcalized setting how the smoothness/regullrity of commonly used activation functions contributes to the F-Principle. Note that this mechanism is rigorously demonstrated for DNNs of general settings in subsequent work (Luo al. (019). Finally, we discuss that the F-Principle provides an understanding of good generalization of DNNs in many real datasets (Zhang et al. 2016) and poor generalization in learning the parity function (Shalev-Shwartz et al., 2017 Nye & Saxe 2018), that is, the E-Principle which implies that DNNs prefer low frequencies, consistent with the property of low frequencies dominance in many real datasets, e.g., MNIST/CIFARIO 10, but is different from the parity function whose spectrum concentrates on high frequencies. Compared with previous studies, our main contributions are as follows:
1. By designing both the projection and filtering methods, we consistently demonstrate the F- F-Principle for MNIST/CIFARIO over various architectures such as VGG16 and various loss functions.
2. For the application of solving differential equations, we show that (i) conventional numerical schemes learn higher frequencies faster whereas DNNs learn lower frequencies faster by the F- Principle, (ii) convergence of low frequencies can be greatly accelerated with DNN-based schemes.
We present theories under an idealized setting to illustrate how smoothness/regullrity of activation function contributes to the F.Principle.
We discuss in detail the implication of the E-Principle to the generalization of DNNs that DNNs are implicitly biased towards a low frequency function and provide explanation of good and poor generalization of DNNs for low and high frequency dominant target functions, respectively.
2 FREQUENCY PRINCIPLE
The concept of "frequency" is central to the understanding of F-Principle. In this paper, the "frequency" means response frequency NOT image (or input) frequency as explained in the following.
Image (or input) frequency (NOT used in the paper): Frequency of 2-d function representing the intensity of image over pixels at different locations. This frequency corresponds to the rate of change of intensity across neighbouring pixels. For example, an image of constant intensity possesses only the zero frequency, i.e., the lowest frequency, while sharp edge contributes to high frequencies of the image.
R R
Response f'reuuecyy (used in the paper): Frequency of a general Input-Output mapping f. For exam- plc, consider a simplified classification problem of partial MNIST data using only the data with label O 784
and 1, fx1, F2,, .1784): 784 + {0, 1} mapping 784-d space of pixel values to 1-d space, where
I, is the intensity of the j-th pixel. Denote the mapping's ' Fourier transform as fk1, ...... k781). The frequency in the coordinate k, measures the rate of change of f fZ1, ..- , .7844 with respect to xj, Le., the intensity of the j-th pixel. If f possesses significant high frequencies for large ky. then a small change of zÿ in the image might induce large change of the output (e.g., adversarial example). For a dataset with multiple classes, we can similarly define frequency for each output dimension. For real data, the response frequency rigorously defined via the standard nonuniform discrete Fourier transform (NUDFT), see Appendix A
Frequency Principle: DNNs often fit fargetfunction functions from low high (response) frequencees during the training process. An illustration of F-Principle using function of 1-d input is in Appendix B The F-Principle is rigorously defined through the frequency defined by the Fourier transform (Appendix Bracewell & Bracewell ( (1986)) and the converging speed defined by the relative error. By using high-dimensional real datasets, we then experimentally demonstrate F-Principle the levels of both individual frequencies (projection method) and coarse-grained frequencies (filtering method).
3 F-PRINCIPLE IN MNIST/CIFAR 10 THROUGH PROJECTION METHOD
Real datasets very different from synthetic data used in previous studies. In order utilize the Principle to understand and better use DNNs in real datasets, is important to verify whether the P-Principle also holds in high-dimensional real datasets.
2

---

Under review as a conference paper at ICLR 2020
In the following experiments, we examine the F-Principle in training dataset of { y1) y4) )
where n is the size of dataset. æ; Rd is a vector representing the image and y: E {0, 1 is the output (a one-hot vector indicating the label for the dataset of image classification). is the dimension of the input (d 784 for MNIST and d 32 x 32 x 3 for CIFARIO). Since the high dimensional discrete Fourier transform (DFT) requires prohibitively high computational cost, in this section, we only consider one direction in the Fourier space through projection method for each examination.
3.1 EXAMINATION METHOD: PROJECTION
For a dataset ((r, y:) y=) we consider one entry of 10-d output, denoted by ys E R. The high dimen- sional discrete non-uniform Fourier transform of (< 1=o00 is ÿk = - -5=0 yr exp (-i2mk æ.). The number of all possible grows exponentially on dimension d. For illustration, in each examina- tion, we consider direction of k in the Fourier space, i.e., k = kp1. is a chosen and fixed unit vector, hence | k. Then we have ÚR E= Ve exp (-i2x k2y)k), which is essentially ) 1n-1 where Tp, Pi - z; is the projection of æ; the direction Pi (Bracewell & Bracewell] 1986). For each training dataset, pi is chosen as the first principle component of the input space. To examine the convergence behavior of different frequency components during the training, we compute the relative difference between the DNN output and the target function for selected important frequencies k's at each recording step, that is, AF(k) = h4 l/usl where ÿR and hg are 1-d Fourier transforms of {y: Ji= and the correspond- ing DNN output ( Ki=o respectively, along p1. Note that each response frequency component, hy. of DNN output evolves the training goes.
the 1-d Fourier transform of {TTp is 36)
3.2 MNIST/CIFARIO
In the following, we show empirically that the F-Principle is exhibited in the selected direction during the training process of DNNs when applied MNIST/CIFARIO with cross-entropy loss. The network for MNIST a callycconnected tanh DNN (784-400-200-10) and for CIFARIO is two ReLU convolutional layers followed by fully-connected DNN (800-400-4000400-10), All experimental details of this paper can be found in Appendix C
We consider one of the 10-d outputs in each case using non-uniform Fourier transform. As shown in Fig. [a] and cc). low frequencies dominate in both real datasets. During the training, the evolution of relative errors of certain selected frequencies (marked by black squares in Fig. aa) and [T)) shown Fig. Thb) and (d). One can easily observe that DNNs capture low frequencies first and gradually capture higher frequencies. Clearly, this behavior is consistent with the F-Principle. For other components of the output vector and other directions of p, similar phenomena are also observed.
10
Mateeee the Inde
leccood too Indox.
C4
0.
18P
127
0.00
0.00
5.10
6.18
10
107
(6) Fourier domain
(b) Relstive error
(c) Fourler domein
(d)
Reletive error
Figure 1: Projection method. (a, b) are for MNIST, (c, d) for CIFAR10. (a, c) Amplitude | vs. frequency. Selected frequencies marked by black squares. (b, d) Ar(k) vs. training epochs for the selected frequencies.
F-PRINCIPLE IN MNIST/CIFARIO THROUGH FILTERING METHOD
The projection method in the previous section enables us to visualize the F-Principle in one direction for each examination at the level of individual frequency components. However, demonstration by this method alone is insufficient because it is impossible to verify the F-Principle at all potentially informative directions for high-dimensional data. To compensate the projection method, in this
3

---

Under review as a conference paper at ICLR 2020
section, consider coarse graiieegrneddd filtering method which is able unravel whether, in the radially averaged sense, low frequencies converge faster than high frequencies.
4.1 EXAMINATION METHOD: FILTERING
The idea of the filtering method is as follows. We split the frequency domain into two parts, i.e., low-frequency part with |k| I Ko and a high-frequency part with |k] > ku, where | is the length of a vector. The DNN is trained as usual by the original dataset { ys) y1))== such as MNIST or CIFARIO. The DNN output is denoted h. During the training, relative errors of low- and high- frequency part, using the two measures below
examine the convergence of
En kIsko (KK) 1())122
Σx (1 - M|
(ASko)) (1((k) (()))22 3 1 [k))
Clow
Σx Lklskk (k)
Ehigh
respectively, where indicates Fourier transform, 1 1 is an indicator function, i.e.,
1, [k| S ko-
1 S
0.
[k| > ko-
If we consistently observe Clow < Chigh for different ko 's during the training, then in mean sense, lower frequencies are first captured by the DNN, i.e., F-Principle.
However, because it is almost impossible to compute above quantities numerically due to high computational cost of high-din nigh-dimensional Fourier transform, we alternatively use the Fourier transform of a Gaussian function Go (k), where is the variance of the Gaussian function G, to approximate 1 k|>>kp This is reasonable due to the following two reasons. First, the Fourier transform of Gaussian still a Gaussian, i.e., (A)) decays exponentially as [k] increases, therefore, it can approximate 1 | Sku by Go with a proper 8(kn) (referred to as 5 for simplicity). Second, the computation of Clow and Ehigh contains the multiplication of Fourier transforms in the frequency domain, which is equivalent to the Fourier transform of a convolution in the spatial domain. We can equivalently perform the examination in the spatial domain so as avoid the almost impossible high-dimensional Fourier transform. The low frequency part can be derived by
yi low.6 P (y GO;;, )a.
(1)
where * indicates convolution operator, and the high frequency part can be derived by
y high,5 A 1ow,6
(2)
Then, examine
En 13,
low. low. 6 1ow.612
h
Σ, high,
1
h
b
Clow
1ow.d 12
Chigh
high.8
3/
where low,6 and h high,6 are obtained from the DNN output h. which evolves function of training epoch, through the same decomposition. If Elow < Chigh for different d's during the training, F-Principle holds; otherwise, is falsified. Next, we introduce the experimental procedure.
Step One:
Training. Train the DNN by the original dataset {(x;, y:) y:) such as MNIST or CIFAR10. æ; is an image vector, y; one-hot vector.
Step Two: Filtering. The low frequency part can be derived by
y Jow, 1
y (2; -zy),
(4)
C,
n- where C; = En= (5(z; - 2;) ) is normalization factor and & (2x æz,) exp (-|x; xz xzy1²
(5)
The high frequency part can be derived by y. h A y: h high, for each DNN output h..
y low.
We also compute h low,ó and
Step Three: Examination. To quantify the convergence of h low,5 and h high.6 we compute the relative error Clow and Chigh at each training epoch through Eq.. 33)
4

---

Under review as a conference paper at ICLR 2020
4.2 DNNs WITH VARIOUS SETTINGS
With the filtering method, we show the F-Principle in the DNN training process of real datasets for commonly used large networks. For MNIST, we use a fully-connected tanh-DNN (no softmax) with MSE loss; for CIFARIO, network, i... two convolutional layers. followed by tully-connected multi-layer neural network with softmax; the other is VGG16 (Simonyan & Zisserman 2014) equipped with a 1024 fully-connected layer. These three structures are denoted as "DNN", "CNN" and "VGG" in Fig. 2 respectively. All trained by SGD from scratch. More details are in Appendix C
cross-entropy loss and two structures, one is small ReLU-CNN
We scan a large range of 8 for both datasets. As an example, results of each dataset for several d's are shown in Fig. 2 respectively. Red color indicates small relative error. In all cases, the relative error of the low-frequency part, i.c., flow, decreases (turns red) much faster than that of the high-frequency part, i.c., Chigh. Therefore, as analyzed above, the low-frequency part converges faster than the high-frequency part. We also remark that, based on the above results on cross-entropp loss, the F-Principle is not limited to MSE loss, which possesses natural Fourier domain interpretation by the Parseval's 's theorem. Note that the above results holds for both SGD and GD.
8
34 [
(a) 6 3, DNN
(b) CNN
(c) VGG
41
35
330
224
256
240
(d) 7. DNN
(e) = CNN
(0 10, VGG
Figure 2: F-Principle in real datasets. flow and ehigh indicated by color against training epoch.
5 F-PRINCIPLE IN SOLVING DIFFERENTIAL EQUATION
Recently, DNN-based approaches have been actively explored for variety of scientific computing problems, e.g., solving high-dimensional partial differential equations (E et al. 2017 | Khoo et al..
2017 He et al. 2018 Fan al. 2018) and molecular dynamics (MD) simulations (Han et al. 2017). However, the behaviors of DNNs applied to these problems are not cell-understood. To facilitate the designs and applications of DNN-based schemes, it is important to characterize the difference between DNNs and conventional numerical schemes on various scientific computing problems. In this section, focusing on solving Poisson's ''s equation, which has broad applications in mechanical engineering and theoretical physics (Evans) 2010), we highlight a stark difference between a DNN-based solver and the Jacobi method during the training/iteration, which can be explained by the F-Principle.
Consider 1-d Poisson's 's equation:
- Au(x) = g(x), = (-1,1), u(-1) u(1) = 0.
(6)
We consider the example with = sin Aai
which has analytic
solution Ure((x) (x) (x) ci + co. where gu sin(x) + sin(4x)/44 sin(8z) (8x)/8 sin(24z)/38)
C = (-n(-1)- 9n (1))/2 and co = - (9o(-1) + go (1)) 1001 training samples {z, {2 are evenly
spaced with grid size dar in [0, 1). Here,
the DNN output, h(x; 0), fit ueer (2r) (Fig. Fa). A
5

---

Under review as a conference paper at ICLR 2020
10
1.0
8.50
treg peak Ietax.
24
22
10 30
-0.5
00
18
10P
351
321
167
206
epom
(a)
(b)
(c)
(d)
Figure 3: Poisson's equation. (a) Uret (ar)(a:). Inset: (Brer())) as function of frequency. Frequencies peaks are marked with black dots. (b.c) ( computed on the inputs of training data at different epochs for the selected frequencies for DNN (b) and Jacobi (c). (d) |/4 "yer]lso at different running time. Green stars indicate |/ - Meee ol using DNN alone. The dashed lines indicate || - Urat so for the Jacobi method with different colors indicating initialization by different timing of DNN training.
DNN-based scheme is proposed by considering the following empirical loss function E & Yu 2018
T Tmp
Σ [.,()a)) 2
g(x)))((aa)))) 8x + 3 (h(xo))2 + M(x))))
(8)
The second term in Lemp (h) is penalty, with constant B, arising from the Dirichlet boundary condition 7 After training, the DNN output well matches the analytical solution Uref- Focusing on the convergence of three peaks (inset of Fig. Baa) in the Fourier transform of Wref. shown in Fig.B(b), b)),, low frequencies converge faster than high frequencies as predicted by the F-Principle. For comparison, also the Jacobi method solve problem (6). High frequencies converge faster in the Jacobi method (Details can be found in Appendix D). as shown in Fig. C)..
As demonstration, we further propose that DNN can be combined with conventional numerical schemes to accelerate the convergence of low frequencies for computational problems. First, we solve the Poisson's equation in Eq. 66) by DNN with M optimization steps (or epochs), which needs be chosen carefully, to get good initial guess in the sense that this solution has already learned the low frequencies (large eigenvalues) part. Then, we use the Jacobi method with the new initial data for the further iterations. We use / Myet &o & maxzen lh(x) (z)r(2) to quantify the learning result. As shown by green stars in Fig.3(ch |/h Mrefll fluctuates after some running time using DNN only. Dashed lines indicate the evolution of the Jacobi method with initial data set to the DNN output at the corresponding steps. If M is too small (stop too early) (left dashed line), which is equivalent to only using Jacobi, it would take long time to converge to a small error, because low frequencies converges slowly, yet. If M is too big (stop too late) (right dashed line), which is equivalent using DNN only, much time would be wasted for the slow convergence of high frequencies. A proper choice of M is indicated by the initial point of orange dashed line, in which low frequencies are quickly captured by the DNN, followed by fast convergence in high frequencies of the Jacobi method.
This example illustrates cautionary tale that, although DNNs has clear advantage, using DNNs alone may not be the best option because of its limitation of slow convergence at high frequencies. Taking advantage of both DNNs and conventional methods to design faster schemes could be promising direction in scientific computing problems.
A PRELIMINARY THEORETICAL UNDERSTANDING
subsequent theoretical work (Luo al. 2019) provides a rigorous mathematical study of the F- Principle at different frequencies for general DNNs (c.g.. multiple hidden layers, different activation functions, nigh-dimensional inputs). The key insight is that the regularity of DNN converts into the decay rate of loss function in the frequency domain. For intuitive understanding of this key insight, we present theories under an idealized setting, which connect the smoothness/regularig of the activation function with different gradient and convergence priorities in frequency domain.
The activation function we consider is oxx) = tanh(x), which is smooth in spatial domain and its derivative decays exponentially with respect frequency in the Fourier domain. For DNN of one

---

y exp (-i2mk æz), where Under review as a conference paper at ICLR 2020
hidden layer with nodes, 1-d imput and 1-d output: h(z) プド= a by), aj Wy by R. We also use the notation 0 {01z} with 01j agj 02j w,, and Oaj bz. ..... m. The loss at frequency k is L(k) - = [((k) f(k) is the Fourier transform, f is the target function.
The total loss function is defined as: I= = -_x (.kk) dk. Note that according to Parseval's theorem, this loss function the Fourier domain equal to the commonly used MSE loss. We have the following theorems (The proofs are at Appendix E). Define W (w1, W2, "mm) E m
Theorem 1. Considering a DNN of one hidden layer with activation function (xx) = tanh(z)) for any frequencies kn and k2 such that (f(k))] > 0, [f(k)) > 0, and [/2| > |k1 > 0, there exist positive constants e and such that for sufficientll small 6, we huve
Je (WW:
BL(K))
@1(k2)
for all 1.3 1.3 nBa)
801y
30eg
2 21-C Cexp((cc/))
p(Bs)
where B5 C. R is ball with radius ó centered at the origin and p(-) is the Lebesgue measure.
Theorem 1 indicates that for any two non-converged frequencies, with small weights, the lower- the higher-frequency ones. Due to Parseval's
frequency gradient exponentially dominates theorem, the MSE loss in the spatial domain is equivalent to the 1.2 loss in the Fourier domain. To intuitively understand the higher decay rate of a weeeuefryy loss function, we consider the training in the Fourier domain with loss function of only two non-zer frequencies.
Theorem 2. Considering a DNN of one hidden layer with activation function o(x) ttan(rr.. Suppose the target function has only two non-zero frequencies k1 and k2, that is, If(k)) > 0, [f(k)) > 0. 1kg] > |k1l > O, and [f)) 0 for k + k1 k2. Consider the loss function of L(k1) + L(k2) with gradient descent training. Denote
(l((1)
< (L(k))
(L(k2)
S =
Ōt S
ØL
at
that is, L(ks) decreases faster than L(k2). There exist positive constants e and C such that for sufficiently small 8, we have
" ((W: :S holds} n Bs) 2 1 21-Cexp(-c/0)
((ss)
where Bj C Rdhh is ball with radius 8 centered the origin and u(-) is the Lebesgue measure.
DISCUSSIONS
DNNs often generalize well for real problems Zhang et al. 2016) but poorly for problems like fitting a parity function SShalev-Shwarde et al. 2017 Nye & Saxe 2018) despite excellent training accuracy for all problems. Understanding the differences between above two types of problems, i.e., good and bad generalization performance of DNN, is critical. In the following,
show qualitative difference between these two types of problems through Fourier analysis and use the F-Principle to provide an explanation different generalization performances of DNNs.
For MNIST/CIFARIO,
examine Ptotal,k
Piostl -1
Paotal
((v;,)) 3:) Thotta Phottal -1 consists of both the training and test datasets with certain selected output com- ponent, at different directions of & in the Fourier space. We find that Icotal, concentrates on the low frequencies along those examined directions. For illustration, Protalkk's 's along the first principle component are shown by green lines in Fig. 4 a, b) for MNIST/CIFARIO, respectively. When only the training dataset is used, Itrain,k well overlaps with Itotal,k at the dominant low frequencies.
For the parity function f(x) 11 Iy detined Ω (-1,1)1 22 parity function concentrates at &s E f- 1..47 and vanishes as - 0. as illustrated Fig. 4) for
1]dd d. its Fourier transform is f(k)
1 Ezen I - k (-i) II -T= sin 2 Clearly, for & E [- al
11d the power of the
the direction of la. Given randomly sampled training dataset 5 C Ω with points, the nonuniform
7

---

Under review as a conference paper at ICLR 2020
12.0
6:75
12"
8:08
Segusecy
Pequirecy
tracuency
(a) MNIST
(b) CIFAR10
(c) parity
Figure 4: Fourier analysis for different generalization ability. The plot is the amplitude of the Fourier coefficient against frequency The red dots are for the training dataset, the green line for the whole dataset, and the blue dashed line is for an output of well-trained DNN on the input of the whole dataset. For (c), 10. The training data 200 randomly selected points.
Fourier transform on S is computed as = = I1==1 zee 12 As shown in Fig. 4(c), (k) and (k) significantly differ at low frequencies.
By experiments, the generalization ability of DNNs can be well reflected by the Fourier analysis. For the MNIST/CIFAR 10, we observed the Fourier transform of the output of a well-trained DNN on
( faithfully recovers the dominant low frequencies, as illustrated in Fig. 4(a) and 4 b). respectively, indicating good generalization performance as observed in experiments. However, for the parity function, we observed that the Fourier transform of the output of well-trained DNN
on {xx hes significantly deviates from fik at almost all frequencies, illustrated in Fig. 4(c),
indicating a bad gencralization performance as observed in experiments.
The F-Principle implicates that among all the functions that can fit the training data, a DNN is implicitly biased during the training towards a function with more power at low frequencies. If the target function has significant lead to artificial low frequencies in training dataset (see red line in Fig. 4c)), which is the well- known aliasing effect. Based the F-Principle, as demonstrated in Fig. 4(c), these artificial low frequency components will be first captured to explain the training samples, whereas the high frequency components will be compromised by DNN. For MNIST/CIFARIO, since the power of high frequencies is much smaller than that of low frequencies, artificial low frequencies caused by aliasing can be neglected. To conclude, the distribution of power in Fourier domain of above two types of problems exhibits significant differences, which result in different generalization performances of DNNs according to the E-Principle.
frggufrryenccy components, insufficient training samples will
RELATED WORK
There different approaches attempting to explain why DNNs often generalize well. For example. generalization error is related to various complexity measures (Bartlett et al.) [999; Neyshabur et al.)
2017 E al. 2018). local properties (sharpness/fltnees))) of loss functions minima (Keskar et al. 2016 Wu et al. 2017), stability of optimization algorithms (Hardt et I 2015). and implicit bias of the training process (Soudry et al. 20188: Arpit et al.) [207]]Xu et 2018). On the other hand, several works focus on the failure of DNNs (Shalev-Shwarte et al. 2017 7 Nye & Saxe 2018)). e.g., fitting the parity function, in which a well-trained DNN possesses no generalization ability. We propose that the Fourier analysis can provide insights into both success and failure of DNNs.
F-Principle was first discovered in (Xu et al., 2018 Rahaman al., 2018) simultaneously through simple synthetic data and not very deep networks. In the revised version, Rahaman et al. (2018) exam- ines the F-Principle in the MNIST dataset. However, they add noise MNIST, which contaminates the labels and damages the structure of real data. They only examine not very deep (6-layer) fully connected ReLU network with MSE loss, while cross-entropy loss is widely used. This paper verified that Prriniicpeee holds in the training process of MNIST and CIFARIO, both CNN and fully connected networks, very deep networks (VGG16) and various loss functions, e.g., MSE Loss, cross-entropy loss and variational loss function. In the aspect of theoretical study, based the key mechanism found by the theoretical study in this paper, Luo et al. (2019) shows a rigorous proof of the F-Principle for general DNNs. The theoretical study of the gradient of tanh(x) in the Fourier domain is adopted
8

---

Under review as a conference paper at ICLR 2020
Rahaman et al. (2018), ) in which they generalize the analysis ReLU and show similar results. is also used to analyze a nonlinear collaborative scheme for deep network training (Zhen 2018). In the aspect of application, based on the study of the F-Principle in this paper, Cai et al. 2019) and Cai & Xu (019) design DNN-hased algorithms to solve high-dimensional and
by
Thm
ct al.
higg-freyuency problems.
REFERENCES
Devansh Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al. A closer look at memorization deep networks. arXiv preprint arXiv: 03304, 2017.
Peter L. Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear vo dimension bounds for piecewise polynomial networks. In Advances in Neural Information Processing Systems, pp. 190-196, 1999.
Ronald Newbold Bracewell and Ronald N Bracewell. The Fourier transform and its applications, volume 31999. McGraw-Hill New York, 1986. 2 3.1
Wei Cai and Zhi-Qin John Xu. Multi-scale deep neural networks for solving high dimensional pdes. arXiv preprint arXiv: 1910: 2019. g
Wei Cai, Xiaoguang Li, and Lizuo Liu. A phase shift deep neural network for high frequency wave 2019.
equations in inhomogeneous media. Arxiv preprint,
Weinan and Bing Yu. The deep ritz method: deep learning based numerical algorithm for solving variational problems. Communications in Mathematics and Statistics, 6(1):1-12, 2018, 5
Weinan E, Jiequn Han, and Aruuff Jentzen. Deep learning based numerical methods for high- dimensional parabolic partial differential equations and backward stochastic differential equations. Communications Mathematics and Statistics, 5(4):349-380, 2017.
Weinan E, Chao Ma, and Lei Wu. A priori estimates of the generalization error for two-layer neural networks. arXiv preprini arXiv: 180.066710 2018. g
Lawrence C Evans. Partial differential equations. 2010.
Yuwei Fan, Lin Lin, Lexing Ying, and Leonardo Zépeda-Nánez. A multiscale neural network based on hierarchical matrices. arXiv preprint arXiv: TeXXiv:807.0088. 2018. 5
Jiequn Han, Linfeng Zhang, Roberto Car, et al. Deep potential: A general representation of many-body potential energy surface. arXiv preprint arXiv: 2017.
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. arXiv preprint 15X.v:150..01240, 2015.
Juncai He, Lin Li, Jinchao Xu, and Chunyue Zheng. Relu deep neural networks and linear finite elements. arXiv preprint 1807.01907 2018.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609 1609.04836, 2016. g
Yuehaw Khoo, Jianfeng Lu, and Lexing Ying. Solving parametric pde problems with artificial neural networks. arXiv preprint arXiv:1707.0833
2017. 5
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 141.691412.69980 2014. 6
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 10 (canadian institute for advanced research). URL http://www. cs. toronto. edu/kriz/cifar himl, 2010.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mnist/. 1998.

---

Under review as a conference paper at ICLR 2020
Tao Luo, Zheng Ma, Zhi-Qin John Xu, and Yaoyu Zhang. Theory of the frequency principle for general deep neural networks. arXiv preprint arXiv:1906.00 1906.0923,. 2019.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in Neural Information Processing Systems, pp. 5947-5956,
2017. g
Maxwell Nye and Andrew Saxe. Are efficient deep representations learnable? 2018.
8
Nasim Rahaman, Devansh Arpit, Aristide Baratin, Felix Draxler, Min Lin, Fred A Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of deep neural networks. arXiv preprint arXiv: 2018.
B
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient-based deep learning. arXiv preprint arXiv: / 170300795, 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1rXiv::409.15555 2014.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70), 2018.
Lei Wu, Zhanxing Zhu, and Weinan E. Towards understanding generalization of deep learning: Perspective of loss landscapes. arXiv preprint arXiv:/706. 10239, 2017. g
Zhi-Qin J Xu, Yaoyu Zhang, and Yanyang Xiao. Training behavior of deep neural network in frequency domain. arXiv preprint
2018.
B
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: (.1.:/631.0330, 2016.
Hui-Ling Zhen, Xi Lin, Alan Tang. Zhenhua Li, Qingfu Zhang, and Sam Kwong. Nonlinear collaborative scheme for deep neural networks. arXiv preprint arXiv:1811.01316, 2018. 8
A RESPONSE FREQUENCY OF TRAINING DATA f3 ON INPUTS { 1==1
In all our experiments, we consistently consider the response frequency defined for the mapping function g between inputs and outputs, say Rd + IR and any k R via the standard nonuniform discrete Fourier transform (NUDFT)
g(a,) Je
12
which is a natural estimator of frequency composition of g. (More details can be found in https 7/en. wiki wedia..og/wiik....... Mtokkii/Nonuniiii form cit.sciteee_ourrrerretteee Fourier_trans + 00, Ok
g(x)e ( dæ, where v(xx) is the data distribution.
We restrict all the evaluation of Fourier transform in our experiments NUDFT of (y: at )=- for the following practical reasons.
(i) The information of target function is only available at {=:)) for training.
(ii) allows us to perform the convergence analysis. As f + co, in general, h( t) + yı for any (h( () is the DNN output), leading to hyg + 0b for any k. Therefore, we can analyze the convergence at different & by evaluating AF(k) like 0vel/lkk during the training. If we use different set of data points for frequency evaluation of DNN output, then AF(k) may not converge to 0 at the end of training.
(iii) UN faithfully reflect the frequency structure training data (x, y W Intuitively, high frequencies of ÿk correspond to sharp changes of output for some nearby points in the training data. Then, by applying a Gaussian filter and evaluating still at (æ,}i we obtain the low frequency part of training data with these sharp changes (high frequencies) well suppressed.
10

---

Under review as a conference paper at ICLR 2020
1.0
true
0.8
0.6
0.4
0.2
10
30"
10
10
epach
(a) target function
(b) relative error
Figure 5: 1d input. (a) f(r). Inset: [f()) (b) (k) of three important frequencies (indicated by black dots in the inset of (a)) against different training epochs.
In practice, it is impossible to evaluate and compare the convergence of all E R even with a proper cutoff frequency for very large d of O(10") (MNIST) or O(10²) (CIFARIO) due to curse of dimensionality. Therefore, we propose the projection upproach, i.c., fixing & at a specific direction and the filtering approach detailed in Section 3 and respectively.
B ILLUSTRATION OF F-PRINCIPLE FOR 1-D SYNTHETIC DATA
To illustrate the phenomenon of F-Principle, we use 1-d synthetic data to show the evolution of relative training error at different frequencies during the training of DNN. we train DNN to fit 1-d target function f(x) = sin + sin (3xr) + sin(5z) of three frequency components. On n = 201 evenly spaced training samples, i.e., {-x) n-1 in 3.114,3.14] the discrete Fourier transform (DFT) of fxx or the DNN output (denoted by h(x)) is computed by fa > nn ((zje--2xzkk -i2nkk/ and
fuR = Di= h(xx)ee -i2rjk/n where is the frequency. As shown in Fig. a). the target function has three important frequencies as we design (black dots at the inset in Fig. a(a)). To examine the convergence behavior of different frequency components during the training with MSE, we compute the relative difference between the DNN output and the target function for the three important lh& - fel/If&l, where | denotes the norm
frequencies k's at each recording step, that is, AF(K of a complex number. As shown in Fig. 5Jb), the DNN converges the first frequency peak very fast, while converging the second frequency peak much slower, followed by the third frequency peak.
Next, we investigate the F-Principle on real datasets with more general loss functions other than MSE which was the only loss studied in the previous works (Xu et al. 2018: Rahaman et al. 2018). All experimental details can be found in Appendix. C
C EXPERIMENTAL SETTINGS
In Fig. 5 the parameters of the DNN initialized by a Gaussian distribution with mean 0 and standard deviation 0.1. We use tanh-DNN with widths 1-8000-1 with full batch training. The learning rate is 0.0002. The DNN is trained by Adam optimizer (Kingma & Ba 2014) with the MSE loss function.
In Fig. for MNIST dataset, the training process of a tanh-DNN with widths 784-400-200-10 is
shown in Fig. aa) and [b). For CIFARI0 dataset. results are shown in Fig. ( and d)) of ReLU-CNN, which consists of one convolution layer of 3 x 3 x 64, a max pooling of x 2, one convolution layer of 3 x 3 x 128, max pooling of 2, followed by a fully-connected DNN with widths 800-400-400-400
For both cases, the output layer of the network is equipped with softmax. The network output is 10-d vector. The DNNs are trained with cross entropy loss by Adam optimizer (Kingma & Ba 2014). (a. b) are for MNIST with tanh-DNN, The learning rate is 0.001 with batch size 10000. After training, the training accuracy is 0.951 and test accuracy is 0.963. The amplitude of the Fourier coefficient with respect to the fourth output component at each frequeney is shown in (a), in which the red dots are computed using the training data. Selected frequencies are marked by black squares. (b) A (kk at different training epochs for the selected frequencies. (c, d)
11

---

Under review as a conference paper at ICLR 2020
for CIFARIO dataset. We use ReLU network of CNN followed by fully conne-con DNN.
The learning rate is 0.003 with batch size 512. (c) and (d) are the results with respect to the ninth output component. After training, the training accuracy is 0.98 and test accuracy is 0.72.
In Fig. 2 for MNIST, we use a fully-connected Banh-DNN with widths 784-400-200-10 and MSE cross-entropy loss and ReLU-CNN, which consists of one convolution layer of 3 x x 32, a max pooling of x 2, one convolution layer x 3 x 64, a max pooling of 2 x 2, followed by fully-connected DNN with widths 400-10 and the output layer of the network is equipped with a softmax. The learning rate for MNIST and CIFAR 10 is 0.015 and 0.003, respectively. The networks are trained by Adam optimizer (Kingma & Ba, 2014) with batch size 10000. For VGGI6, the learning rate is 10 The network is trained by Adam optimizer (Kingma & Ba 2014) with batch size 500.
loss; for CIFAR10,
In Fig. 3 the samples are evenly spaced in [0. 1] with sample size 1001. We use DNN with widths 1 14000-500-4000 and full batch training by Adam optimizer (Kingma & Bal 2014). The learning rate is 0.0005. 3 is 10. The parameters of the DNN are initialized following Gaussian distribution with mean and standard deviation 0.02.
In Fig- 4 the settings of (a) and (b) are the same the ones in Fig. For (c), we a tanh-DNN with widths 10-500- 1000-100-, learning rate 0.00 0.0005 under full batch-size training by Adam optimizer (Kingma & Ba 2014). The parameters of the DNN are initialized by Gaussian distribution with mean () and standard deviation 0.05.
D CENTRAL DIFFERENCE SCHEME AND JACOBI METHOD
Consider a one-dimensional (1-d) Poisson's 's equation:
Au(x) g(r), =EQ==-1111)
a 2
r ==
[_ is uniformly discretized into + 1 points with grid size h 2/n. The Poisson's equation in Eq. 9 can be solved by the central difference scheme,
U++1 244 24-1 =((x)), i 1,2, . (8x)²
Au.
(10)
resulting linear system
Au 9,
(11)
where
2
-1
0
-1
2
1
0
0
0
-1
2
-1
A
(12)
:
0
0
-1
2
1)x(n-1)
91
92
W
= (6z)²
I;
(13)
71
Un
9n-2
Up-1
9n-1
class of methods to solve this linear system iterative schemes, for example, the Jacobi method. Let A D L - U, where D is the diagonal of A, and L and U are the strictly lower and upper triangular parts of - AA, respectively. Then, we obtain
u = (L + U)u+ + g.
(14)
At step & N, the Jacobi iteration reads
++ D- (L+ +D-1g.
(15)
12

---

Under review as a conference paper at ICLR 2020
We perform the standard error analysis of the above iteration process. Denote u the true value obtained by directly performing inverse of A in Eq. [11). The error at step f+ is e = 4++ u².
Then, e ee, where R, D (L + U). The converging speed of et is determined by the eigenvalues of R,,, that is,
A AR (R.)) = COs
k= 1,2, ,
(16)
n
and the corresponding cigenvector 2y 's entry is
sin
1.2, ... ,
(17)
7
So we can write
n
(18)
where of can be understood as the magnitude of e in the direction of Us. Then,
n-1
++1
a
R
(19)
k=1
ox
1+1
d
Therefore, the converging rate of et the direction of uy controlled by dg. Since
(n k)t
cos
COs
(20)
n
the frequencies and (n k-) are closely related and converge with the same rate. Consider the frequency & < n/2, Ae is larger for lower frequency. Therefore, lower frequency converges slower in the Jacobi method.
E PROOF OF THEOREMS
The activation function we consider is (xx) = tanh(x).
c² e-
(xx) tanh(x)
R.
e + -
For DNN of one hidden layer with m nodes, 1-d input x and 1-d output:
h(x) Σ agjowwx+ bb)), aj, wy, by E R,
(21)
where w aj. and by are called parameters, in particular, wy and aj are called weights, and by is also known bias. In the sequel, will also the notation 0 {0rr with 01ş aj. 02j wy+ is
and fly by. j 1,... m. Note that (k)) (k/22( where the Fourier transformation and its inverse transformation are defined follows:
f(k) = f +00
1
f(x)e ihe da, [(x)
f(k) dk.
2T
The Fourier transform of owwyx + by) with wy. by E RR 1,
m reads
2ri
ibbk
oww, +b;)(k)
exp
(22)
|
Wi
exp(
nk 2w;
a exp
Thus
ibbk
1
T((k) Σ
exp
(23)
|wj]
Wi
exp(
Zw
nk
exp
2wy
nk
13

---

Under review as a conference paper at ICLR 2020
We define the amplitude deviation between DNN output and the target f(x) at frequency k: as
((k) - ((a)) f(k+).
Write Dkk) as D(k) A(k)elo(k), where A(k) E [0, +00) and (kk E R are the amplitude and phase of (Kk), respectively. The loss at frequency & is T(kk) 1 ( 2 where | denotes the norm of a complex number. The total loss function is defined as: L f L(k) dk. Note that according to Parseval's 's theorem, this loss function in the Fourier domain is equal to the commonly used loss of mean squared error, that is, L f- (h((x) f(x))² dx. For readers' reference, we list the partial derivatives of L(k) with respect to parameters
@L(k)
2T
byk:
sin
o(k))
Eo.
(24)
da,
W
Wj
al(k)
byk
o(())
m²ask
2 w
sin
E1
Owj
W/
2Ta byk
Cos
byk
((k))
Eo,
(25)
w)
W
bT
byk
-o(k)) Eu.
(26)
0b;
w
Wj
where
sgn(w;) sgn(wy)AA(k)
En
exp(
exp(
5k 2wz
2wy
exp(
rk
exp(
5k 2wy
2wy
F
exp(
ok
cxp(
5k
2wy
2wy
The descent increment at any direction, say, with respect to parameter 0ty, is
0L
aL(k)
dk.
(27)
00,
a0iy
The absolute contribution from frequency k this total amount 0ty is
@L(k)
2J A(k) exp
(0, A),
(28)
001;
where O2 A {w,, bj. a,), 0 E 8j. Flş k) is a function with respect to 8g and k. which can be found in one of Eqs. 24 25 26
When the component at frequency where h((k) is not close enough f(k). exp k morkk/ww /2 would dominate (0,, k) for a small wy. Through the above framework of analysis, we have the following theorem. Define
(w1, W2, .. (0 Wm)) Rm
Theorem. Consider a one hidden layer DNN with activation function (xx) = tanh For any frequencies kn and b2 such that [f(k)) > 0, (f > O, and [i2l > |ka] > O, there exist positive constants e and such that for sufficiently small 6, we have
1 W
0T(k))
(L((2)
for all 1. n Bs
30.3
0015
u(Bs)
2 1- 1- eeceeppp-2e ex)
(30)
where B5 C T is ball with radius 5 centered at the origin and y(.) is the Lebesgue measure.
We remark that and C depend k1, 12 (f(())) (kk2)) sup las|, sup [bs], and
14

---

Under review as a conference paper at ICLR 2020
Proof. To prove the statement, it is sufficient to show that μu ((((t,,)/m((B)) exx((-c/0) for each 1.j, where
@L(kk)
@L(k2)
S1j,8 W E BB
(31)
06ij
0015
We prove this for S1j.6, that is, Oij aj. The proofs for Oyj wy and by are similar. Without loss of
generality, we assume that k1, h2 > 0, by > O, and w/ + 0, j = -, m. According to Eq. (24).
the inequality [ [T[())] is equivalent to
daz
dag
A(k2)
mk1 exp(
2w;
exp(
mk1 2wry nb2 201g
byk2 ((k))
sin (2yb) wj
o(ki))
sin
(32)
A(ki)
exp
exp(
W/
2m1
Note that [h(+)]] - C - ==1
m
Los]
exp(
mkk
for le > 0. Thus
mzyl
2/wuy1
lim h(kk) = and
lim W-50
D(k) = f(k).
(33)
W00
Therefore,
lim A(k) = lf()) and W
lim (kk ग + arg(f(k)) W-X
(34)
For W E Bg with sufficiently small 6, A(kj) > f1( > and A(k2) < 212(2 Also note that
sin
bakk
o(k2)) $ and that for sufficiently small 8, wy
exp(
sk1 2
exp(
nke 2
T (k(k22 k1)
exp
(35)
exp( 2wy
xk2 exp(
2wy
2|w,1
Thus, inequality (32 implies that
byki Wj
81f(k22
T T(ki k1)
sin
((ki)
exp
(36)
2/wryg
Noticing that 2 |z|| S
sin (|2=) S 3) and Eq.
34 we have for W E Stjj8. for some
q Z.
beki
8T S exp (-
(- T(k2 - ki)
arg(f((n)) q s
(37)
wt
[f(k))
28
that is.
biki
-ciexp(-co + qı arg(f((s)) S
< ci exp(-cc/6)) + qा + arg(f(k))),
(38)
Wi
B=(f(k2) and 02 = π  k1). Define == T+ U where
where 6j
[f(k))
1+ =+== (w, 0: W $118),
r= {w; < < We E S1y8).
I =
(39)
For wy > 0, we have for some g E Z,
byki
byki
0
S w S
(40)
ci exp(-c2/0) पा + arg arg(f (f())
-c exp(-c2/0) + qu arg(f(k)))
Since W E B3 and c₁ exp(-c2/ + arg (k1()( <
2T, we have b,k1 अ
S wj S 8. Then Eq. 440
only holds for some large q, more precisely, q 2 qu (one-dimensional) Lebesgue measure of I
byk
2. Thus we obtain the estimate for the
ad
byk1
byke
m(r+) $
Σ 9o
+ qu + arg(f(k))
e + qu + arg(f(k)))
-c
< kic
Σ
1
(qr +
- (c expl exp(-c2/8)))
8=
5 cCexp(-c/6).
(41)
15

---

Under review as a conference paper at ICLR 2020
The similar estimate holds for (u(I"), and hence p(l) I Cexp(-c/8). For W Bs, the (m 1) dimensional vector (W'1.... - Wi+1," " Wm) )² final arrive at the desired estimate
is in a ball with radius in R=-1, Therefore,
((S15,6)
I C Cexp(-c/0).
(42)
((Bs)
wmdm
where wm the volume of unit ball R
Theorem. Considering DNN of one hidden layer with activation function (xx) tanh(x). Suppose the target function has only two non-zero frequencies ką and 22, that is, (f(kk) [f(kg) > O, and |22 > [kl] > O, and [f() for k # k1, k2. Consider the loss function of L = (k2) ) + L(kg) with gradient descent training. Denote
[aL(ki) Ōt
@L(k1)
@L(k2)
S
20,
I
Ot
Øt
that is, L(ky) decreases faster than L(k2). There exist positive constants and C such that for sufficiently small 8, we have
" ( : holds} n Bs). 2 2 exx((cc(0)
((ss)
where B5 C. R is ball with radius å centered at the origin and u(-) is the Lebesgue measure.
Proof. By gradient descent algorithm, we obtain
aL(k))
(L(k)) 0015
Σ
Ø1
001j
ŌL
1.
(L(k)) O(L(Ks) + L(k2))
-E
001;
001,
1J
2
(L(k))
(L(k2)
Σ
00iy
20y
0013
15
4
0L(k2)
aL(k22)
2
aL(k)
(L(k2)
0t
00i5
30,
0013
45
and
OL
8 (L(k)) + L(k2))
(L(k))
(L(k))
2
Σ
S 0.
(43)
Ø1
30:3
001j
L.j
To obtain
(T(k))
(l(k2)
oI(ki))
27
E
(44)
Øt
Øt
0015
it is sufficient to have
al(k1)
aL(k2)
(45)
801;
001z
Eqs.
also yield
aL(k))
0.
0t
Therefore, Eq. theorem 2.
(45) sufficient condition for S. Based on the theorem 1, we have proved the
16

---

Under review as a conference paper at ICLR 2020
small Inttal
output
(c) 1-d
DFT
lange inital
( UNN output
(g) 1-d slice
(h) convergence order
Figure 6: F-Principle in fitting natural image. The training data are all pixels whose horizontal indices are odd. We initialize DNN parameters by a Gaussian distribution with mean and standard deviation 0.08 (small initial) or (large initial). (a) True image. (b-g) correspond to the case of the
small initial parameters. (f-h) correspond to the case of the large initial parameters. (b) DNN outputs of all pixels at different training epochs. (c, g) DNN outputs (blue) and the true gray-scale (red) of test pixels at the red dashed position in (a). (d) [h((t)] (green) at certain training epoch and [f() (red) at the red dashed position in (a), as function of frequency index. Selected peaks are marked by black dots. (e, h) P computed by the training data at different epochs for the selected frequencies in (d), (1) DNN outputs of training pixels (left) and all pixels (right) after training. We use tanh-DNN with widths 2-400-200- 200-100-1. We train the DNN with the full batch and learning rate 0.0002. The
DNN is trained by Adam optimizer Kingma & Ba 2014 with the MSE loss function.
F MEMORIZING 2-D IMAGE
We train DNN to fit natural image (See Fig. Ga)), mapping from coordinate (rc, y) gray scale strength, where the latter subtracted by mean and then normalized by the maximal absolute value. First, we initialize DNN parameters by Gaussian distribution with mean 0 and standard deviation 0.08 (initialization with small parameters). From the snapshots during the training process, can that the DNN captures the image from moarse-grained low frequencies to detailed high frequencies (Fig. b)). As an illustration the F-Principle, we study the Fourier transform of the image with respect for fixed y (red dashed line in Fig. a)), denoted the target function f(x in the spatial domain). The DNN can well capture this 1-d stice after training as shown in Fig. ((c). Fig. d) displays the amplitudes parameters, as an example in Fig. ()).. when the DNN fitting low-frequency components, high frequencies stay relatively small. As the relative error shown in Fig. e)... the first five frequency peaks converge from low to high in order.
[A)] | of the first 40 frequency components, Due to the small initial
Next, we initialize DNN parameters by Gaussian distribution with mean 0 and standard deviation 1 (initialization with large parameters). After training, the DNN can well capture the training data, as shown in the left in Fig. ff. However, the DNN output at the test pixels are very noisy, as shown in the right in Fig. f). For the pixels at the red dashed lines in Fig. ((a), as shown in Fig. g). the DNN output fluctuates a lot. Compared with the case of small initial parameters, as shown in Fig. kh), the convergence order of the first five frequency peaks do not have a clear order.
17


Reviews:
[{"review_id": "rkeMvyPTFH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies the training process of NNs through the lens of Fourier analysis. The authors argue that during the training process, NNs will first learn low frequencies part of the function first and then the high frequency part. To verify this claim empirically, the author propose two methods: 1. examine the convergence of different frequencies in a pre-selected direction in the frequency space during training; 2. examine the convergence rate of the 2-norm of low v.s. high frequencies during training.  Through the experimental results of these two methods, the authors conclude that NNs learn the low  frequency components before the high frequency components. The authors also discuss a potential application of this observation to solving high dimensional PDEs: coupling DNNs training (good at learning low frequency components) with the Jacobi method (good at learning high frequency components). Finally, the authors also provide some theoretical intuition (Thm 1., 2.) why low frequency components are learned faster and an explanation why NNs could generalize well on images but perform poorly on tasks like learning parity functions. \n\n\nOther comments: \n1. It seems the filtering method is a better (might be a sufficient) way to justify the F-Principle than the projection method, given the projection method examines only one direction (also appointed out in the paper).  \n2. When talking about Fourier transform, would you specify what is the domain of the functions and how the functions are defined (section 3.1) The notation there is somewhat confusing (which makes the rest of the paper difficult to follow) since you are mentioning the Fourier transform of the set {(x_i, y_i)}. It will be helpful to define the function before defining its Fourier transform.  Please also mention what is the domain of the function, {x_i}_i or R^d? \n3. According to equation (4), it seems the domain of the functions is {x_i}_i, otherwise equation (4) should be a function of x\\in R^d, not x_i.  \n4. Could you elaborate why (4) is a good approximation of the low frequency energy rather than the L2 norm (over x\\in R^d) of (4) with x_i replaced by x\\in R^d. \n5. It might be useful to refine the related work section. It is not clear what are the previous contributions prior to this paper, and it seems [1] shares some similar results/observation with the this paper. \n\nOverall, I lean to a weak rejection. The key findings (and similar results, e.g. NNs learn simple functions first), i.e. F-Principle seems to have already appeared in previous works, e.g. [1] and the theoretical results of this paper are limited to an idealized setting (results of more general setting appear in another work, mentioned in the paper.)\n\n\n[1]Nasim Rahaman, Devansh Arpit, Aristide Baratin, Felix Draxler, Min Lin, Fred A Hamprecht,\nYoshua Bengio, and Aaron Courville. On the spectral bias of deep neural networks. arXiv preprint\narXiv:1806.08734, 2018. 1, 8, A \n\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1eohdR3Kr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to analyze the loss of neural networks in the Fourier domain. Since this is computationally expensive for larger-dimensional datasets, the analysis instead first projects the data onto the principal component of the data, and then using a Gaussian kernel estimation (which has nice properties in the Fourier domain). The analysis finds that DNNs tend to learn low-frequency components before high-frequency ones.\n\nOverall I quite like the analysis of this paper. I think it could be clearer and contain more experiments but it is otherwise rather convincing proof that DNNs learn low-frequency patterns first.\n\n\n- More experiments: in particular, analyzing this phenomenon over more than a single principal component or through non-linear transformations of the data.\n- It's not always clear how $\\mathbf{k}$ is calculated or where it comes from, whether it is implicit through the Gaussian metric or chosen randomly. The paper would benefit from always making this clear in the text and figure captions.\n- It's well known that different optimizers seem to learn differently both in terms of speed and features that end up being learned (thus generalization), repeating this analysis for Adam, RMSprop & friends would be great.\n\nThe paper is mostly easy to read, but there are a few mistakes here and there that slow down reading. Here are a few:\n- \"variation problems\" you mean \"variational\"?\n- \"This difference implicates\" -> \"implies\"\n- \"by the Parseval's theorem\" -> \"by Parseval's theorem\" (occurs multiple times)\n- \"difference of\" -> \"difference between\"\n- \"in previous section\" -> \"in the previous section\"\n- \"to verify F-Principle\" -> \"to verify the F-Principle\"", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BklpyIz0YB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper mainly focuses on experimental results on real data to verify the so-called Frequency Principle: DNNs often fit target functions from low to high frequencies during the training process. Some theoretical analyses are also provided to backup the empirical observation. \n\nThis paper is very well-written. The methods are explained very clearly, and the logic is easy to follow. However I think this paper also has some weak points, as listed below:\n\n(1) The frequency principle lacks a rigorous definition. In Section 2, the authors provide very inspiring explanations and examples, however no rigorous definitions are given. Is there a way to directly quantitatively define the response frequency?\n\n(2) In Section 3.1, it is not explained why the frequencies are calculated based on the samples. Probably I have missed something, but based on the description, can’t the frequencies be directly calculated on a grid along the 1-dimensional subspace defined by the mean and first principle component of the data? In other words, even after training the predictor function with real data samples for several steps, the frequency of a predictor function should still be its own property and  should be independent of the distribution of data inputs. In fact, are the vectors $n^{-1/2} (cos( 2\\pi k x_{p_1,1}), cos( 2\\pi k x_{p_1,2}), \\ldots, cos( 2\\pi k x_{p_1,n}) )$ for different $k$ even orthonormal vectors? I think unless $x_{p_1,i}$ follows certain specific distributions, these vectors are not even close to orthonormal. Therefore using them to calculate the frequencies is very weird.\n\n(3) In fact, are Sections 3,4 and 6 studying the same kind of frequency? It is not very clear due to the vague definitions.\n\nBecause of these concerns, I think this paper is on the borderline. For now I tend to recommend a weak reject.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Borderline decision.  The idea is nice, but the theory is not completely convincing.  That makes the results in this paper not be significant enough.
Decision: Reject