Title: A SPECTRAL APPROACH TO GENERALIZATION AND OPTIMIZATION IN NEURAL NETWORKS

Abstract: The recent success of deep neural networks stems from their ability to generalize well on real data; however, Zhang et al. (Zhang et al., 2016) have observed that neural networks can easily overfit random labels. This observation demonstrates that with the existing theory, we cannot adequately explain why gradient methods can find generalizable solutions for neural networks. In this work, we use a Fourierbased approach to study the generalization properties of gradient-based methods over 2-layer neural networks with sinusoidal activation functions. We prove that if the underlying distribution of data has nice spectral properties such as bandlimitedness, then the gradient descent method will converge to generalizable local minima. We also establish a Fourier-based generalization bound for bandlimited spaces, which generalizes to other activation functions. Our generalization bound motivates a grouped version of path norms for measuring the complexity of 2-layer neural networks with ReLU activation functions. We demonstrate numerically that regularization of this group path norm results in neural network solutions that can fit true labels without losing test accuracy while not overfitting random labels.

1. INTRODUCTION:

Deep neural networks (DNNs) have achieved state-of-the-art performance on a wide array of diverse tasks (LeCun et al., 2015) . A given DNN architecture represents a highly rich space of hypotheses. However, numerous empirical results have demonstrated that a simple stochastic gradient descent (SGD) learner can efficiently search over this space to find a solution that achieves high performance on both training and test data. Despite many successful applications of DNNs to practical tasks such as computer vision (Krizhevsky et al., 2012) , natural language processing (Collobert & Weston, 2008) and speech recognition (Hinton et al., 2012) , our basic understanding of the factors that drive DNN generalization is still lacking.

Addressing generalization for DNNs is hard for two fundamental reasons: 1) Empirical risk minimization for neural networks is a non-convex optimization problem with possibly many local minima, and 2) Two different local minima with the same training performance can achieve significantly different performance on test data. For these reasons, the neural network optimization method plays an important role in the generalizability of the local minima found. For example, SGD has been empirically shown to outperform large-batch gradient descent (Keskar et al., 2016) . Also, the performance of gradient methods can be improved upon by incorporating the geometry of observed data (Duchi et al., 2011; Neyshabur et al., 2015a) .

For DNNs, however, a good optimization method is not sufficient for guaranteeing good generalization. Zhang et al. (Zhang et al., 2016) empirically demonstrate that a neural network trained by SGD can easily overfit random labels on the CIFAR-10 ( Krizhevsky & Hinton, 2009) data. Yet, the same neural network fitted by the same SGD algorithm achieves good generalization performance for the original CIFAR-10 labels. This observation challenges the ability of traditional learning theory to explain why SGD learns generalizable hypotheses over neural networks. To shed light on this phenomenon, two recent works have developed generalization bounds and complexity measures for neural networks which can distinguish the local minima found for true and random labels. (Bartlett et al., 2017) proves a margin-based generalization bound and shows how it correlates with the generalization risk of DNNs when fitting true and random labels. (Neyshabur et al., 2017) explores different complexity scores for DNNs and how they behave differently for true and random labels. The complexity measures investigated in these works can effectively distinguish generalizable from poorly-generalizable local with true and random labels on a 2-layer neural network with 512 ReLU hidden units, regularized with an additive penalty: (b1) no penalty, (b2) 2 -norm, (b3) χ 2 -group path norm, (b4) 1 -path norm. The χ 2 -group path norm and 1 -path norm were successful to close the generalization gap for both true and random labels.

minima. They do not explain, however, why SGD converges to generalizable local minima when there exist poorly-generalizable local minima which can also perfectly fit the training set.

To approach this question, one needs to understand the key characteristic of CIFAR-10's original labeling which differentiates it from random labels and how it is exploited by SGD to achieve good generalization performance. In this work, we approach this problem in the Fourier domain where non-random labeling schemes behave completely differently from random labeling schemes. While signals recoverable from few measurements possess nice spectral properties such as bandlimitedness, fully random stochastic processes are not bandlimited and not recoverable from any finite number of measurements.

Using spectral analysis, we focus on characterizing spectral properties of an underlying distribution which can be exploited by gradient-based methods to converge to generalizable local minima. We address this problem for 2-layer neural networks (see Figure 1a ) with sinusoidal activation functions, where we show that if the underlying labeling scheme has limited bandwidth and Fourier 1 -norm (i.e. "nice" Fourier properties), we expect a gradient-based method to achieve good generalization performance. To arrive at this result, we first develop a Fourier-based generalization bound for 2-layer neural networks in terms of bandwidth and Fourier 1 -norm. Next, we prove that the local minima found by the gradient descent method over a 2-layer neural network with sine activation have bandwidth and Fourier 1 -norm bounded in terms of the spectral properties of the underlying labeling scheme.

