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.
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.