# Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data

arXiv: https://arxiv.org/abs/1703.11008 · HTML: https://mlsanity.com/paper/1703.11008/

## Key facts

- Cited by 533 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Mar 2017.

## Built on by (most cited first, 30 of 533)

- [Scalable agent alignment via reward modeling: a research direction](https://mlsanity.com/paper/1811.07871/) (2018)
- [SWAD: Domain Generalization by Seeking Flat Minima](https://mlsanity.com/paper/2102.08604/) (2021)
- [When Vision Transformers Outperform ResNets without Pre-training or Strong Data Augmentations](https://mlsanity.com/paper/2106.01548/) (2021)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability](https://mlsanity.com/paper/2209.15594/) (2022)
- [Leveraging Unlabeled Data to Predict Out-of-Distribution Performance](https://mlsanity.com/paper/2201.04234/) (2022)
- [Efficient Sharpness-aware Minimization for Improved Training of Neural Networks](https://mlsanity.com/paper/2110.03141/) (2021)
- [Towards Efficient and Scalable Sharpness-Aware Minimization](https://mlsanity.com/paper/2203.02714/) (2022)
- [Overcoming Catastrophic Forgetting in Incremental Few-Shot Learning by Finding Flat Minima](https://mlsanity.com/paper/2111.01549/) (2021)
- [Assessing Generalization of SGD via Disagreement](https://mlsanity.com/paper/2106.13799/) (2021)
- [Scalable Marginal Likelihood Estimation for Model Selection in Deep Learning](https://mlsanity.com/paper/2104.04975/) (2021)
- [Sharpness-Aware Gradient Matching for Domain Generalization](https://mlsanity.com/paper/2303.10353/) (2023)
- [The Bayesian Learning Rule](https://mlsanity.com/paper/2107.04562/) (2021)
- [Revisiting Catastrophic Forgetting in Large Language Model Tuning](https://mlsanity.com/paper/2406.04836/) (2024)
- [Improving Generalization in Federated Learning by Seeking Flat Minima](https://mlsanity.com/paper/2203.11834/) (2022)
- [Sharpness-Aware Training for Free](https://mlsanity.com/paper/2205.14083/) (2022)
- [Agreement-on-the-Line: Predicting the Performance of Neural Networks under Distribution Shift](https://mlsanity.com/paper/2206.13089/) (2022)
- [More Than a Toy: Random Matrix Models Predict How Real-World Neural Representations Generalize](https://mlsanity.com/paper/2203.06176/) (2022)
- [A Closer Look at Smoothness in Domain Adversarial Training](https://mlsanity.com/paper/2206.08213/) (2022)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophily](https://mlsanity.com/paper/2110.15777/) (2021)
- [Fisher SAM: Information Geometry and Sharpness Aware Minimisation](https://mlsanity.com/paper/2206.04920/) (2022)
- [Same Pre-training Loss, Better Downstream: Implicit Bias Matters for Language Models](https://mlsanity.com/paper/2210.14199/) (2022)
- [When Do Flat Minima Optimizers Work?](https://mlsanity.com/paper/2202.00661/) (2022)
- [PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization](https://mlsanity.com/paper/2211.13609/) (2022)
- [Agree to Disagree: Diversity through Disagreement for Better Transferability](https://mlsanity.com/paper/2202.04414/) (2022)
- [Boosting the Transferability of Adversarial Attacks with Reverse Adversarial Perturbation](https://mlsanity.com/paper/2210.05968/) (2022)
- [How Does Sharpness-Aware Minimization Minimize Sharpness?](https://mlsanity.com/paper/2211.05729/) (2022)
- [The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning](https://mlsanity.com/paper/2304.05366/) (2023)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)

## Abstract (arXiv)

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.