As a byproduct of our Fourier analysis, we derive generalization bounds for 2-layer neural networks with general activation functions. For bandlimited activation functions with finite Fourier 1 -norm, such as sinusoidal or Gaussian activation1 , our bound is tighter than the generalization bound obtained using only the Lipschitz constant of the activation function. For ReLU-type activation functions, our generalization bound is comparable to Lipschitz-based bounds; however, it leads to a grouped version of the path norms developed in (Neyshabur et al., 2015a) . We therefore call this capacity norm group path norm which can be used as an additive penalty to regularize 2-layer neural networks with ReLU activation. Our numerical experiments suggest that the generalization gap can be effectively tightened by regularizing the group path norm. Figure 1b demonstrates how group path norm regularization can help close the generalization gap for both true and random labels.

Generalization has been a topic of central interest in statistical learning theory (Vapnik, 1999; Shalev-Shwartz & Ben-David, 2014) . Generalization bounds have been derived using the stability of a learning algorithm (Bousquet & Elisseeff, 2002) and various complexity measures of a function space such as VC-dimension (Vapnik, 2013) and Rademacher complexity (Bartlett & Mendelson, 2002) . (Hardt et al., 2015) develops a stability-based generalization result for SGD as the learning algorithm, which holds for both convex and non-convex loss functions.

We note that spectral analysis has provided a powerful framework for studying neural networks.

(Barron, 1993) uses a Fourier-based approach to prove the universal approximation theorem for 2-layer neural networks. Similarly, (Lee et al., 2017) applies Fourier analysis to extend Barron's result to a general feedforward neural network. (Rippel et al., 2015) uses a spectral approach to model and analyze convolutional neural networks (CNNs) and introduce the spectral pooling scheme for CNNs. Also, our Fourier-based approach to analyze SGD's performance for 2-layer neural networks follows the same prinicples as the analysis performed in (Shamir, 2016) to prove the hardness of fitting periodic labeling schemes via gradient-based methods. We should note that in this work we use only periodic activation functions and not periodic labeling schemes. Therefore, the hardness result shown in (Shamir, 2016) does not affect our numerical experiments.

In general, theoretical studies of neural networks can be categorized into three main categories: 1) Approximation: Neural networks have been proven to be powerful in expressing a very rich class of functions (Cybenko, 1989) and in general deeper networks need fewer neurons to express the same class of functions (Eldan & Shamir, 2016; Liang & Srikant, 2016) . 2) Generalization: Tight bounds have been shown on the VC dimesnion of feedforward neural networks (Anthony & Bartlett, 2009; Harvey et al., 2017) . Also, norm-based Rademacher complexity bounds have been developed at (Bartlett & Mendelson, 2002; Neyshabur et al., 2015b) . Sharpness of local minima and its connection to their generalizibility have been the focus of several recent works (Keskar et al., 2016; Dinh et al., 2017; Neyshabur et al., 2017) 3) Optimization: theoretical studies have shown both positive (Andoni et al., 2014; Daniely, 2017) and negative (Shalev-Shwartz et al., 2017) results about the performance of gradient-based methods in training neural networks.

3. PRELIMINARIES:



3.1. SUPERVISED LEARNING AND GENERALIZATION:

Suppose that we are given n samples (x i , y i ) n i=1 drawn i.i.d. from a population distribution P X,Y . Here X denotes the random vector of features and Y denotes the target variable. Using these n samples, the goal of a supervised learner is to find a prediction rule f from a function space F which can predict Y for an unseen test sample X. Therefore, given loss function the supervised learner wants to find f * ∈ F minimizing the population risk, defined as E f (X), Y averaged under the population distribution.

However, the supervised learner does not know the population distribution P X,Y and has only access to the n training samples. The supervised learner can minimize the empirical risk, defined as 1/n n i=1 f (x i ), y i and find f emp n . Since we only observe a limited number of samples, the empirical risk would be different from the population risk. The generalization risk, defined for

f ∈ F as E[ (f (X), Y )] -1 n n i=1 (f (x i ), y i ),

is the difference among the population risk and empirical risk for f . Studying the behavior of f emp n 's generalization risk for different function spaces and learning algorithms is a topic of central interest in statistical learning theory.

3.2. FOURIER TRANSFORM AND BANDLIMITED FUNCTIONS:

Consider a real-valued function f : R k → R. The Fourier transform of this function, which we denote by f , is defined as

f (ξ) = f (x) exp -2πiξ T x dx.

(1)

Some important examples of Fourier transform are:

• Sinusoidal function: f (x) = exp(2πiω T x), then f (ξ) = δ(ξ -ω)

where δ denotes the Dirac delta function, which also implies

-f (x) = cos(2πω T x), then f (ξ) = 1/2 δ(ξ + ω) + δ(ξ -ω) . -f (x) = sin(2πω T x), then f (ξ) = i/2 δ(ξ + ω) -δ(ξ -ω) .

• Gaussian function:

f (x) = ( √ 2πσ) k exp -x 2 2 /2σ 2 , then f (ξ) = exp -σ 2 ξ 2 2 /2

. Thus, the Fourier transform of a Gaussian function preserves the Gaussian shape.

A function f is called B-bandlimited if f (ξ) = 0 for every ξ where ξ 2 > B. The smallest B for which this property holds is called the bandwidth of f . We use B(f ) to denote the bandwidth of function f . We also use f 1 to denote the 1 -norm of f 's Fourier transform,

f 1 = | f (ξ)| dξ (2)

which we call the Fourier 1 -norm of f . Fourier 1 -norm can be interpreted as the absolute volume under f 's Fourier transform, and is an approximate measure of f 's sparsity. Fourier 1 -norm is both scale and shift invariant, i.e. if we define g(x) = f (Wx + b) for a real-valued f and W ∈ R r×k and b ∈ R r for some r ≤ k, then g 1 = f 1 . Some other useful properties of Fourier transform are:

• Synthesis: f (x) = f (ξ) exp 2πiξ T x dξ, which also implies f 1 = f (0) if f is real and non-negative. • Shift: f b (ξ) = exp(2πib T ξ) f (ξ) where f b (x) := f (x -b), which implies f b 1 = f 1 and B(f b ) = B(f ).

• Derivative: ∇f (ξ) = 2πi f (ξ) ξ, where ∇f denotes the gradient of f .

• Isometry: f (x)g(x) dx = f (ξ) g(ξ) dξ where z denotes the complex conjugate of z.

• Convolution: f g = f g where denotes the convolution operator i.e. f g(ξ

) := f (η) g(ξ -η) dη. Therefore, B(f g) ≤ B(f ) + B(g) and f g 1 ≤ f 1 g 1 .

4. A FOURIER-BASED GENERALIZATION BOUND:

Consider a supervised learning task with n training samples x i , y i n i=1 and function space F. We are interested in uniform convergence bounds on the generalization risk. A standard approach to bound the generalization risk is based on the notion of Rademacher complexity. Given samples x i , y i n i=1 , the empirical Rademacher complexity of F is defined as

EQUATION

where σ i 's are i.i.d. random variables uniformly distributed over {-1, +1}. In fact, the Rademacher complexity of F measures how well F can fit some random labels over input x i 's. The following result shows how to bound the generalization risk over F through its Rademacher complexity.

Theorem 1 (Bartlett & Mendelson (2002) ). Consider a ρ-Lipschitz loss function (f (x), y) bounded as | (z, y)| ≤ c. Then, for any δ > 0, with probability at least 1 -δ

EQUATION

Since the Rademacher complexity of norm-bounded linear functions can be appropriately bounded (Kakade et al., 2009) , one can effectively apply Theorem 1 to bound generalization risk over normbounded linear functions. To use Theorem 1 in the Fourier domain, here we provide a Rademacher complexity bound for bandlimited functions with bounded Fourier 1 -norm. We apply the following Rademacher complexity bound to bound generalization risk for 2-layer neural networks in Section 5, and also to analyze the performance of gradient-based methods with sinusoidal activation functions in Section 6.

Theorem 2. Consider function space

F = f : R k → R s.t. B(f ) ≤ B, f 1 ≤ V of B-

bandlimited functions with V -bounded Fourier 1 -norm. Then, the empirical Rademacher complexity for samples (x i , y i ) n i=1 is bounded as

EQUATION

Proof. We defer the proof to the Appendix.

Corollary 1. Assume that X 2 ≤ C holds almost surely and the loss function is ρ-Lipschitz.

Then, for any δ > 0 with probability at least 1 -δ the following generalization bound holds for any B-bandlimited function f with V -bounded Fourier 1 -norm:

EQUATION

)

Proof. The corrollary is a direct result of applying the bound in Theorem 2 to Theorem 1.

The above corollary bounds the generalization risk uniformly over all bandlimited f 's such that B(f ) ≤ B and f 1 ≤ V . Next, we apply the above results to 2-layer neural networks.

5. APPLICATION OF THEOREM 2 TO 2-LAYER NEURAL NETWORKS:

Consider a 2-layer neural network including d neurons with activation function φ in the hidden layer (See Figure 1a ). The output of this neural network is

EQUATION

If φ has bounded bandwidth and Fourier 1 -norm, we can apply Theorem 2 to bound the Rademacher complexity and hence generalization risk over the 2-layer neural network. Here, we use W 2,∞ to denote the maximum 2 -norm w i 2 among all rows of W.

Corollary 2. Let F φ = f (x) = a T φ(Wx + b) : W 2,∞ ≤ W, a 1 ≤

A be the class of 2-layer neural networks where B(φ) = B and φ 1 = V . Then, the empirical Rademacher complexity of F φ for samples (x i , y i ) n i=1 is bounded as follows

EQUATION

Proof. We defer the proof to the Appendix.

