Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise

We consider a one-hidden-layer leaky ReLU network of arbitrary width trained\nby stochastic gradient descent (SGD) following an arbitrary initialization. We\nprove that SGD produces neural networks that have classification accuracy\ncompetitive with that of the best halfspace over the distribution for a broad\nclass of distributions that includes log-concave isotropic and hard margin\ndistributions. Equivalently, such networks can generalize when the data\ndistribution is linearly separable but corrupted with adversarial label noise,\ndespite the capacity to overfit. To the best of our knowledge, this is the\nfirst work to show that overparameterized neural networks trained by SGD can\ngeneralize when the data is corrupted with adversarial label noise.\n