# Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach

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

## Key facts

- Cited by 126 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2018.

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

- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Leveraging Unlabeled Data to Predict Out-of-Distribution Performance](https://mlsanity.com/paper/2201.04234/) (2022)
- [PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization](https://mlsanity.com/paper/2211.13609/) (2022)
- [Subgroup Generalization and Fairness of Graph Neural Networks](https://mlsanity.com/paper/2106.15535/) (2021)
- [The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning](https://mlsanity.com/paper/2304.05366/) (2023)
- [Bayesian Model Selection, the Marginal Likelihood, and Generalization](https://mlsanity.com/paper/2202.11678/) (2022)
- [Deep Learning is Not So Mysterious or Different](https://mlsanity.com/paper/2503.02113/) (2025)
- [Non-Vacuous Generalization Bounds for Large Language Models](https://mlsanity.com/paper/2312.17173/) (2023)
- [Improved Regularization and Robustness for Fine-tuning in Neural Networks](https://mlsanity.com/paper/2111.04578/) (2021)
- [Fortuitous Forgetting in Connectionist Networks](https://mlsanity.com/paper/2202.00155/) (2022)
- [Robust Fine-Tuning of Deep Neural Networks with Hessian-based Generalization Guarantees](https://mlsanity.com/paper/2206.02659/) (2022)
- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes](https://mlsanity.com/paper/2106.09683/) (2021)
- [Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stability](https://mlsanity.com/paper/2102.06589/) (2021)
- [Deep Networks on Toroids: Removing Symmetries Reveals the Structure of Flat Regions in the Landscape Geometry](https://mlsanity.com/paper/2202.03038/) (2022)
- [On the Generalization Mystery in Deep Learning](https://mlsanity.com/paper/2203.10036/) (2022)
- [Interpretability Illusions in the Generalization of Simplified Models](https://mlsanity.com/paper/2312.03656/) (2023)
- [Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models](https://mlsanity.com/paper/2407.18158/) (2024)
- [How Tight Can PAC-Bayes be in the Small Data Regime?](https://mlsanity.com/paper/2106.03542/) (2021)
- [Non-Vacuous Generalisation Bounds for Shallow Neural Networks](https://mlsanity.com/paper/2202.01627/) (2022)
- [Lifelong Reinforcement Learning with Modulating Masks](https://mlsanity.com/paper/2212.11110/) (2022)
- [RATT: Leveraging Unlabeled Data to Guarantee Generalization](https://mlsanity.com/paper/2105.00303/) (2021)
- [Train Flat, Then Compress: Sharpness-Aware Minimization Learns More Compressible Models](https://mlsanity.com/paper/2205.12694/) (2022)
- [Understanding Augmentation-based Self-Supervised Representation Learning via RKHS Approximation and Regression](https://mlsanity.com/paper/2306.00788/) (2023)
- [Scaling Up Exact Neural Network Compression by ReLU Stability](https://mlsanity.com/paper/2102.07804/) (2021)
- [On Margins and Derandomisation in PAC-Bayes](https://mlsanity.com/paper/2107.03955/) (2021)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [Energy-based Automated Model Evaluation](https://mlsanity.com/paper/2401.12689/) (2024)
- [On Rademacher Complexity-based Generalization Bounds for Deep Learning](https://mlsanity.com/paper/2208.04284/) (2022)
- [(Almost) Provable Error Bounds Under Distribution Shift via Disagreement Discrepancy](https://mlsanity.com/paper/2306.00312/) (2023)

## Abstract (arXiv)

Modern neural networks are highly overparameterized, with capacity to substantially overfit to training data. Nevertheless, these networks often generalize well in practice. It has also been observed that trained networks can often be "compressed" to much smaller representations. The purpose of this paper is to connect these two empirical observations. Our main technical result is a generalization bound for compressed networks based on the compressed size. Combined with off-the-shelf compression algorithms, the bound leads to state of the art generalization guarantees; in particular, we provide the first non-vacuous generalization guarantees for realistic architectures applied to the ImageNet classification problem. As additional evidence connecting compression and generalization, we show that compressibility of models that tend to overfit is limited: We establish an absolute limit on expected compressibility as a function of expected generalization error, where the expectations are over the random choice of training examples. The bounds are complemented by empirical results that show an increase in overfitting implies an increase in the number of bits required to describe a trained network.