Notice that for bandlimited activation functions with bounded Fourier 1 -norm, the above generalization bound is increasing logarithmically with W 2,∞ . For example, this result holds for sinusoidal activation φ(x) = sin(2πx) where φ 1 = 1, B(φ) = 1. On the other hand, the existing Rademacher complexity bounds which use only the Lipschitz constant of the activation function are linear in W's norm (Bartlett & Mendelson, 2002) . Therefore, by exploiting the spectral properties of φ, Corollary 2 results in a tighter generalization bound than the bounds using only the Lipschitz constant of φ.

However, an unbounded function such as ReLU φ(x) = max(x, 0) has an infinite Fourier 1 -norm. Therefore, Corollary 2 does not directly apply to these functions. The following theorem uses a boundedness assumption on input X to apply Theorem 2 to ReLU-type activation functions. Although the following bound is growing faster than logarithmically with W's norm, it introduces new capacity norms for 2-layer ReLU-based networks. Theorem 3. Suppose that φ α (x) = max{x, αx} where α ∈ [0, 1] is an arbitrary constant. Consider the pair of dual norms ( • p , • q ) where 1 ≤ p, q ≤ ∞ and 1/p + 1/q = 1. Assume that x i p ≤ C holds for all x i 's. Then, for F φα = f a,W (x) = a T φ α (Wx) :

EQUATION

Proof. We relegate the proof to the Appendix.

The above bound uses the complexity score d i=1 |a i | w i q for each f a,W (x) = a T φ α (Wx). We can rewrite this complexity score in the following way, which is an 1,q -group norm on the product of weights for each path from the input nodes to the output node of the 2-layer neural network,

EQUATION

)

Here w i,j denotes the weight on the link from the jth node of the input layer to the ith node of the hidden layer. Based on the path-norm function defined at (Neyshabur et al., 2015a), we call χ q f a,W the group path norm. For q = 1, χ 1 -group path norm leads to the 1 -path norm for 2-layer neural networks. We can use group path norms as an additive regularization penalty to learn over 2-layer neural networks. In our numerical experiments, we test the performance of χ 2 -group path norm and 1 -path norm regularization to control the generalization risk over 2-layer neural networks.

6. FOURIER ANALYSIS OF GRADIENT-BASED METHODS FOR 2-LAYER NEURAL NETWORKS WITH SINE ACTIVATION:

In this section, we apply Fourier analysis for a 2-layer neural network with sinusoidal activation. We aim to understand the connection between generalizibility of local minima found by gradient-based methods and spectral properties of the population distribution P X,Y . As a simplifying assumption, let's assume that target variable Y is a deterministic function Y (x) of input X, which we call the labeling scheme. In our analysis, we consider the squared-error loss (y, y ) = (y -y ) 2 .

We specifically ask this question: how can spectral properties of labeling scheme Y (x) and population density function P X (x) affect the generalization performance of a gradient-based method? To address this question, we use a similar strategy to the analysis performed in (Mei et al., 2016) by establishing generalization results for both the empirical risk and the gradient of empirical risk. First, we show that the bandwidth and Fourier 1 -norm for the local minima of the population risk can be bounded in terms of the bandwidth and Fourier 1 -norm of Y (x) and P X (x). Next, we establish a generalization result for the gradient of the empirical risk, proving that the gradient of empirical risk would stay close to the gradient of population risk given that Y (x) has limited bandwidth and Fourier 1 -norm. These two results show that by assuming a labeling scheme with limited bandwidth and Fourier 1 -norm, the local minima found by the gradient descent (in general large-batch gradient descent) method will generalize well.

6.1. POPULATION RISK WITH SINUSOIDAL ACTIVATION:

Consider f a,W,b (x) = d j=1 a j sin(2πw T j x + b j ) coming from a 2-layer neural network with d sinusoidal hidden units. Given the labeling scheme Y (x) the population risk will be

EQUATION

)

where the expectation is according to the population density function P X (x). Lemma 1. Consider the population risk in (11). Assume w j satisfies ∀ i = j : min w iw j 2 , w i +w j 2 > B(P X ). Then, if (a, W, b) is assumed to be a local minimum of the population risk,

EQUATION

)

Proof. We defer the proof to the Appendix.

Lemma 1 says that if the component a j sin(2πw T j x) becomes isolated for a local minimum, by which we mean there are no other component a i sin(2πw T i x) with min{ w i -w j 2 , w i + w j 2 } less than P X 's bandwidth, then the value of a j for that local minimum is nicely bounded in terms of the population distribution. This result leads to the following Theorem which describes the Fourier properties of the local minima of the population risk. 

* i -w * j 2 , w * i + w * j 2 > 2 B(P X ), then for the local minimum function f a * ,W * ,b * • B(f a * ,W * ,b * ) ≤ B(Y ) + B(P X ), • f a * ,W * ,b * 1 ≤ 2 Y 1 .

Proof. We defer the proof to the Appendix.

