Theory of the Frequency Principle for General Deep Neural Networks

Introduction

Deep learning has achieved great success as in many fields (LeCun et al., 2015), e.g., speech recognition (Amodei et al., 2016), object recognition (Eitel et al., 2015), natural language processing (Young et al., 2018) and computer game control (Mnih et al., 2015). It has also been adopted into algorithms to solve scientific computing problems (E et al., 2017; Khoo et al., 2017; He et al., 2018; Fan et al., 2018). In principle, the universal approximation theorem states that a commonly-used Deep Neural Network (DNN) of sufficiently large width can approximate any function to a desired precision (Cybenko, 1989). However, it remains a mystery that how a DNN finds a minimum corresponding to such an approximation through the gradient-based training process. To understand the learning behavior of DNNs for the approximation problem, recent works model the gradient flow of parameters in a two-layer ReLU neural networks by a partial differential equation (PDE) in the mean-field limit (Rotskoff & Vanden-Eijnden, 2018; Mei et al., 2018; Sirignano & Spiliopoulos, 2018). However, it is not clear whether this PDE approach, which describes a neural network of one hidden layer of infinite width, can be extended to general DNNs of multiple hidden layers and limited neuron number.

In this work, we take another approach that uses Fourier analysis to study the learning behavior of DNNs based on the phenomenon of Frequency Principle (F-Principle), i.e., a DNN tends to learn a target function from low to high frequencies during the training (Xu et al., 2018; Rahaman et al., 2018; Xu, 2018a, b; Xu et al., 2019; Zhang et al., 2019). Empirically, the F-Principle can be widely observed in general DNNs for both benchmark and synthetic data (Xu et al., 2018, 2019). Conceptually, it provides a qualitative explanation of the success and failure of DNNs (Xu et al., 2019). Based on the F-Principle, a series of works has been done. For example, it is used as an important phenomenon to pursue fundamentally different learning trajectories of meta-learning (Rabinowitz, 2019). It is also used as a tool to observe the performance of adaptive activation function (Jagtap & Karniadakis, 2019). Based on the F-Principle, a numerical algorithm is developed to accelerate the DNN fitting of high frequency functions by shifting high frequencies to lower ones (Cai et al., 2019). Theoretically, an effective model of linear F-Principle dynamics (Zhang et al., 2019), which accurately predicts the learning results of two-layer ReLU neural networks of large widths, leads to an apriori estimate of the generalization bound. In addition, a theorem is provided for the characterization of the initial training stage of a two-layer $\tanh$ network (Xu et al., 2019). The same theoretical analysis in Xu et al. (2019) is also adopted in the analysis of DNNs with ReLU activation function (Rahaman et al., 2018) and a nonlinear collaborative scheme of loss functions for DNN training (Zhen et al., 2018). These subsequent works show the importance of the F-Principle. However, a theory of the F-Principle for general DNNs is still missing.

Following the same direction as in Xu et al. (2019), in this work, we propose a theoretical framework of Fourier analysis for the study of the training behavior of general DNNs in the following three stages: the initial stage, the intermediate stage, and the final stage. At all stages, we rigorously characterize the F-Principle by estimating some proper quantities. At the initial and final stages with the MSE loss (mean-squared error, also known as $L^{2}$ loss), we show that the change of MSE is dominated by low frequencies. Furthermore, in these two stages with general $L^{p}$ ($2\leq p<\infty$) loss, we show that the change of the DNN output is dominated by the low-frequency part. A key contribution of this work is on the intermediate stage — with $L^{p}$ loss, the difference of the MSE over a certain period, in which the MSE is reduced by half, is dominated by the low frequencies. In summary, we verify that the F-Principle is universal in the sense that our results not only work for DNNs of multiple layers with any commonly-used activation function, e.g., ReLU, sigmoid, and tanh, but also work for a general population density of data and for a general class of loss functions. The key insight unraveled by our analysis is that the regularity of DNN converts into the decay rate of a loss function in the frequency domain.

Preliminaries

We start with a brief introduction to DNNs and its training dynamics. Under very mild assumptions, we provide some regularity results which are crucial to the proof of the main theorems summarized in the next section.

Consider a DNN with $(H-1)$-hidden layers and general activation functions. We regard the $d$-dimensional input as the -th layer and the one-dimensional output as the $H$-th layer. Let $n_{l}$ be the number of neurons in the $l$-th layer. In particular, $n_{0}=d$ and $n_{H}=1$.

The size $N$ of the network is the number of the parameters, i.e.,

To define the hypothesis functions in $\mathcal{H}$, we need some nonlinear functions which are known as activation functions:

