Benign Overfitting in Deep Neural Networks under Lazy Training

Zhenyu Zhu, Fanghui Liu, Grigorios G Chrysos, Francesco Locatello, Volkan Cevher

TL;DR

This paper provides a theoretical foundation for benign overfitting in deep ReLU neural networks (DNNs) operating in the "lazy training" regime. The authors prove that these over-parameterized models can achieve Bayes-optimal test error even when they perfectly fit noisy training data, and they establish a critical link between a model's generalization ability and its Lipschitz smoothness.

What Problem Does This Paper Address?

In classical statistics, overfitting is a cardinal sin: fitting training data too closely—especially noisy data—usually leads to poor generalization on new samples. However, modern deep learning often defies this logic. Large models frequently achieve near-zero training error (effectively "memorizing" noise) yet still perform exceptionally well on test sets. This phenomenon is known as benign overfitting.

While previous research successfully explained benign overfitting in linear models and shallow (two- or three-layer) neural networks, extending these proofs to deep neural networks has remained a significant challenge. This paper tackles the open question: Under what conditions does benign overfitting occur in deep ReLU networks, and what role does the network's depth and smoothness play?

Methods

The authors analyze deep, fully connected neural networks with ReLU activations trained via Stochastic Gradient Descent (SGD). They focus on the lazy training regime (often analyzed through the lens of the Neural Tangent Kernel or NTK), where the network is so wide that its weights stay close to their initial values, making the model behave almost like a linear predictor in a high-dimensional feature space.

Key technical components include:

  • Binary Classification Analysis: Proving that for well-separated data with flipped labels (noise), DNNs can still reach the Bayes-optimal error rate.
  • Lipschitz Unification: Connecting the Lipschitz constant (a measure of how much a function's output changes relative to its input) to generalization bounds.
  • NTK Eigenvalue Bounds: Deriving new lower bounds for the minimum eigenvalue of the NTK matrix in high-dimensional settings, which is crucial for understanding how quickly the model converges.

Datasets

While the paper is primarily theoretical, the authors use the MNIST dataset to empirically validate a core assumption: that the NTK kernel naturally assigns higher similarity to data points within the same class than to those in different classes.

Figure 1. Averaged kernel values among 10 classes in MNIST, where a larger kernel value indicates a higher similarity between two data pairs.

Key Insights and Ideas

  • Smoothness is Key: The most intuitive "aha" moment is the rigorous connection between the Lipschitz constant and generalization. The authors show that if a DNN interpolates the data using a "smoother" function (lower Lipschitz constant), it achieves a faster convergence rate for generalization.
  • The Noise Floor: For regression tasks, the generalization error doesn't vanish entirely; instead, it converges to a constant order that depends solely on the label noise and the initialization noise. This theoretically confirms that the model "ignores" the specific noise of individual training points in favor of the underlying signal.
  • Phase Transitions: The behavior of the model changes significantly depending on the ratio of training samples ($n$) to input dimensions ($d$). The authors identify a "phase transition" in the minimum eigenvalue of the NTK, which affects how the model perceives the complexity of the task as more data is added.
Table 1. The trend of the bound with respect to n under different range of n values and a fixed d.

Key Results

  • Bayes-Optimality: Theorem 1 demonstrates that in the lazy regime, the test error rate is bounded by the noise rate $\eta$ plus a generalization term that vanishes as the number of samples increases.
  • Dimension-Free Bounds: The analysis provides generalization guarantees that can be "dimension-free," meaning they hold even when the input dimension $d$ is very large or grows with the number of samples $n$.
  • Faster Convergence: Compared to previous results on shallow networks, this work shows that deep ReLU networks can achieve a faster convergence rate on generalization, specifically when the network's Lipschitz constant is well-behaved.

Limitations and Future Work

The primary limitation is the reliance on the lazy training regime. In practice, many high-performing deep learning models operate in the "active" or "feature learning" regime, where weights move significantly and the model's internal representations change. The authors acknowledge that their linear approximation of the network dynamics doesn't hold in the active regime, leaving that as a challenging frontier for future research.

Additionally, the current proofs assume the data distribution is "well-separated" (e.g., log-concave). Extending these results to more complex, non-log-concave distributions would bring the theory closer to the messy reality of real-world data.

Summary updated

Abstract

This paper focuses on over-parameterized deep neural networks (DNNs) with ReLU activation functions and proves that when the data distribution is well-separated, DNNs can achieve Bayes-optimal test error for classification while obtaining (nearly) zero-training error under the lazy training regime. For this purpose, we unify three interrelated concepts of overparameterization, benign overfitting, and the Lipschitz constant of DNNs. Our results indicate that interpolating with smoother functions leads to better generalization. Furthermore, we investigate the special case where interpolating smooth ground-truth functions is performed by DNNs under the Neural Tangent Kernel (NTK) regime for generalization. Our result demonstrates that the generalization error converges to a constant order that only depends on label noise and initialization noise, which theoretically verifies benign overfitting. Our analysis provides a tight lower bound on the normalized margin under non-smooth activation functions, as well as the minimum eigenvalue of NTK under high-dimensional settings, which has its own interest in learning theory.
BibTeX
@inproceedings{zhu2023benign,
  author = {Zhenyu Zhu and Fanghui Liu and Grigorios G Chrysos and Francesco Locatello and Volkan Cevher},
  title = {{Benign Overfitting in Deep Neural Networks under Lazy Training}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=LvT0l1CD81},
}
Figure