Theorem 4 implies that the bandwidth of the local minima of the population risk is less than the sum of bandwidths for Y and P X . Also, the Fourier 1 -norm for the local minima of the population distribution is bounded by twice the Fourier 1 -norm of Y . Remark 1. To apply Theorem 4, the bandwidth of P X needs to be smaller than half the distance among w * i 's. For example, suppose that X ∼ N (µ, σ 2 I k×k ) has a multivariate Gaussian distribution with mean µ and diagonal covariance matrix with standard deviation σ. Then, the above theorem shows that if for any i, j we have min w

* i -w * j 2 , w * i + w * j 2 > 2C/σ for some constant C, then • B(f a * ,W * ,b * ) ≤ B(Y ) + O √ k/σ , • f a * ,W * ,b * 1 ≤ 2(1 + d exp(-C 2 /2)) Y 1 .

Proof. See the proof of Theorem 4 in the Appendix.

6.2. GENERALIZATION TO THE EMPIRICAL RISK:

Theorem 4 characterizes the Fourier properties of the local minima for the population risk. However, we want to investigate the generalization performance of the local minima of the empirical risk defined for training samples (x i , Y (x i )) n i=1 as

EQUATION

)

To address this question, note that the bandwidth and Fourier 1 -norm of the loss's gradient with respect to each a j are bounded in terms of the bandwidth and Fourier 1 -norm of Y (x) as

EQUATION

EQUATION

We can apply Corollary 1 to show that not only the empirical risk uniformly converges to the population risk but also the gradient of the empirical risk will stay close to the gradient of the population risk.

Corollary 3. Consider f a,W,b (x) = d j=1 a j sin(w T j x + b j ) and squared error loss . Then, given that X 2 ≤ C, for any δ > 0 with probability at least 1 -δ we have

∀ j, a, W, b s.t. a 1 + Y 1 ≤ V, 2 W 2,∞ + B(Y ) ≤ B : (16) E ∇ aj f a,W,b (X), Y (X) - 1 n n i=1 ∇ aj f a,W,b (x i ), Y (x i ) ≤ O V k log nBC/δ n .

Proof. The corollary is a direct result of Corollary (1) given ( 14) and ( 15). Note that the generalization bound holds with probability 1 -δ for the derivative with respect to all a j 's, since the bounds in ( 14) and ( 15) hold for all j's.

We emphasize that to prove Theorem 4 we need to analyze the risk function's derivative only with respect to a j 's. Hence, generalization of the empirical risk's gradient with respect to a j 's, which is , and also

f a * ,W * ,b * 1 ≤ 2 Y 1 + O dV k log(nBC/δ n .

Based on the above discussion, if a large-batch gradient descent method starts learning from f a,W,b with low a 1 and W 2,∞ and also we assume that the bandwidth and the Fourier 1 -norm for Y (x) are properly bounded, Theorem 4 combined with Corollary 1 will guarantee good generalization performance for the local minima found by the gradient descent method.

7. NUMERICAL EXPERIMENTS:

For all experiments described in this section, we implemented and trained the two-layer neural network described in Figure 1a using TensorFlow 1.3.0. We used SGD to train the model for 2000 epochs with an initial learning rate of 0.01. The learning rate decayed slightly each epoch at a rate of 0.95 every 390 epochs. We used h = 512 hidden units and a batch size of 128. When working with CIFAR10 data, we preprocessed the data as described in (Zhang et al., 2016) , resulting in each training sample having dimension d = 2352. Initial weights from the first layer were sampled from N (0, 0.01/d) and initial weights from the second layer were sampled from N (0, 0.01/h).

7.1. SGD GRADUALLY LEARNS HIGHER FOURIER 1 -NORM, BANDWIDTH HYPOTHESES:

We first numerically demonstrate that how Fourier 1 -norm and bandwidth both increases during training via SGD. Motivated by the analysis from Section 6, we use the squared-error as our loss function and sine as our activation function. Our samples consist of cats and airplanes from the CIFAR10 dataset with the labels mapped to -1 and 1. We use 5000 and 2000 samples from each category for training and test, respectively. We arbitrarily chose two of the ten classes to accommodate our choice of loss function. We evaluate the network's performance for both random and true labels.

Figure 2a shows that without regularization, SGD learns to perfectly fit both the true and random labels, which is consistent with the results from Zhang et al. (2016) . Additionally, the random labels are harder to learn, requiring more epochs before achieving a perfect fit. Figures 2b and 2c confirm that both Fourier 1 -norm and bandwidth consistently increase with training, highlighting how SGD gradually finds more complex hypotheses in order to fit the data. Finally, we see in figures 2d and 2e how both Fourier 1 -norm and bandwidth increase with generalization risk (the difference between test mean squared-error (MSE) and training MSE) with almost perfect correlation. This suggests that, as implied by the theory above, regularizing Fourier 1 -norm and bandwidth could improve generalizability of the final learned model.

7.2. GROUP PATH NORM REGULARIZATION FOR RELU ACTIVATION:

We regularize group path norm for ReLU activation as motivated by Theorem 3. Although χ 2 -group path norm is not convex, it is differentiable and we can use it as an additive penalty and find a local minimum via SGD. Using the same experimental setup as from section 7.1, we swap sine for ReLU and test the network's performance for both random and true labels.

Figure 3a confirms that, like before, the network can fit both true and random labels. The generalization gap, however, remains large for random labels. By regularizing the 2 -norm of all the weights, we see that the generalization gap closes for both the true labels and the random labels without compromising test accuracy significantly (Figure 3b ). This result is further improved when we use the χ 2 -group path norm and 1 -path norm (Figure 3c and 3d ), demonstrating that direct regularization of Fourier 1 -norm leads to better generalization.

We cross-validated the value of λ for each regularization technique, and we chose the λ that resulted in the smallest generalization gap with comparable validation performance. To fairly compare different regularization strategies, we tested five lambda values for each strategy and then reported the performance on the test set for the lambda value that resulted in the best performance on the validation set.

We repeated the experiment using all 50000 CIFAR10 training samples (and 10000 test samples). We included all 10 classes and switched to cross-entropy loss. The results are shown in Figure 1b . Again, we see that while all regularization techniques give similar test performance, the generalization gap is closed significantly for the χ 2 -group path norm and 1 -path norm.

Ohad Shamir. Distribution-specific hardness of learning neural networks. arXiv preprint arXiv:1609.01037, 2016.

Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.

Vladimir N Vapnik. An overview of statistical learning theory. IEEE transactions on neural networks, 10(5): 988-999, 1999.

Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016.

8. APPENDIX:

8.1 PROOF OF THEOREM 2

We use a high-dimensional grid in the Fourier domain to approximate the Fourier transform of a B-bandlimited function. Consider the ball ξ : ξ 2 ≤ B . Using the bounds on the covering number for 2-norm, for any 0 < < B we can find a set of points {ξ j : 1 ≤ j ≤ (3B/ ) k } such that for any ξ with ξ 2 ≤ B, there exists some ξ j with ξξ j 2 ≤ .

Let Sj = {ξ : ξξ j 2 ≤ } for each 1 ≤ j ≤ (3B/ ) k . Note that {ξ : ξ 2 ≤ B} ⊂ ∪jSj. We then define S j = Sj \ ∪ j-1 t=1 St to have a group of disjoint sets S j covering {ξ : ξ 2 ≤ B}. Since any f ∈ F is assumed to be B-bandlimited, for f ∈ F

EQUATION

Then, for any f ∈ F = {f : B(f

) ≤ B, f 1 ≤ V } we have f (x) - (3B/ ) k j=1 exp(2πiξ T j x) ξ∈S j f (ξ) dξ (a) = (3B/ ) k j=1 ξ∈S j f (ξ) exp(2πiξ T x) -exp(2πiξ T j x) dξ ≤ (3B/ ) k j=1 ξ∈S j f (ξ) exp(2πiξ T x) -exp(2πiξ T j x) dξ (b) ≤ (3B/ ) k j=1 ξ∈S j f (ξ) 2π x 2 ξ -ξ j 2 dξ ≤ 2π x 2 (3B/ ) k j=1 ξ∈S j f (ξ) ξ -ξ j 2 dξ (c) ≤ 2π x 2 (3B/ ) k j=1 ξ∈S j f (ξ) dξ = 2π x 2 f (ξ) dξ ≤ 2π x 2V.

Here, (a) is a direct application of ( 17 Therefore, the following function space F can approximate any f ∈ F = f : B(f ) ≤ B, f 1 ≤ V within 2π CV accuracy for any x 2 ≤ C. Here a is, in general, a vector of complex numbers, and a 1 := j |aj| where |z| denotes the absolute value of complex number z,

EQUATION

Then, F is the space of 1-norm bounded linear functions in terms of the input vector exp(2πiξ T j x) j . Now, we can apply a well-known bound (Shalev-Shwartz & Ben-David, 2014) on the Rademacher complexity of 1-norm bounded linear space Flin,1

EQUATION

)

Applying the above bound, we can bound the Rademacher complexity of F as

EQUATION

)

Since for each f ∈ F there exists

EQUATION

Finally, combining ( 20) and ( 21) we obtain:

EQUATION

)

If we choose the value = 1 2πn max i x i 2 , then we get

EQUATION

where the last inequality follows from the fact that 1 ≤ k, n. Therefore, the proof is complete.

8.2. PROOF OF COROLLARY 2:

First, we prove the following lemma.

Lemma 2. Given function f : R k → R and matrix W ∈ R k×k , we define g(x) = f (Wx). Then,

• B(g) ≤ W 2 B(f ) with W 2 denoting the spectral norm of W,

• g 1 = f 1.

Proof. From the properties of the Fourier transform we know

g(ξ) = 1 | det(W)| f W -T ξ . (24) Therefore, g(W T ξ ) = 1 | det(W)| f ξ and if ξ 2 ≤ B(f ), then W T ξ 2 ≤ W 2B(f )

