Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
arXiv:1905.11427 · doi:10.1016/j.neunet.2020.06.024
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.
References in corpus (27)
- Understanding deep learning requires rethinking generalization
- Opening the Black Box of Deep Neural Networks via Information
- A Convergence Theory for Deep Learning via Over-Parameterization
- Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks
- Train faster, generalize better: Stability of stochastic gradient descent
- A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
- Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
- Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
- Robust Large Margin Deep Neural Networks
- Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
- Gradient Descent Finds Global Minima of Deep Neural Networks
- Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
- In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning
- Sharp Minima Can Generalize For Deep Nets
- Gradient Descent Converges to Minimizers
- Fisher-Rao Metric, Geometry, and Complexity of Neural Networks
- Data-Dependent Stability of Stochastic Gradient Descent
- Generalization in Deep Networks: The Role of Distance from Initialization
- Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation
- Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
- Theory of Deep Learning III: explaining the non-overfitting puzzle
- Theory II: Landscape of the Empirical Risk in Deep Learning
- Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience
- Theory of Deep Learning IIb: Optimization Properties of SGD
- Stability and Convergence Trade-off of Iterative Optimization Algorithms
- Generalization Error of Invariant Classifiers
- Fast Rates for Empirical Risk Minimization of Strict Saddle Problems