We remark that for the most applications, the activation functions $\sigma_{i}^{(l)}$ are chosen to be the same, i.e., $\sigma_{i}^{(l)}=\sigma$, $l=1,\cdots,H-1$, $i=1,\cdots,n_{l}$.

For instance, if a one-hidden layer neural network is used, then $H=2$ and the hypothesis function can be written into the following form:

Thus the size of the network $N=(d+2)n$ which is consistent with (4).

In the sequel, we will also refer to $h$ and $f$ as the hypothesis and target functions, respectively.

2 Loss Function and Training Dynamics

In this work, we investigate the training dynamics of parameters in DNNs with two cases of loss functions:

(i) The MSE loss function with population measure $\mu$, i.e.,

In this case, the training dynamics of $\theta$ follows the gradient flow:

(ii) A general loss function with population measure $\mu$, i.e.,

In the case of MSE loss function, we have

3 Assumptions

The requirements on $\chi$, $f$, $\sigma$, and $\mu$ are summarized here.

If an activation function is ReLU, then $k=1$.

For the training dynamics (13) or (15), we suppose the parameters are bounded.

The bound $R$ depends on initial parameter $\theta_{0}$.

In the case of MSE loss function, we will further take the following assumption.

The general loss function considered in this work satisfies the following assumption.

4 Regularity

We begin with the integrability of the hypothesis function. To achieve this, we use the “Japanese bracket” of $\xi$:

The continuity of $\sigma_{i}^{(l)}$ is neccesary because the composition of two Lebesgue measurable functions need not be Lebesgue measurable.

Suppose that the Assumptions 1 and 2 hold. Then

(c). Let $m_{1}=m-m_{2}$ and $m_{2}=\min\{m,k\}$. Then $0\leq m_{1}\leq k-1$ and $0\leq m_{2}\leq k$. Combining the inequalities in parts (a) and (b), we have

Suppose that the Assumptions 1, 2, and 4 hold. Then

Main Results

In this section, we first propose several quantitative characterization for the F-Principle. Main results are then summarized with numerical illustrations at the end of this section.

For the MSE loss function, a natural quantity to characterize the F-principle is the ratio of the loss function decrements caused by low frequencies and the total loss function decrements. To achieve this, we devide the MSE loss function into two parts, contributed by low and high frequencies, respectively, i.e.,

For a general loss function, the training dynamics leads to

However, there is an issue in this characterization: $L$ may not be monotonically decreasing and the denominator in (38) may be zero. To overcome this, a time averaging is required. Indeed, we investigate the following ratio where integrals are taken for both numerator and denominator in (38):

For the general loss function, we also propose another quantity to characterize the F-Principle:

2 Main Theorems

As we mentioned in the introduction, the training dynamics of a DNN has three stages: initial stage, intermediate stage, and final stage. For each stage, we provide a theorem to characterize the F-Principle.

We start with the F-Principle in the initial stage. Clearly, the constants $C$ in the estimates depend on the initial parameter $\theta_{0}$ and the time $T$.

[F-Principle in the initial stage] ($L^{2}$ loss function) Suppose that Assumptions 1, 2, 3, and 4 hold. We consider the training dynamics (13). Then for any $1\leq m\leq 2k-1$ and any $T>0$ satifying $\lvert\nabla_{\theta}L_{\rho}(\theta(T))\rvert>0$ (if $k=1$, we further require that $\inf_{t\in(0,T]}\lvert\nabla_{\theta}L_{\rho}(\theta(t))\rvert>0$), there is a constant $C>0$ such that

[F-Principle in the intermediate stage] (general loss function) Suppose that Assumptions 1, 2, 3, and 5 hold. We consider the training dynamics (15). Then for any $1\leq m\leq k-1$, there is a constant $C>0$ such that for any $0<T_{1}<T_{2}$ satisfying $\frac{1}{2}L(\theta(T_{1}))\geq L(\theta(T_{2}))$, we have

If non-degenerate global minimizers are achieved in the training dynamics, we can obtain global-in-time result which characterizing the training dynamics in the final stage. Here we give the definition for non-degenerate minimizers:

[F-Principle in the final stage] ($L^{2}$ loss function) Suppose that Assumptions 1, 2, 3, and 4 hold. We consider the training dynamics (13). If the solution $\theta$ converges to a non-degenerate global minimizer $\theta^{*}$, then for any $1\leq m\leq k-1$, there is a constant $C>0$ such that

(general loss function) Suppose that Assumptions 1, 2, 3, and 5 hold. We consider the training dynamics (15). If the solution $\theta$ converges to a non-degenerate global minimizer $\theta^{*}$, then for any $1\leq m\leq k-1$, there is a constant $C>0$ such that

3 Discussion and Illustrations