gives an upperbound on B(g). Also,

EQUATION

It can be seen that this result remains valid even if W is not an invertible matrix, which will complete the proof for Corollary 2. However, we continue proving Corollary 2 without using this fact.

As shown in the above lemma, Fourier 1-norm and bandwidth are invariant to an orthonormal transformation W. Given fi(x) = aiφ(w T i x), we define gi(x) = fi(Aix) where Ai is an orthonormal matrix with wi as an eigenvector. Note that fi 1 = gi 1 and B(fi) = B(gi). However, gi(x) is a function of only one of the coordinates, which we can assume, without loss of generality, to be the first coordinate. Hence, gi(x) = aiφ( wi 2x1) for the first coordinate x1, implying gi(ξ) = a i w i 2 φ( ξ 1 w i 2 ).δ2(ξ2) . . . δ k (ξ k ) where δj is the Dirac delta function across the jth dimension. Hence, we can use the above lemma in the 1-dimensional case to show gi 1 = |ai| φ 1 and B(gi) = wi 2B(φ). As a result,

EQUATION

Hence, for f

EQUATION

)

The corollary is then a direct application of Theorem 2.

8.3. PROOF OF THEOREM 3:

Given a ReLU-type activation function φα(z) = max{z, αz}, φα w T x = w q φα ( w w q ) T x .

Since w w q q = 1, if x p ≤ C, then ( w w q ) T x ≤ C and hence the input to φα in the R.H.S. of ( 28) is always between -C and C.

Suppose that function ψα satisfies ψα(z) = φα(z) for z ∈ [-C, C]. Then, based on the above discussion, we can bound the Rademacher complexity of F φα by finding a bound on the Rademacher complexity of

F ψα = f v,U (x) = v T ψα(Ux) : v 1 ≤ V, ∀i : ui q = 1 .

To find a good candidate for ψα, we use a symmetrization trick to define

EQUATION

) Note that ψα(z) = (1 -α)C h( z-C C ) + 2αC h( z-C 2C ) -αC where h(z) = max{0, 1 -|z|}.

It can be seen that h(ξ) = sin(πξ) πξ 2 which is real and positive everywhere. Therefore, h 1 = h(0) = 1 which means that

ψα 1 ≤ C(1 + 2α) ≤ 3C. Since | h(ξ)| ≤ 1

ξ 2 , we have ψα(ξ) ≤ 1 ξ 2 . For B > 0, we let the B-filtered ψα,B be a function with the following Fourier transform:

EQUATION

)

8.5 PROOF OF THEOREM 4

Since the isolatedness assumption holds for all j's, by Lemma 1,

EQUATION

If w * t 2 > B(Y ) + B(P X ) holds for some t , (37) implies

EQUATION

Hence, a * t will be 0, implying there will be no component in f a * ,W * ,b * with w * t 2 > B(Y ) + B(P X ). This discussion proves the first part of Theorem, i.e. B(f a * ,W * ,b * ) ≤ B(Y ) + B(P X ).

To show the second part, note that

EQUATION

Here, (a) comes from Lemma 1. Also, since min w * t -w * r 2, w * t + w * r 2 > 2 B(P X ) is assumed for any t = r, for any ξ at most one element in P X (w * t -ξ) d t=1 can be nonzero. Because if both P X (w * t -ξ) and P X (w * r -ξ) are nonzero for r = t, then w * t -ξ ≤ B(P X ) and also w * r -ξ ≤ B(P X ) which results in w * t -w * r ≤ 2B(P X ) which is a contradiction. Hence, Then, the Fourier transform PX has a Gaussian shape with mean 0 and standard deviation 1/σ. Hence, if for any i, j we have min w * i -w * j 2, w * i + w * j 2 > 2C/σ for some constant C, the approximation error term which should be added to the upperbound in Equation ( 39) is 2 Y 1d exp(-C 2 /2). Also, given any > 0 the Fourier 1 norm outside the bandwidth O( 

8.6. APPROXIMATE VERSION OF THEOREM 4:

Here we show an approximate version of Theorem 4 which applies to approximate population local minima. Proof. Since the isolated components condition holds, we can apply Lemma 1's proof to show under the above assumptions ∀ j : |a * j | ≤ 2 Ŷ PX (w * j ) + . Then, a simple modification of Theorem 4's proof according to the above inequality proves the above theorem.

8.7. PROOF OF THEOREM 4 WITHOUT THE ISOLATED COMPONENTS ASSUMPTION:

What happens if a component wi is not isolated from the other components which has been assumed in Theorem 4? As a simplifying assumption, we assume that b = 0 and P X is real. We can write Letting the gradient element in (41) be zero for all ai's at a local minimum (a * , W * ) of the population risk, the following approximation holds in general case:

EQUATION

EQUATION

Here, the matrix P X (wi -wj) 1≤i,j≤d is positive-definite and hence invertible, because P X is the Fourier transform of P X and due to Bochner's theorem a positive-definite kernel function. Therefore, the system of linear equations P X (w * i -w * j ) a * j -ξ∈Sw j Im{ Y (ξ)} dξ ≈ 0 would imply (42). This discussion indicates that the result of Theorem 4 would remain valid even if the isolated components condition does not hold.

:

Since a Gaussian function's Fourier transform can be arbitrarily well approximated by bandlimited functions in the 1-norm sense, the results shown in this work are applicable to Gaussian activation.

Figures and Tables:

Figure 1: (a) A 2-layer neural network with activation function φ, (b) Training and test accuracy on CIFAR10 with true and random labels on a 2-layer neural network with 512 ReLU hidden units, regularized with an additive penalty: (b1) no penalty, (b2) 2 -norm, (b3) χ 2 -group path norm, (b4)1 -path norm. The χ 2 -group path norm and 1 -path norm were successful to close the generalization gap for both true and random labels.

Consider the minimization problem of the population risk (11). If a local minimum (a * , W * , b * ) satisfies the isolated components condition, i.e. for any two different i, j we have min w

Figure 2: Training an test performance on cat and airplane CIFAR10 images with true and random labels. Sine activation and mean-squared-error loss were used. a. b. c. d.

Figure 3: Training and test performance on cat and airplane CIFAR10 images with true and random labels. ReLU activation and cross-entropy loss were used.

). (b) holds as exp(ibz) = cos(bz) + i sin(bz) is b-Lipschitz as a function of z ∈ R for any real number b > 0. (c) holds because according to our definitions S j ⊆ Sj and Sj = {ξ : ξξ j 2 ≤ }.

