Published as a conference paper at ICLR 2018 SGD LEARNS OVER-PARAMETERIZED NETWORKS THAT PROVABLY GENERALIZE ON LINEARLY SEPARA- BLE DATA
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 and only the first layer is trained, 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.
This paper shows that on linearly separable data, SGD on a overparametrized network (one hidden layer, with leaky ReLU activations) can still lean a classifier that provably generalizes. The assumption on data and structure of network is a bit strong, but this is the first result that achieves a number of desirable properties
``1. Works for overparametrized network
2. Finds global optimal solution for a non-convex network.
3. Has generalization guarantees (and generalization is related to the SGD algorithm).
4. Number of samples need not depend on the number of neurons. 
There have been several papers achieving 1 and 2 (with much weaker assumptions), but they do not have 3 and 4. The proof of the optimization part is very similar to the proof of perceptron algorithm, and really relies on linear separability. The proof of generalization is based on a compression argument, where if an algorithm does not take many nonzero steps, then it must have good generalization. Ideally, one would also want to see a result where overparametrization actually helps (in the main result the whole data can be learned by a linear classifier). This is somewhat achieved when the activation is replaced with standard ReLU, where the paper showed with a small number of hidden units the algorithm is likely to get stuck at a local minima, but with enough hidden units the algorithm is likely to converge (but even in this case, the data is still linearly separable and can be learned just by a perceptron). 
The main concern about the paper is the possibility of generalizing the result. The algorithm part seems to heavily rely on the linear separable assumption. The generalization part relies on not making many non-zero updates, which is not really true in realistic settings (where the data is accessed in multiple passes) [After author response: Yes in the linearly separable case with hinge loss it is quite possible that the number of updates is sublinear. However what I meant here is that with more complicated data and different loss functions it is hard to believe that this can still hold.]. The related work section is also a bit unfair to some of the other generalization results (e.g. Bartlett et al. Neyshabur et al.): those results work on more general network settings, and it's not completely clear that they cannot be related to the algorithm because they rely on certain solution specific quantities (such as spectral/Frobenius norms of the weight matrices) and it could be possible that SGD tends to find a solution with small norm (which can be proved in linear setting and might also be provable for the setting of this paper) [This is addressed in the author response].
Overall, even though the assumptions might be a bit strong, I think this is an interesting result working towards a good direction and should be accepted.