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

2021/01/04 by Spencer Frei, Yuan Cao, Frei, Spencer +3 · 1 citation
Computer Science · #Advanced Neural Network Applications #Adversarial Robustness in Machine Learning #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Data Classification #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2101.01152

openalex publication_date 2021/01/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• On the Role of Label Noise in the Feature Learning Process

Related

• SGD Learns Over-parameterized Networks that Provably Generalize on\n Linearly Separable Data
• Learning Overparameterized Neural Networks via Stochastic Gradient\n Descent on Structured Data
• Random Feature Amplification: Feature Learning and Generalization in Neural Networks
• Neural Networks Efficiently Learn Low-Dimensional Representations with SGD
• On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications