Frequency Principle in Deep Learning Beyond Gradient-descent-based Training

Following the suggested notation in BAAI (2020), we denote the target function by $f(x)$ and the DNN output by $f_{\theta}(x)$. For $1$-d synthetic data, $\{(x_{j},f(x_{j}))\}_{j=1}^{n}$ and $\{(x_{j},f_{\theta}(x_{j}))\}_{j=1}^{n}$, we examine the relative error of each frequency during the training. The discrete Fourier transforms (DFT) of $f(x)$ and the DNN output (denoted by $f_{\theta}(x)$) are computed by:

where $k$ is the frequency. We compute the relative difference between the DNN output and the target function for each frequencies $k$ at each training epoch, that is, $\Delta_{F}(k)=|\hat{f_{\theta}}_{k}-\hat{f}_{k}|/|\hat{f}_{k}|$, where $|\cdot|$ denotes the norm of a complex number.

F-Principle is tenable when $\Delta_{F}(k)$ converge to $0$ one by one in the training process, from low frequency components to high-frequency components. For our experiments of 1-d situation in the following texts, $\{x_{j}\}^{n}_{j=1}$ will choose evenly sampled points from $[-3.14,3.14]$ with sample size 201, and each elements in $\bm{W}^{[l]}$ and $\bm{b}^{[l]}$ are initialized by a distribution, namely, they are sampled from $N(0,\frac{2}{m_{l+1}+m_{l}})$, where $m_{l}$ is the neuron number of $l$th layer. The loss function is chosen as mean squared error (MSE) here. The activation function for fully-connected networks is sigmoid function.

For high-dimensional data, it is hard to compute the high-dimensional Fourier transform. We now introduce a filtering method proposed in Xu et al. (2019b) to examine the F-Principle in a real data set (e.g., MNIST).

We train the DNN by the original dataset $\{(\bm{x}_{i},\bm{y}_{i})\}_{i=0}^{n-1}$, where $\bm{x}_{i}$ is an image vector, $\bm{y}_{i}$ is a one-hot vector. At each training epoch, the low frequency part can be derived by a low-frequency filter, that is, the convolution with a Gaussian function,

where $C_{i}=\sum_{j=0}^{n-1}G^{\delta}(\bm{x}_{i}-\bm{x}_{j})$ is a normalization factor and $\delta$ is the variance of the following Gaussian function

The high frequency part can be derived by

We also compute $\bm{h}_{i}^{\mathrm{low},\delta}$ and $\bm{h}_{i}^{\mathrm{high},\delta}$ for each DNN output $\bm{h}_{i}=f_{\theta}(x_{i})$.

To quantify the convergence of $\bm{h}^{\mathrm{low},\delta}$ and $\bm{h}^{\mathrm{high},\delta}$, we compute the relative error $e_{\mathrm{low}}$ and $e_{\mathrm{high}}$ at each training epoch,

where $\bm{h}^{\mathrm{low},\delta}$ and $\bm{h}^{\mathrm{high},\delta}$ are obtained from the DNN output, which evolves as a function of training epoch, through the same decomposition. If $e_{\mathrm{low}}<e_{\mathrm{high}}$ for different $\delta$’s during the training, F-Principle holds; otherwise, it is falsified.

We use a MSE loss and a small sigmoid-CNN network, i.e., two convolutional layers (one convolution layer of 5$\times$5$\times$32, a max pooling of 2$\times$2, one convolution layer of 5$\times$5$\times$64, a pooling layer of 2$\times$2), followed by a fully connected multi-layer neural network 1024-10 equipped with a softmax.

Due to the memory constrained of some training algorithms, we only train 550 randomly selected samples from MNIST data, and we only perform experiments of Conjugate Gradient algorithm and L-BFGS in the following experiments. Other algorithms perform badly for the high-dimensional MNIST data.

Conjugate gradient (CG) algorithm is a popular algorithm for solving nonlinear optimization problems. The features of CG are that it requires no matrix storage and are faster than the gradient descent. The detail of CG algorithm is given in Appendix.

