Neural networks exhibit good generalization behavior in the
 over-parameterized regime, where the number of network parameters
 exceeds the number of observations. Nonetheless,
 current generalization bounds for neural networks fail to explain this
 phenomenon. In an attempt to bridge this gap, we study the problem of
 learning a two-layer over-parameterized neural network, when the data is generated by a linearly separable function. In the case where the network has Leaky
 ReLU activations, we provide both optimization and generalization guarantees for over-parameterized networks.
 Specifically, we prove convergence rates of SGD to a global
 minimum and provide generalization guarantees for this global minimum
 that are independent of the network size. 
 Therefore, our result clearly shows that the use of SGD for optimization both finds a global minimum, and avoids overfitting despite the high capacity of the model. This is the first theoretical demonstration that SGD can avoid overfitting, when learning over-specified neural network classifiers. Neural networks have achieved remarkable performance in many machine learning tasks. Although recently there have been numerous theoretical contributions to understand their success, it is still largely unexplained and remains a mystery. In particular, it is not known why in the overparameterized setting, in which there are far more parameters than training points, stochastic gradient descent (SGD) can learn networks that generalize well, as been observed in practice BID15 BID26 .In such over-parameterized settings, the loss function can contain multiple global minima that generalize poorly. Therefore , learning can in principle lead to models with low training error, but high test error. However, as often observed in practice, SGD is in fact able to find models with low training error and good generalization performance. This suggests that the optimization procedure, which depends on the optimization method (SGD) and the training data, introduces some form of inductive bias which directs it towards a low complexity solution. Thus, in order to explain the success of neural networks, it is crucial to characterize this inductive bias and understand what are the guarantees for generalization of over-parameterized neural networks.In this work, we address these problems in a binary classification setting where SGD optimizes a two-layer over-parameterized network with the goal of learning a linearly separable function. We study a relatively simple case of SGD where the weights of the second layer are fixed throughout the training process, and only the weights of the first layer are updated. Clearly, an over-parameterized network is not necessary for classifying linearly separable data, since this is possible with linear classifiers (e.g., with the Perceptron algorithm) which also have good generalization guarantees BID20 . But, the key question which we address here is whether a large network will overfit in such a case or not. As we shall see, it turns out that although the networks we consider are rich enough to considerably overfit the data, this does not happen when SGD is used for optimization. In other words, SGD introduces an inductive bias which allows it to learn over-parameterized networks that can generalize well. Therefore, this setting serves as a good test bed for studying the effect of over-paramaterization. Understanding the performance of over-parameterized neural networks is essential for explaining the success of deep learning models in practice. Despite a plethora of theoretical results for generalization of neural networks, none of them give guarantees for over-parameterized networks. In this work, we give the first provable guarantees for the generalization performance of over-parameterized networks, in a setting where the data is linearly separable and the network has Leaky ReLU activations. We show that SGD compresses its output when learning over-parameterized networks, and thus exhibits good generalization performance.The analysis for networks with Leaky ReLU activations does not hold for networks with ReLU activations, since in this case the loss contains spurious local minima. However, due to the success of over-parameterized networks with ReLU activations in practice, it is likely that similar results hold here as well. It would be very interesting to provide convergence guarantees and generalization bounds for this case. Another direction for future work is to show that similar results hold under different assumptions on the data.
We show that SGD learns two-layer over-parameterized neural networks with Leaky ReLU activations that provably generalize on linearly separable data. The paper studies overparameterised models being able to learn well-generalising solutions by using a 1-hidden layer network with fixed output layer. This paper shows that on linearly seperabel data, SGD on an overparameterized network can still lean a classifier that provably generalizes.