Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness

Pengzhan Jin, Lu Lu, Yifa Tang, George E. KarniadakisNeural Networks 2019 · DOI · OpenReview

TL;DR

This paper tackles the long-standing mystery of why deep neural networks generalize so well, even when they have more parameters than data. The authors propose a new theoretical framework that quantifies generalization error by considering both the "difficulty" of the data distribution (measured by "cover complexity") and the "smoothness" of the trained neural network. Their findings reveal a surprising linear relationship between data complexity and error, and offer practical insights for training.

What Problem Does This Paper Address?

Deep learning has achieved remarkable success across various domains, yet a solid theoretical understanding of why it works, particularly regarding generalization, remains elusive. While approximation and optimization errors in neural networks are relatively well-understood, generalization error—the gap between performance on training data and unseen data—is a major puzzle. Existing theories often fail to explain the observed phenomenon where highly overparameterized networks can memorize training data yet still generalize effectively. This paper aims to bridge this gap by developing a more practical theoretical framework for generalization error in classification tasks, focusing on the interplay between data characteristics and model properties.

Methods

The core of this work lies in introducing two novel concepts:

  • Cover Complexity (CC): This metric quantifies the inherent difficulty of a dataset for classification. It's derived from concepts like "total cover," "self cover," and "mutual cover," which analyze how well data points of the same or different classes are clustered and spread out within the data distribution. A higher CC implies a more challenging dataset to learn.
  • Neural Network Smoothness: This is measured by the inverse of the modulus of continuity of the trained neural network. Intuitively, a smoother network is less sensitive to small changes in its input, which is generally desirable for generalization. The authors propose estimating this by looking at the spectral norm of the weight matrices.

Using these measures, the authors derive a quantitative bound for the expected generalization error. They also introduce a stronger notion of accuracy called "c-accuracy" to better capture performance.

Datasets

The authors validate their theoretical findings using several standard image classification datasets:

  • MNIST
  • CIFAR-10
  • CIFAR-100
  • COIL-20
  • COIL-100
  • SVHN

They also created variants of these datasets, such as grayscale images or images processed through a convolutional layer, to explore different data distributions and complexities. A particularly challenging scenario tested was using randomly assigned labels to MNIST images, which resulted in significantly higher cover complexity.

Key Insights and Ideas

  • Data Distribution Matters (A Lot): The paper strongly emphasizes that the inherent difficulty of the data distribution, quantified by Cover Complexity, is a primary driver of generalization error.
  • Smoothness is Key to Generalization: Neural network smoothness, measured by the inverse modulus of continuity, is shown to be directly related to accuracy. This suggests that networks that are "too wiggly" will generalize poorly.
  • A New "Early Stopping" Strategy: The observed consistency between test loss and neural network smoothness during training suggests that monitoring smoothness could provide a more principled way to determine when to stop training, preventing overfitting.
  • Network Size vs. Smoothness: While increasing network depth and width generally leads to smoother networks, the effect of depth is more pronounced. Crucially, smoothness appears to be insensitive to the size of the training dataset, a finding that is particularly relevant for deep learning.
  • Linear Relationship: A surprising and significant finding is the linear relationship between the normalized error (error scaled by the square root of the number of classes) and the Cover Complexity of the data.

Key Results

  • The paper derives a quantitative bound for generalization error that depends on both Cover Complexity and neural network smoothness.
  • Empirical results across multiple image datasets demonstrate a strong linear correlation between the normalized error and the Cover Complexity of the data. For instance, Figure 3 shows this relationship, with coefficients of determination (R²) as high as 0.99 for certain category numbers.
  • The study shows that neural network smoothness decreases as network depth and width increase, with depth having a more significant impact.
  • Crucially, the normalized smoothness (df/dr) was found to be insensitive to the training dataset size, suggesting that for deep networks, the inherent complexity of the data and the model's learned properties are more dominant factors than sheer data volume beyond a certain point.
  • The authors observed a clear consistency between the decrease in test loss and the increase in neural network smoothness during training, suggesting a potential for early stopping based on smoothness.

Limitations and Future Work

  • Assumption of Single Labels: Some theoretical results, particularly in the proofs, rely on the assumption that data points have a single correct label. While the authors acknowledge this and discuss its relaxation, it's a simplification.
  • Maximum Cross-Entropy Loss Sensitivity: Theorem 3.2's reliance on the maximum cross-entropy loss (Lmax) makes it sensitive to outliers. The authors note that this assumption might be relaxed in practice, and they explore using average loss (Lf) in high-dimensional settings.
  • Exploration of Depth Dependence: While the paper notes that the theoretical bound for smoothness can depend exponentially on network depth, they suggest that in practice, it might scale polynomially. Further exploration of this dependence is left for future work.
  • Conjectures on Learnability: The paper proposes two conjectures to fully explain the observed linear relationship between error and Cover Complexity, but these remain unproven. Future work could focus on proving these conjectures.

Summary updated

Abstract

The accuracy of deep learning, i.e., deep neural networks, can be characterized by dividing the total error into three main types: approximation error, optimization error, and generalization error. Whereas there are some satisfactory answers to the problems of approximation and optimization, much less is known about the theory of generalization. Most existing theoretical works for generalization fail to explain the performance of neural networks in practice. To derive a meaningful bound, we study the generalization error of neural networks for classification problems in terms of data distribution and neural network smoothness. We introduce the cover complexity (CC) to measure the difficulty of learning a data set and the inverse of the modulus of continuity to quantify neural network smoothness. A quantitative bound for expected accuracy/error is derived by considering both the CC and neural network smoothness. Although most of the analysis is general and not specific to neural networks, we validate our theoretical assumptions and results numerically for neural networks by several data sets of images. The numerical results confirm that the expected error of trained networks scaled with the square root of the number of classes has a linear relationship with respect to the CC. We also observe a clear consistency between test loss and neural network smoothness during the training process. In addition, we demonstrate empirically that the neural network smoothness decreases when the network size increases whereas the smoothness is insensitive to training dataset size.
BibTeX
@inproceedings{jin2019quantifying,
  author = {Pengzhan Jin and Lu Lu and Yifa Tang and George E. Karniadakis},
  title = {{Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness}},
  booktitle = {Neural Networks},
  year = {2019},
  doi = {10.1016/j.neunet.2020.06.024},
}
Figure