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

Spencer Frei, Yuan Cao, Quanquan Gu

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.

Introduction

A central paradox in modern deep learning is the success of overparameterized models. These networks often possess far more parameters than training examples, which, according to classical statistical learning theory, should lead to catastrophic overfitting—especially when the training data is corrupted by noise. While empirical evidence suggests that neural networks generalize remarkably well, theoretical explanations have often been restricted to the "Neural Tangent Kernel" (NTK) regime. The NTK regime assumes networks are infinitely wide and that weights remain near their initial values, which does not fully capture the dynamics of practical training.

This research bridges the gap by providing a theoretical guarantee for the generalization of one-hidden-layer neural networks of arbitrary width and arbitrary initialization. Specifically, it addresses how these networks perform in the presence of adversarial label noise, where a portion of the training labels are intentionally flipped to mislead the learner.

Methodology and Technical Framework

The study focuses on a one-hidden-layer network utilizing the leaky ReLU activation function. Unlike the standard ReLU, which outputs zero for negative inputs, the leaky ReLU maintains a small positive slope for negative values. This property is crucial for the proof as it prevents "dead neurons" and ensures that gradients remain informative throughout the training process.

Training via Online SGD

The authors analyze the network's performance using online Stochastic Gradient Descent (SGD) with a standard cross-entropy loss function. The core of their technical contribution is the "Correlation Argument." Rather than attempting to show that weights stay close to their initialization (as in NTK proofs), the authors demonstrate that the weights learned by SGD become increasingly correlated with the optimal linear classifier (the best possible halfspace) for the underlying distribution.

Distributional Assumptions

The theoretical bounds hold for a broad class of "well-behaved" distributions, including:

  • Log-concave isotropic distributions: Such as standard Gaussians.
  • Anti-concentration distributions: Distributions where data points are not excessively clustered in a single region, allowing the optimizer to find a stable boundary.

Key Insights: Implicit Regularization

The most significant finding is that the optimization process itself—SGD—acts as an implicit regularizer. The research demonstrates that the generalization bound is independent of the number of neurons ($m$). This suggests that even as the network becomes "wider" and gains the capacity to memorize noise, the path taken by SGD naturally gravitates toward simpler, linear-like solutions early in the training process.

This "simplicity bias" allows the network to ignore adversarial noise without requiring explicit regularization techniques like weight decay or dropout. The study proves that the network will achieve an error rate competitive with the best linear classifier ($O(\sqrt{OPT_{lin}})$) in polynomial time.

Experimental Validation

While primarily a theoretical work, the authors validated their findings using synthetic 2D experimental setups involving Gaussian mixtures ($D_{b, \gamma_0}$) separated by a margin. They introduced two types of noise to test robustness:

  1. Deterministic (Adversarial) Noise: Labels were flipped in specific boundary regions to maximize confusion.
  2. Random Classification Noise: 10% of all labels were flipped at random.

Results

  • Theoretical Error Bounds: For distributions with anti-concentration, the network achieves a classification error of at most $\tilde{O}(\sqrt{OPT_{lin}})$. For distributions with a "hard margin," this improves to $\tilde{O}(OPT_{lin})$.
  • Decision Boundaries: In 2D simulations, the leaky ReLU network's decision boundary remained nearly linear, matching the best linear classifier. This occurred despite the network having sufficient capacity to create complex, non-linear boundaries to fit the noise.
  • The Role of Depth: Interestingly, while one-layer networks remained biased toward linear solutions, the authors observed that three-hidden-layer networks could learn non-linear boundaries that outperformed linear classifiers, approaching Bayes optimal accuracy while maintaining robustness to noise.

Conclusion and Future Directions

This work provides a rigorous foundation for why overparameterized networks do not necessarily succumb to noise. By proving that arbitrary-width networks trained by SGD can remain competitive with the best linear classifiers, the authors highlight the power of implicit regularization in deep learning.

However, the study also notes limitations. The current proof is restricted to one-hidden-layer networks without bias terms, which are sometimes "too simple" to outperform linear models on complex tasks. Future research will focus on extending these guarantees to deeper architectures and exploring how networks can learn more expressive concept classes while retaining provable robustness to adversarial corruption.

Summary updated

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.
BibTeX
@inproceedings{frei2021provable,
  author = {Spencer Frei and Yuan Cao and Quanquan Gu},
  title = {{Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=YtmHu_bbyuM},
}
Figure