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

Abstract

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

arXiv comment30 pages, 10 figures

References in corpus (10)

• Explaining and Harnessing Adversarial Examples
• A Convergence Theory for Deep Learning via Over-Parameterization
• Risk bounds for statistical learning
• On Lazy Training in Differentiable Programming
• Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
• Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals
• Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent
• Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins