Frequency Principle in Deep Learning with General Loss Functions and Its Potential Application

Introduction

Deep neural networks (DNNs) has achieved many state-of-the-art results in various fields , such as object recognition, language translation and game-play. A fully understanding of why DNNs can achieve such good results remains elusive. The often used DNNs equip much more parameters than the number of the training data. As Von Neumann said “With four parameters I can fit an elephant, and with five I can make him wiggle his trunk”. It is no surprise that such DNNs can well fit the training data. However, counter-intuitive to the traditional learning theory, such DNNs often do not overfit (DNNs often generalize well to the test data which are not seen during the training), which is often referred to as “apparent paradox” .

A series of recent works , both experiments and theories, have gained us more understanding to this paradox. In this work, we focus on the Fourier analysis of DNNs . Although the often used dataset, such as MNIST and CIFAR, are relative simple compared with practical dataset, the input dimension (the pixel number of each input image) is still very high for a quantitative analysis. A good starting point to understand this apparent paradox is to find an example that is simple enough for analysis but also preserves this interesting paradox. The simple example turns out to be the fitting of a function with one-dimension (1-d) input and 1-d output . A prompt example to understand the apparent paradox is that a very high-order polynomial fitting for randomly sampled data points often overfit the training data, that is, high oscillation occurs around the sample boundary (Runge’s phenomenon); however, a DNN with small weight initialization, no matter how large size the DNN is, often learns the training data with a relative flat function . Starting from such 1-d functions, experimentally and theoretically , there exists a Frequency Principle (F-Principle) that DNNs often first quickly capture low-frequency components while keeping high-frequency ones small, and then relatively slowly captures high-frequency components. By F-Principle, the high-frequency components of the DNN output is controlled by the training data. High oscillation which exists in the Runge’s phenomenon is then absent in the DNN fitting. F-Principle also holds well in the often used dataset , that is, MNIST and CIFAR-10. Theoretical work indicates that the key ingredient underlying the F-Principle in general DNN fitting problems is that the power spectrum of the activation function decays in the Fourier space, where the power-decay property is easy to be satisfied, such as sigmoid function and rectified linear unit.

Previous studies focused on the DNN with mean square error . It is yet to study whether F-Principle applies in the DNN with other types of loss functions. This is important since loss function varies in different problems, such as image classification and solving differential equations . In this work, we perform a theoretical analysis to show that for a general loss function, e.g., cross entropy, the F-Principle qualitative holds in the DNN training, which is also verified by experiments. The first experiment is a classification problem with the loss function of cross entropy. The second experiment is to apply DNN to solve Poisson equation by using Dirichlet’s principle.

The DNN is a powerful tool to solve differential equations , especially for high-dimensional problems. It is well-known that different frequencies converge with different speeds in solving differential equations by numerical schemes. For example, for the Jacobi method, low frequency converges much slower than high frequency. Multigrid method is designed to speed up the convergence, which explicitly first captures low-frequency parts . In addition, manual frequency marching from low frequency to high frequency has achieved great success in designing numerical schemes in various problems, such as inverse scattering problems and Cryo-EM reconstruction problems . By showing F-Principle in solving Poisson’s equations, we emphasize that the DNN structure, which implicitly endows low frequency with high priority, could be a powerful tool to the problems that benefit from a fast converging of low frequency. For example, we propose an ideal that combines DNN and conventional methods (e.g., Jacobi method or Gauss-Seidel method), in which DNN is in charge of capturing low-frequency parts and conventional methods are in charge of capturing high-frequency parts. This idea is exemplified by solving a 1-d Poisson’s equation.

F-Principle with general loss function

Consider a general DNN, and denote its output as $\Upsilon_{\theta}(x)$, where $\theta$ stands for the DNN parameters and $x$ stands for the input. Represent $\Upsilon_{\theta}(x)$ with orthonormal basis $\{p_{k}(x)\}$:

where $c_{\theta,k}$ is the coefficient of mode $k$ depending on $\theta$. Denote the loss at sample $x$ as

Consider the gradient of the total loss with respect to parameter $\theta$:

$d_{k}$ is the coefficient of $\partial l(\Upsilon_{\theta}(x))/\partial\Upsilon$ at the component of $p_{k}$. Consider that $\{p_{k}(x)\}$ is Fourier basis. According to Riemann-Lebesgue lemma, if a function is an integrable function on an interval, then the Fourier coefficients of this function tend to 0 as the order $k$ tends to infinity. Therefore, when the activation function and the target function both are integrable functions on the considered interval, $c_{\theta,k}$ and $d_{k}$ tend to 0 as the order $k$ tends to infinity. Denote

