mlsanityData to 7 Oct 2026

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

arXiv 1703.11008 ↗First posted 31 Mar 2017cs.LGcited by 527

Not on the map. Why?

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.

Key facts. Cited by 527 papers in the map (data through 7 Oct 2026). First posted on arXiv 31 Mar 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2018: 1; 2019: 0; 2020: 1; 2021: 84; 2022: 105; 2023: 107; 2024: 82; 2025: 78; 2026: 69.

527 papers.

Sort:

By area:

  1. 2018Scalable agent alignment via reward modeling: a research directioncited by 438
  2. 2021SWAD: Domain Generalization by Seeking Flat Minimacited by 431
  3. 2021When Vision Transformers Outperform ResNets without Pre-training or Strong Data Augmentationscited by 259
  4. 2021User-friendly introduction to PAC-Bayes boundscited by 234
  5. 2022Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stabilitycited by 151
  6. 2022Leveraging Unlabeled Data to Predict Out-of-Distribution Performancecited by 141
  7. 2021Efficient Sharpness-aware Minimization for Improved Training of Neural Networkscited by 137
  8. 2022Towards Efficient and Scalable Sharpness-Aware Minimizationcited by 129
  9. 2021Overcoming Catastrophic Forgetting in Incremental Few-Shot Learning by Finding Flat Minimacited by 118
  10. 2021Assessing Generalization of SGD via Disagreementcited by 116
  11. 2021Scalable Marginal Likelihood Estimation for Model Selection in Deep Learningcited by 105
  12. 2023Sharpness-Aware Gradient Matching for Domain Generalizationcited by 102
38 more
  1. 2022Improving Generalization in Federated Learning by Seeking Flat Minimacited by 98
  2. 2021The Bayesian Learning Rulecited by 95
  3. 2022Sharpness-Aware Training for Freecited by 95
  4. 2022Agreement-on-the-Line: Predicting the Performance of Neural Networks under Distribution Shiftcited by 94
  5. 2024Revisiting Catastrophic Forgetting in Large Language Model Tuningcited by 93
  6. 2022More Than a Toy: Random Matrix Models Predict How Real-World Neural Representations Generalizecited by 87
  7. 2022A Closer Look at Smoothness in Domain Adversarial Trainingcited by 85
  8. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  9. 2021GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophilycited by 84
  10. 2022Fisher SAM: Information Geometry and Sharpness Aware Minimisationcited by 84
  11. 2022Same Pre-training Loss, Better Downstream: Implicit Bias Matters for Language Modelscited by 84
  12. 2022When Do Flat Minima Optimizers Work?cited by 78
  13. 2022PAC-Bayes Compression Bounds So Tight That They Can Explain Generalizationcited by 75
  14. 2022Agree to Disagree: Diversity through Disagreement for Better Transferabilitycited by 69
  15. 2022Boosting the Transferability of Adversarial Attacks with Reverse Adversarial Perturbationcited by 67
  16. 2022How Does Sharpness-Aware Minimization Minimize Sharpness?cited by 64
  17. 2023The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learningcited by 63
  18. 2021A Theory of PAC Learnability of Partial Concept Classescited by 59
  19. 2022Sharp-MAML: Sharpness-Aware Model-Agnostic Meta Learningcited by 57
  20. 2022Bayesian Model Selection, the Marginal Likelihood, and Generalizationcited by 56
  21. 2025Deep Learning is Not So Mysterious or Differentcited by 55
  22. 2021A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learningcited by 54
  23. 2023Non-Vacuous Generalization Bounds for Large Language Modelscited by 53
  24. 2022The Dynamics of Sharpness-Aware Minimization: Bouncing Across Ravines and Drifting Towards Wide Minimacited by 51
  25. 2021Domain Adversarial Neural Networks for Domain Generalization: When It Works and How to Improvecited by 46
  26. 2021Improved Regularization and Robustness for Fine-tuning in Neural Networkscited by 45
  27. 2021Heavy Tails in SGD and Compressibility of Overparametrized Neural Networkscited by 44
  28. 2023An Adaptive Policy to Employ Sharpness-Aware Minimizationcited by 43
  29. 2024SAMformer: Unlocking the Potential of Transformers in Time Series Forecasting with Sharpness-Aware Minimization and Channel-Wise Attentioncited by 43
  30. 2021Contraction Theory for Nonlinear Stability Analysis and Learning-based Control: A Tutorial Overviewcited by 42
  31. 2022Enhancing Adversarial Training with Second-Order Statistics of Weightscited by 42
  32. 2021Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolationcited by 41
  33. 2022Anticorrelated Noise Injection for Improved Generalizationcited by 41
  34. 2023Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?cited by 41
  35. 2022SAM as an Optimal Relaxation of Bayescited by 40
  36. 2022Low-Pass Filtering SGD for Recovering Flat Optima in the Deep Learning Optimization Landscapecited by 39
  37. 2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 39
  38. 2023Sharpness Minimization Algorithms Do Not Only Minimize Sharpness To Achieve Better Generalizationcited by 39

50 most cited of 527 All 527 (JSON)