Learning Overparameterized Neural Networks via Stochastic Gradient
  Descent on Structured Data
  Neural networks have many successful applications, while much less
theoretical understanding has been gained. Towards bridging this gap, we study
the problem of learning a two-layer overparameterized ReLU neural network for
multi-class classification via stochastic gradient descent (SGD) from random
initialization. In the overparameterized setting, when the data comes from
mixtures of well-separated distributions, we prove that SGD learns a network
with a small generalization error, albeit the network has enough capacity to
fit arbitrary labels. Furthermore, the analysis provides interesting insights
into several aspects of learning neural networks and can be verified based on
empirical studies on synthetic data and on the MNIST dataset.