Therefore, we can decompose $\partial L/\partial\theta$ into a summation of $\mathcal{L}_{k}$, which tends to 0 as the order $k$ tends to infinity. This analysis implies that for any loss function, the change of any parameter $\theta$ at each training step is affected more by lower frequencies, which would rationalize the F-Principle in general loss functions, as examined in the following experiments.

Experiment: cross entropy loss

The loss function of cross entropy is widely used in classification problems. We use experiments to show that F-Principle holds in the DNN training with this loss function.

Consider a target function $y(x)=(y_{1}(x),y_{2}(x))$, where

This fitting problem is a toy classification problem. In the DNN in this problem, the output layer has two neurons with softmax as activation function. The output is denoted as $\Upsilon(x)=(\Upsilon_{1}(x),\Upsilon_{2}(x))$. The loss function is

For illustration, we focus on $y_{1}(x)$, which is shown in Fig.1a. Next, we examine the convergence of different frequencies. In a finite interval, the frequency components of a target function are quantified by Fourier coefficients computed from Discrete Fourier Transform (DFT). Note that because the frequency in DFT is discrete, we can refer to a frequency component by its index instead of its physical frequency. The Fourier coefficient of $y_{1}(x)$ for the $\gamma$-th frequency component is denoted by $F[y_{1}](\gamma)$ (a complex number in general). $|F[y_{1}](\gamma)|$ is the corresponding amplitude, where $|\cdot|$ denotes the absolute value. Note that we call $\gamma$ the frequency index. $|F[y_{1}](\gamma)|$ is shown in Fig. 1b. To examine the convergence behavior of different frequency components during the training of a DNN, we compute the relative difference of the DNN output $\Upsilon_{1}(x)$ and $y_{1}(x)$ in frequency domain at each recording step, i.e.,

During the training, $\Upsilon_{1}(x)$ captures $y_{1}(x)$ from low to high frequency in a clear order, as shown in Fig.1c.

2 MNIST data

To verify that the F-Principle holds in the image classification problems (MNIST) with the loss function of cross entropy, we perform Fourier analysis in the first principle component of the input space. The procedure is as follows.

