# PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization

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

## Key facts

- Cited by 76 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 77 references that are in the map.
- First posted on arXiv 24 Nov 2022.

## Builds on (most cited first, 30 of 44)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://mlsanity.com/paper/1905.11946/) (2019)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [FiLM: Visual Reasoning with a General Conditioning Layer](https://mlsanity.com/paper/1709.07871/) (2017)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Group Equivariant Convolutional Networks](https://mlsanity.com/paper/1602.07576/) (2016)
- [Tensor field networks: Rotation- and translation-equivariant neural networks for 3D point clouds](https://mlsanity.com/paper/1802.08219/) (2018)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs](https://mlsanity.com/paper/1802.10026/) (2018)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Spherical CNNs](https://mlsanity.com/paper/1801.10130/) (2018)
- [General E(2)-Equivariant Steerable CNNs](https://mlsanity.com/paper/1911.08251/) (2019)
- [Measuring the Intrinsic Dimension of Objective Landscapes](https://mlsanity.com/paper/1804.08838/) (2018)
- [Entropy-SGD: Biasing Gradient Descent Into Wide Valleys](https://mlsanity.com/paper/1611.01838/) (2016)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [What Are Bayesian Neural Network Posteriors Really Like?](https://mlsanity.com/paper/2104.14421/) (2021)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [A Survey of Model Compression and Acceleration for Deep Neural Networks](https://mlsanity.com/paper/1710.09282/) (2017)
- [Identifying and attacking the saddle point problem in high-dimensional non-convex optimization](https://mlsanity.com/paper/1406.2572/) (2014)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [Generalizing Convolutional Neural Networks for Equivariance to Lie Groups on Arbitrary Continuous Data](https://mlsanity.com/paper/2002.12880/) (2020)
- [Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets](https://mlsanity.com/paper/1903.05662/) (2019)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Qualitatively characterizing neural network optimization problems](https://mlsanity.com/paper/1412.6544/) (2014)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Tighter risk certificates for neural networks](https://mlsanity.com/paper/2007.12911/) (2020)
- [Provably Strict Generalisation Benefit for Equivariant Models](https://mlsanity.com/paper/2102.10333/) (2021)

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

- [How Does Information Bottleneck Help Deep Learning?](https://mlsanity.com/paper/2305.18887/) (2023)
- [The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning](https://mlsanity.com/paper/2304.05366/) (2023)
- [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)
- [Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models](https://mlsanity.com/paper/2407.18158/) (2024)
- [Position: Understanding LLMs Requires More Than Statistical Generalization](https://mlsanity.com/paper/2405.01964/) (2024)
- [Understanding Augmentation-based Self-Supervised Representation Learning via RKHS Approximation and Regression](https://mlsanity.com/paper/2306.00788/) (2023)
- [Simplifying Neural Network Training Under Class Imbalance](https://mlsanity.com/paper/2312.02517/) (2023)
- [How Uniform Random Weights Induce Non-uniform Bias: Typical Interpolating Neural Networks Generalize with Narrow Teachers](https://mlsanity.com/paper/2402.06323/) (2024)
- [More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity](https://mlsanity.com/paper/2306.12214/) (2023)
- [Learning via Wasserstein-Based High Probability Generalisation Bounds](https://mlsanity.com/paper/2306.04375/) (2023)
- [Understanding prompt engineering may not require rethinking generalization](https://mlsanity.com/paper/2310.03957/) (2023)
- [Efficient Sketches for Training Data Attribution and Studying the Loss Landscape](https://mlsanity.com/paper/2402.03994/) (2024)
- [Models of Heavy-Tailed Mechanistic Universality](https://mlsanity.com/paper/2506.03470/) (2025)
- [Data-dependent Generalization Bounds via Variable-Size Compressibility](https://mlsanity.com/paper/2303.05369/) (2023)
- [Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!](https://mlsanity.com/paper/2306.05862/) (2023)
- [Multitask methods for predicting molecular properties from heterogeneous data](https://mlsanity.com/paper/2401.17898/) (2024)
- [When Do Neural Networks Learn World Models?](https://mlsanity.com/paper/2502.09297/) (2025)
- [Norm-based Generalization Bounds for Compositionally Sparse Neural Networks](https://mlsanity.com/paper/2301.12033/) (2023)
- [Can DPO Learn Diverse Human Values? A Theoretical Scaling Law](https://mlsanity.com/paper/2408.03459/) (2024)
- [PAC-Bayes Generalization Certificates for Learned Inductive Conformal Prediction](https://mlsanity.com/paper/2312.04658/) (2023)
- [Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers](https://mlsanity.com/paper/2509.22445/) (2025)
- [Comparing Comparators in Generalization Bounds](https://mlsanity.com/paper/2310.10534/) (2023)
- [A PAC-Bayesian Perspective on the Interpolating Information Criterion](https://mlsanity.com/paper/2311.07013/) (2023)
- [From Low Intrinsic Dimensionality to Non-Vacuous Generalization Bounds in Deep Multi-Task Learning](https://mlsanity.com/paper/2501.19067/) (2025)
- [Compute-Optimal LLMs Provably Generalize Better With Scale](https://mlsanity.com/paper/2504.15208/) (2025)
- [Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural Networks](https://mlsanity.com/paper/2303.00196/) (2023)
- [Input margins can predict generalization too](https://mlsanity.com/paper/2308.15466/) (2023)
- [Perspectives on the State and Future of Deep Learning - 2023](https://mlsanity.com/paper/2312.09323/) (2023)
- [Slicing Mutual Information Generalization Bounds for Neural Networks](https://mlsanity.com/paper/2406.04047/) (2024)

## Abstract (arXiv)

While there has been progress in developing non-vacuous generalization bounds for deep neural networks, these bounds tend to be uninformative about why deep learning works. In this paper, we develop a compression approach based on quantizing neural network parameters in a linear subspace, profoundly improving on previous results to provide state-of-the-art generalization bounds on a variety of tasks, including transfer learning. We use these tight bounds to better understand the role of model size, equivariance, and the implicit biases of optimization, for generalization in deep learning. Notably, we find large models can be compressed to a much greater extent than previously known, encapsulating Occam's razor. We also argue for data-independent bounds in explaining generalization.