X (w * t -ξ) ≤ max ξ P X (ξ ) ≤ P X (x) dx = 1,(40)which proves (b) and completes the proof.8.5.1 APPLYING THEOREM 4 TO MULTIVARIATE GAUSSIAN XAssume X ∼ N (µ, σ 2 I k×k ) has a multivariate Gaussian distribution with mean µ and standard deviation σ.

k log(1/ )/σ) is at most . Therefore, Theorem 4 implies• B(f a * ,W * ,b * ) ≤ B(Y ) + O √ k/σ , • f a * ,W * ,b * 1 ≤ 2(1 + d exp(-C 2 /2)) Y 1.

Consider minimizing the population risk (11). Consider an approximate local minimum (a * , W * , b * ) where |∇a j E f a * ,W * ,b * (X), Y (X) | ≤ for all j's. If for any two different i, j we have min w * i -w * j 2, w * i + w * j 2 > 2 B(P X ), then the Fourier 1-norm of f a * ,W * ,b * outside the bandwidth B(Y ) + B(P X ) is bounded by d and f a * ,W * ,b * 1 ≤ 2 Y 1 + d .

x), Y (x) = d j=1 aj P X (wi -wj) -Im Y P X (wi) Im{ Y (ξ)} dξ P X (wi -wj)(41)Here Sw j 's, which are centered around wj's, are disjoint sets covering the bandwidth region for Y , i.e. {ξ : ξ 2 ≤ B(Y )} ⊆ j Sw j . Note that in (41) we have approximated the convolution integral asY P X (wi) = ξ: ξ 2 ≤B(Y ) P X (wi -ξ) Y (ξ

Peer review (iclr2018):
 This work proposes to study the generalization of learning neural networks via the Fourier-based method. It first gives a Fourier-based generalization bound, showing that Rademacher complexity of functions with small bandwidth and Fourier l_1 norm will be small. This leads to generalization for 2-layer networks with appropriate bounded size. For 2-layer networks with sine activation functions, assuming that the data distribution has nice spectral property (ie bounded bandwidth), it shows that the local minimum of the population risk (if with isolated component condition) will have small size, and also shows that the gradient of the empirical risk is close to that of the population risk. Empirical results show that the size of the networks learned on random labels are larger than those learned on true labels, and shows that a regularizer implied by their Fourier-based generalization bound can effectively reduce the generalization gap on random labels. The idea of applying the Fourier-based method to generalization is interesting. However, the theoretical results are not very satisfactory. -- How do the bounds here compared to those obtained by directly applying Rademacher complexity to the neural network functions? -- How to interpret the isolated components condition in Theorem 4? Basically, it means that B(P_X) should be a small constant. What type of distributions of X will be a good example? -- It is not easy to put together the conclusions in Section 6.1 and 6.2. Suppose SGD leads to a local minimum of the empirical loss. One can claim that this is an approximate local minimum (ie, small gradient) by Corollary 3. But to apply Theorem 4, one will need a version of Theorem 4 for approximate local minima. Also, one needs to argue that the local minimum obtained by SGD will satisfy the isolated component condition. The argument in Section 8.6 is not convincing, ie, there is potentially a large approximation error in (41) and one cannot claim that Lemma 1 and Theorem 4 are still valid without the isolated component condition.