Then, the sample set is $S=\{(x_{0},\vec{y}_{0}),(x_{1},\vec{y}_{1}),\cdots,(x_{n-1},\vec{y}_{n-1})$. For illustration, we only consider the first component of $\vec{y}$, i.e., $\vec{y}^{(1)}$. Note that now $\{x_{k}\}_{k=0}^{n-1}$ is a non-uniform sampling. Using non-uniform FFT (NUFFT), we can obtain

Then, the sampling on the Fourier domain is

After each training step, we feed each $\vec{x}_{k}$ into the DNN and obtain the DNN output $\Upsilon(\vec{x}_{k})$:

Using non-uniform FFT (NUFFT), similarly, we can obtain the sampling of the DNN’s first dimension output on the Fourier domain

which is shown in Fig.2a. We then examine the relative error of certain selected important frequency components (marked by black squares). As shown in the first column in Fig.2b, we can observe that the DNN tends to capture low-frequency components first.

Experiment: Poisson’s equations

Consider one-dimension (1-d) Poisson’s equation :

The Poisson’s equation can be solved by numerical schemes (e.g., Jacobi method) or DNN. As well known, high frequency converges faster in the Jacobi method. In the following, we would show that high frequency converges slower when the DNN is applied to solve the above Poisson’s equation.

$$is uniformly discretized into$n+1$points with step$\Delta x=2/n$, i.e.,$x_{0},x_{1},\cdots,x_{n}$. The Poisson’s equation in Eq. (21) can be solved by central differencing scheme:

If $n$ is not a large number, Eq. (23) can be solved by performing the inverse of $A$. When $n$ is a very large number, this problem can be solved by iterative schemes. For example, we illustrate the Jacobi method. Let $A=D-L-U$, where $D$ is diagonal, and $L$ and $U$ are the strictly lower and upper parts of $-A$, respectively. Then, we can obtain

We perform error analysis of the above iteration process. Denote $u^{*}$ as the true value obtained by directly performing inverse of $A$ in Eq. (23). The error at step $l+1$ is $e^{l+1}=u^{l+1}-u^{*}$. Then, $e^{l+1}=R_{J}e^{l}$, where $R_{J}=D^{-1}(L+U)$. The converging speed of $e^{l}$ is determined by the eigenvalues of $R_{J}$, that is,

and the corresponding eigenvector $v_{k}$ is

where $\alpha_{k}^{l}$ can be understood as the magnitude of $e^{l}$ in the direction of $v_{k}$. Then,

Therefore, the converging speed of $e^{l}$ in the direction of $v_{k}$ is controlled by $\lambda_{k}$. Since

the frequencies $k$ and $(n-k)$ are closely related and converge with the same speed. Consider the frequency $k<n/2$, $\lambda_{k}$ is larger for lower frequency. Therefor, lower frequency converges slower in the Jacobi method.

2 DNN approach

Similar as the loss function in Ref , we consider the following loss function (energy method)

It is equivalent to solve Poisson’s equation by finding the function that minimizes $I(u)$ (Dirichlet’s principle) . The last term in $I(u)$ is a penalty in order to satisfy the boundary condition. The DNN structure is 1-d input (i.e., $x$) and 1-d output (denoted as $\Upsilon(x)$) for solving Eq. (21). $\beta$ is a constant.

The procedure is similar. We discretized $$into$n+1$even-space points. In each training step, we compute$\Upsilon(x_{i})$for$i=0,1,2,\cdots n$. The gradient of$I(\Upsilon)$with respect to parameter$\Theta$ is

At each training step, we compare $\Upsilon(x)$ and $u^{*}(x)$ in the Fourier domain. Note that $u^{*}(x)$ is the one obtained by directly performing inverse of $A$ in Eq. (23).

3 Experiment

As shown in Fig. 3a, after training, the DNN output can well fit the solution $u^{*}$ obtained by directly performing inverse of $A$ in Eq. (23). As shown in Fig. 3b, there are three peaks of $u^{*}$ in the Fourier domain.

To examine the convergence behavior of different frequency components during the DNN training, we compute the relative difference of the DNN output $\Upsilon(x)$ and $u^{*}(x)$ in frequency domain at each recording step, i.e.,

As shown in Fig. 3c, F-Principle holds well in solving Poisson’s equation . For comparison, we also show that low frequency converges much slower than high frequency in Jacobi method, as shown in Fig. 3d.

Combination of DNN and convention methods

In light of the above numerical simulations, it is natural to consider if we can combine DNN and Jacobi method to solve the Poisson’s equation. For simplicity, we call the combination method D-Jacobi method.

In the first part of D-Jacobi method, we solve the Poisson’s equation by DNN with $M$ steps. In the second part, we use the DNN output at step $M$ as the initial value for the Jacobi method.

We solve the problem in Fig. 3 by a laptop (Dell, Precision 5510). As shown in Fig.4a, the DNN loss fluctuates after some running time. We use Jacobi method to solve the problem after some time points, which are indicated by vertical dashed lines. As shown in Fig.4b (Fig.4c), green stars indicates the $|\Upsilon-u^{*}|_{\infty}$ of the DNN output at different steps. Dashed lines indicates the evolution of the Jacobi (Gauss-Seidel) method. As we can see, if the selected timing is too early, it would still take long time to converge to a small error, because the low frequencies are not converged, yet. If the selected timing is too late, much time would be waste because the DNN is hard to capture high frequencies and fluctuates a lot. The selected timing of the green or the red one is a better choice. In practice, a better way to select the timing is when the loss gets flat and fluctuated for a short while.

Discussion

In this work, we have shown that F-Principle holds well in the DNN training with a general loss function, extending the study of F-Principle in the loss function of mean square error in previous works . Along with the previous study that F-Principle holds in both DNN and convolutional neural networks with the activation function of either tanh or Relu , these works implicate that the F-Principle may provide understandings to the generalization ability of general DNNs.

We also show that the generality of F-Principle in the DNN training could potentially be useful in designing algorithms for solving practical problems. To be specific, we apply DNN to solve 1-d Poisson’s equation. Compared with conventional numerical schemes, DNN could potentially work better in rather high dimensions . In addition, it does not requires discretization for the DNN method, which would be much easier to be implemented. In future, it would be interested to use DNN’s F-Principle to develop numerical schemes for solving various problems which would benefit from a fast converging of low frequency.

Acknowledgments

The author wants to thank Weinan E, Wei Cai for helpful discussion. The author also wants to thank Tao Luo, Zheng Ma, Yanyang Xiao and Yaoyu Zhang for the discussion of the F-Principle. This work was funded by the NYU Abu Dhabi Institute G1301.