Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
By Gintare Karolina Dziugaite, Daniel M. Roy. 2017
967 citations recorded by the source corpus.
One of the defining properties of deep learning is that models are chosen to have many more parameters than available training data. In light of this capacity for overfitting, it is remarkable that simple algorithms like SGD reliably return solutions with low test error. One roadblock to explaining these phenomena in terms of implicit regularization, structural properties of the solution, and/or easiness of the data is that many learning bounds are quantitatively vacuous when applied to networks learned by SGD in this "deep learning" regime. Logically, in order to explain generalization, we need nonvacuous bounds. We return to an idea by Langford and Caruana (2001), who used PAC-Bayes bounds to compute nonvacuous numerical bounds on generalization error for stochastic two-layer two-hidden-unit neural networks via a sensitivity analysis. By optimizing the PAC-Bayes bound directly, we are able to extend their approach and obtain nonvacuous generalization bounds for deep stochastic neural network classifiers with millions of parameters trained on only tens of thousands of examples. We connect our findings to recent and old work on flat minima and MDL-based explanations of generalization.
Subfields: Artificial Intelligence, Scaling & Learning Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Sergey Levine
- Ruslan Salakhutdinov
- Percy Liang
- Quoc V. Le
- Mohit Bansal
- Jianfeng Gao
- Luke S. Zettlemoyer
In Scaling & Learning Theory
Citations in the corpus
- Deep Learning Scaling is Predictable, Empirically (2017, background): “Recent work by Dziugaite and Roy (2017) tightens bounds for the common real application setting that model size is larger than the number of samples in the data set.”
- Scalable agent alignment via reward modeling: a research direction (2018, background): “…even more ambitious would be the development of theoretically well-founded scalable learning algorithms that come with probably approximately correct (Dziugaite & Roy, 2017) or sample complexity guarantees, capacity statements, well-calibrated uncertainty estimates, etc. (Veness et al., 2017).”
- The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, neutral): “…count provides only a crude approximation of a model’s capacity, more sophisticated metrics such as those based on PAC-Bayes [McAllester, 1999, Dziugaite and Roy, 2017, Neyshabur et al., 2017b], VC dimension [Vapnik and Chervonenkis, 1971], and parameter norms [Bartlett et al., 2017,…”
- Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “With the success of deep networks, there is a renewed interest in understanding capacity of the neural networks under different norm constraints or network architectures [22, 5, 44, 26].”
- Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “[3, 23, 21] proved spectrally-normalized margin-based generalization bounds, [9, 23] derived bounds from a PAC-Bayes approach, and [1, 33, 4] derived bounds from the compression point of view.”
- Wireless Network Intelligence at the Edge (2018, background): “PAC-Rademancher bounds are free from the said limitation, yet become vacuous for modern NN architectures under ReLU activations with an SGD training process [134].”
- Visualizing the Loss Landscape of Neural Nets (2017, background): “Dziugaite and Roy [8] connect sharpness to PAC-Bayes bounds for generalization.”
- Certifying Some Distributional Robustness with Principled Adversarial Training (2017, background): “This problem currently persists for most learning-theoretic guarantees in deep learning, and the recent works of Bartlett et al. [2], Dziugaite and Roy [22], and Neyshabur et al. [49] attempt to mitigate this shortcoming.”
- Overcoming Catastrophic Forgetting in Incremental Few-Shot Learning by Finding Flat Minima (2021, background): “A substantial body of methods [2, 37, 11, 15] have been proposed to optimize neural networks towards flat local minima.”
- Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks (2019, background): “Third, we introduce a computable upper bound to the amount of the retained information, which can be efficiently computed even for DNNs.”
- Where is the Information in a Deep Neural Network? (2019, methodology): “In [8], a non-vacuous generalization bound is computed for DNNs, using a (non-centered and non-isotropic) Gaussian prior and Gaussian posterior distributions.”
- Exploring Generalization in Deep Learning (2017, methodology): “This connection between sharpness and the PAC-Bayes framework was also recently noted by Dziugaite and Roy [8].”
- Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, methodology): “Dziugaite & Roy (2017); Zhou et al. (2019) used the PAC-Bayes approach to compute non-vacuous generalization bounds for MNIST and ImageNet, respectively.”
- A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks (2017, methodology): “Langford and Caruana [6], and more recently Dziugaite and Roy [4] and Neyshabur et al. [12], used PAC-Bayes bounds to analyze generalization behavior in neural networks, evaluating the KL-divergence, “perturbation error” L [ f + ] − L [ f ] , or the entire bound numerically.”
- Stronger generalization bounds for deep nets via a compression approach (2018, background): “Some obvious improvements: (i) Empirically it has been observed that deep net training introduces fairly small changes to parameters as compared to the (random) initial weights (Dziugaite and Roy, 2017).”
- A Study on Overfitting in Deep Reinforcement Learning (2018, neutral): “Similar phenomenons are reported in supervised learning (Zhang et al., 2017), and recent work shows various approaches to explain this (Bartlett et al., 2017; Neyshabur et al., 2017; Advani & Saxe, 2017; Smith & Le, 2017; Dziugaite & Roy, 2017; Liang et al., 2017).”
- Generalization in Deep Learning (2017, methodology): “This observation has been called an “apparent paradox” and led to active discussions by many researchers (Arpit et al., 2017; Zhang et al., 2017b; Krueger et al., 2017; Hoffer et al., 2017; Wu et al., 2017; Neyshabur et al., 2017; Dziugaite and Roy, 2017; Dinh et al., 2017).”