We use CG algorithm to train the 1-100-10-1 DNN to learn the target function with three frequency peaks, namely,

As shown in Figure 1, the DNN converges gradually from low-frequency to high frequency in Fourier analysis.

We also use CG algorithm to train a convolutional network to fit MNIST. The F-Principle also holds in the training process, see Figure 2 for different variances $\delta$ of the Gaussian function.

Truncated Newton algorithm (TNC), also called Newton Conjugate-Gradient, is a nonlinear method based on Newton method. The CG method is designed to solve positive definite systems, however, the Hessian matrix may have negative eigenvalues to lead to an inaccurate solution. TNC is a Hessian-free optimization method (Nash, 1985). The detail of TNC algorithm is given in Appendix.

In this experiment, we use TNC to train the 1-100-10-1 DNN to learn the target function with two frequency peaks, i.e., $f(x)=\sin x+\sin 3x$. Again, as shown in Figure 3, the DNN converges gradually from low-frequency to high frequency.

In our experiments, we point out that the results of training DNN by TNC to regress the target function (5) are not perfect, which is caused by the fact that the search direction is not the descent direction. This also may be influenced by the Hessian matrix, which may not keep positive definite in the training process. For $f(x)=\sin x+\sin 3x$, the low-frequency components is converged first, and it is regressed perfectly.

In this subsection, we use BFGS and L-BFGS, which are quasi-Newton methods, to train neural networks. The detail of BFGS algorithm is given in Appendix.

In Figure 4(a), we use BFGS to train a DNN of 1-100-10-1 to learn the target function (5). Similarly, the DNN converges gradually from low-frequency to high frequency.

L-BFGS uses a limited memory algorithm based on BFGS. This method only uses the data of the recent steps, which can simplify the computation and memory (Nocedal & Wright, 2006; Byrd et al., 1995). The detail of L-BFGS algorithm is given in Appendix.

In Figure 4(b), we use L-BFGS to train a DNN of 1-500-50-1 to learn the target function (5). It is clear that the DNN converges gradually from low-frequency to high frequency in this example.

We further use L-BFGS to train a CNN to learn MNIST. As shown in Fig. 5, for different filter width, we still observe that the high frequency part converges slower, that is, F-Principle.

In this section, we have used experiments to show that a training algorithm, which uses gradient information but not a gradient-descent method, can still lead to the phenomenon of F-Principle. In the next section, we would show that even using a training algorithm without using gradient information, the F-Principle can still hold.

Powell’s method, a conjugate direction method, performs sequential one-dimensional minimization along each vector of a direction set, in which the direction set is updated at each iteration (Powell, 1964). The method used here is a modification of Powell’s method. The loss function can be non-differentiable, since no derivative is taken. The detail of Powell’s method is given in Appendix.

The Powell’s method is slow in solving large scale optimization problems, such as training DNN, since it needs large internal memory and computations. Therefore, we use Powell’s method to train a small DNN of 1-100-1 to learn $f(x)=\sin x+\sin 3x$. Considering the two frequency peaks of the target function, as shown in Figure 6(a), one can see that the DNN converges the low-frequency components first.

Particle Swarm Optimization (PSO) does random search in parameter space, inspired by the moving of the swarm of birds. It can be viewed as a mid-level form of artificial life or biologically derived algorithm, and highly depends on stochastic processes. The PSO algorithm is given in appendix:

In this experiment, we use PSO to train a DNN of 1-100-10-1 to learn target function: $f(x)=\sin x+\sin 3x$. As shown in Figure 6(b), the DNN learns the low-frequency components first.

We found the F-Principle also holds in the following Monte-Carlo-Like algorithm: $\bm{\theta}_{j+1}$ is any element in

unless $S$ is empty. We train a DNN of 1-500-200-1 to learn target function $f(x)=\sin x+\sin 3x$. Considering the important frequency peaks of the target function. As shown in Figure 7, the DNN converges the low-frequency components first.