mlsanityData to 7 Oct 2026

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

arXiv 2101.01152 ↗First posted 4 Jan 2021cs.LG math.OC stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 45 of its 61 references that are in the map. First posted on arXiv 4 Jan 2021.

Builds on

45 of 61 references.

References · 45

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  4. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  5. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  6. 2018On Lazy Training in Differentiable Programmingcited by 671
  7. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  8. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  9. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  10. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  11. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  12. 2020The Pitfalls of Simplicity Bias in Neural Networkscited by 349
33 more
  1. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 308
  2. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 302
  3. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  4. 2019SGD on Neural Networks Learns Functions of Increasing Complexitycited by 203
  5. 2019Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limitcited by 187
  6. 2020Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the Neural Tangent Kernelcited by 185
  7. 2020Directional convergence and alignment in deep learningcited by 172
  8. 2019Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networkscited by 162
  9. 2019Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networkscited by 158
  10. 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 139
  11. 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
  12. 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 120
  13. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
  14. 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
  15. 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
  16. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
  17. 2020Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracycited by 70
  18. 2019Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networkscited by 60
  19. 2020The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networkscited by 58
  20. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 57
  21. 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
  22. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  23. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  24. 2020Agnostic Learning of a Single Neuron with Gradient Descentcited by 46
  25. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  26. 2015Efficient Learning of Linear Separators under Bounded Noisecited by 36
  27. 2019Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginalscited by 32
  28. 2020Non-Convex SGD Learns Halfspaces with Adversarial Label Noisecited by 30
  29. 2020Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTKcited by 18
  30. 2019Algorithm-Dependent Generalization Bounds for Overparameterized Deep Residual Networkscited by 16
  31. 2020Agnostic Learning of Halfspaces with Gradient Descent via Soft Marginscited by 14
  32. 2018Are ResNets Provably Better than Linear Predictors?cited by 12
  33. 2020Noise in Classificationcited by 10

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 5; 2023: 5; 2024: 3; 2025: 1.

17 papers.

Sort:

  1. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 90
  2. 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 82
  3. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  4. 2022Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Datacited by 46
  5. 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 40
  6. 2023Understanding and Improving Feature Learning for Out-of-Distribution Generalizationcited by 35
  7. 2023Benign Overfitting for Two-layer ReLU Convolutional Neural Networkscited by 34
  8. 2022Random Feature Amplification: Feature Learning and Generalization in Neural Networkscited by 33
  9. 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
  10. 2021Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descentcited by 21
  11. 2021Self-training Converts Weak Learners to Strong Learners in Mixture Modelscited by 19
  12. 2024Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimizationcited by 17
5 more
  1. 2023Provable Guarantees for Neural Networks via Gradient Feature Learningcited by 13
  2. 2025On the Role of Label Noise in the Feature Learning Processcited by 4
  3. 2022Agnostic Learnability of Halfspaces via Logistic Losscited by 2
  4. 2024Class-wise Activation Unravelling the Engima of Deep Double Descentcited by 0
  5. 2024Impact of Label Noise on Learning Complex Featurescited by 0