To help the readers get some intuitions of the above theorems, we present a numerical example using the following target function

The training data are uniformly sampled from $[-3.14,3.14]$ with sample size $300$. The discrete Fourier transform of $f(x)$ is shown in Fig. 1(a), in which we focus on the peak frequencies marked by black squares. First, we use the MSE as the training loss function.

Intermediate stage in Fig. 1 (c). The ratio of the change of the loss function in a certain period, $\lvert L_{\eta}^{+}(\theta(T_{1}))-L_{\eta}^{+}(\theta(T_{2}))\rvert/\lvert L_{\eta}(\theta(T_{1}))-L_{\eta}(\theta(T_{2}))\rvert$, increases with $\lvert T_{2}-T_{1}\rvert$ for a fixed $\eta$.

Secondly, we use the $L^{4}$ training loss $\frac{1}{M}\sum_{i=1}^{M}(h(x_{i},\theta)-y_{i})^{4}$ as shown in Fig. 2. We obtain similar results.

Proof of Theorems

In this section, we focus on the initial stage of the training dynamics. The first result shows that the change of loss function concentrates on low frequencies.

In general, $C$ may depend on $T$. In the next section, we will provide a similar result in some situation where $C$ does not depend on $T$.

The dynamics for the loss function contributed by high frequency reads as:

The dynamics for the total loss function is

Note that $\eta\leq\langle\xi\rangle$ for all $0<\eta\leq\lvert\xi\rvert$. Therefore

By Assumption 3, $\sup_{t\geq 0}\lvert\theta(t)\rvert\leq R$ and

In the situation of Theorem 1 for $L^{2}$ loss function, we have that for sufficiently large $\eta$

For sufficiently large $\eta$, the dynamics of $L^{-}_{\rho,\eta}$ is dissipative because

Next we prove the case of general loss function.

On the one hand, we estimate the numerator by studying the dynamics for $\hat{h}$:

Taking square and integrating both sides on $B_{\eta}^{c}$ leads to the upper bound on the numerator

On the other hand, note the dynamics for the hypothesis function

and the dynamics for the total loss function

where we used the Cauchy–Schwarz inequality in the last step. Combining Eqs. (56) and (59), we obtain

Again, by Assumption 3, $\sup_{t\geq 0}\lvert\theta(t)\rvert\leq R$ and

2 F-Principle: Intermediate Stage (Theorem 2)

In this section, we prove the key theorem for the intermediate stage. This theorem then implies several useful corollaries.

The numerator can be controlled as follows

where in the second-to-last step we used the Cauchy–Schwarz inequality and the Plancherel theorem, and in the last step we used the following

By Assumption 3, $\sup_{t\geq 0}\lvert\theta(t)\rvert\leq R$ and

By the assumption that $\frac{1}{2}L(\theta(T_{1}))\geq L(\theta(T_{2}))$ , we have

If $M>2L(\theta(T_{1}))$, then we choose $t_{M}\in[T_{1},T_{2}]$ such that $L(\theta(t_{M}))=M$. We have

If the condition $\frac{1}{2}L(\theta(T_{1}))\geq L(\theta(T_{2}))$ is replaced by $\delta L(\theta(T_{1}))\geq L(\theta(T_{2}))$ for any $\delta\in(0,1)$, the estimates in Theorem 2 and the following corollaries still hold.

Under the same assumptions in Theorem 2, for any $1\leq m\leq k-1$, there is a constant $C>0$ such that for any $0<T_{1}<T_{2}$ satisfying $\frac{1}{2}L(\theta(T_{1}))\geq L(\theta(T_{2}))$ and $L(\theta(T_{1}))\geq L(\theta(t))$ for all $t\in[T_{1},T_{2}]$, we have

Similar to the proof of Theorem 2, we have the upper bound for the numerator

where the last inequality is due to the same reason as Theorem 2. ∎

Under the same assumptions in Theorem 2, if the solution $\theta$ converges to a non-degenerate global minimizer $\theta^{*}$, then for any $1\leq m\leq k-1$, the above upper bound can be improved to the following: there is a constant $C>0$ such that for any $T>0$, we have

We skip the proof since this corollary can be obtained directly from Theorem 3.

3 F-Principle: Final Stage (Theorem 3)

In this section, we prove the F-Principle in final stage of the training dynamics.

By Assumption 3, $\sup_{t\geq 0}\lvert\theta(t)\rvert\leq R$ and

where we used the assumption that the minimizer is non-degenerate with the Hessian $\Lambda=\nabla_{\theta}^{2}L_{\rho}(\theta^{*})$. ∎

Now we finish the proof for general loss function.

Since $\lim_{t\to+\infty}\theta(t)=\theta^{*}$, we have

References