# Stronger generalization bounds for deep nets via a compression approach

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

## Key facts

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

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

- [Scaling Down to Scale Up: A Guide to Parameter-Efficient Fine-Tuning](https://mlsanity.com/paper/2303.15647/) (2023)
- [The Values Encoded in Machine Learning Research](https://mlsanity.com/paper/2106.15590/) (2021)
- [Neural Collapse Under MSE Loss: Proximity to and Dynamics on the Central Path](https://mlsanity.com/paper/2106.02073/) (2021)
- [Task-Specific Skill Localization in Fine-tuned Language Models](https://mlsanity.com/paper/2302.06600/) (2023)
- [Sharpness-Aware Training for Free](https://mlsanity.com/paper/2205.14083/) (2022)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Deep Model Fusion: A Survey](https://mlsanity.com/paper/2309.15698/) (2023)
- [Fisher SAM: Information Geometry and Sharpness Aware Minimisation](https://mlsanity.com/paper/2206.04920/) (2022)
- [PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization](https://mlsanity.com/paper/2211.13609/) (2022)
- [Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks](https://mlsanity.com/paper/2111.13171/) (2021)
- [Finding Skill Neurons in Pre-trained Transformer-based Language Models](https://mlsanity.com/paper/2211.07349/) (2022)
- [What Does Rotation Prediction Tell Us about Classifier Accuracy under Varying Testing Environments?](https://mlsanity.com/paper/2106.05961/) (2021)
- [Error estimates for physics informed neural networks approximating the Navier-Stokes equations](https://mlsanity.com/paper/2203.09346/) (2022)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning](https://mlsanity.com/paper/2304.05366/) (2023)
- [Lost in Pruning: The Effects of Pruning Neural Networks beyond Test Accuracy](https://mlsanity.com/paper/2103.03014/) (2021)
- [What Kinds of Functions do Deep Neural Networks Learn? Insights from Variational Spline Theory](https://mlsanity.com/paper/2105.03361/) (2021)
- [Deep Learning is Not So Mysterious or Different](https://mlsanity.com/paper/2503.02113/) (2025)
- [Exploring Memorization in Adversarial Training](https://mlsanity.com/paper/2106.01606/) (2021)
- [Empirical Design in Reinforcement Learning](https://mlsanity.com/paper/2304.01315/) (2023)
- [Implicit Regularization Towards Rank Minimization in ReLU Networks](https://mlsanity.com/paper/2201.12760/) (2022)
- [Non-Vacuous Generalization Bounds for Large Language Models](https://mlsanity.com/paper/2312.17173/) (2023)
- [Analytic Insights into Structure and Rank of Neural Network Hessian Maps](https://mlsanity.com/paper/2106.16225/) (2021)
- [Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks](https://mlsanity.com/paper/2106.03795/) (2021)
- [The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networks](https://mlsanity.com/paper/2203.04466/) (2022)
- [VideoXum: Cross-modal Visual and Textural Summarization of Videos](https://mlsanity.com/paper/2303.12060/) (2023)
- [Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion](https://mlsanity.com/paper/2302.04451/) (2023)
- [Fortuitous Forgetting in Connectionist Networks](https://mlsanity.com/paper/2202.00155/) (2022)
- [Why neural networks find simple solutions: the many regularizers of geometric complexity](https://mlsanity.com/paper/2209.13083/) (2022)
- [Predicting Grokking Long Before it Happens: A look into the loss landscape of models which grok](https://mlsanity.com/paper/2306.13253/) (2023)

## Abstract (arXiv)

Deep nets generalize well despite having more parameters than the number of training samples. Recent works try to give an explanation using PAC-Bayes and Margin-based analyses, but do not as yet result in sample complexity bounds better than naive parameter counting. The current paper shows generalization bounds that're orders of magnitude better in practice. These rely upon new succinct reparametrizations of the trained net --- a compression that is explicit and efficient. These yield generalization bounds via a simple compression-based framework introduced here. Our results also provide some theoretical justification for widespread empirical success in compressing deep nets. Analysis of correctness of our compression relies upon some newly identified textquotedblleft noise stabilitytextquotedblright properties of trained deep nets, which are also experimentally verified. The study of these properties and resulting generalization bounds are also extended to convolutional nets, which had eluded earlier attempts on proving generalization.