# Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Sep 2019.

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

- [Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks](https://mlsanity.com/paper/2111.13171/) (2021)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [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)
- [Generalization bounds via distillation](https://mlsanity.com/paper/2104.05641/) (2021)
- [Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms](https://mlsanity.com/paper/2106.04881/) (2021)
- [Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms](https://mlsanity.com/paper/2203.02474/) (2022)
- [Scaling Up Exact Neural Network Compression by ReLU Stability](https://mlsanity.com/paper/2102.07804/) (2021)
- [Generalization Bounds with Data-dependent Fractal Dimensions](https://mlsanity.com/paper/2302.02766/) (2023)
- [Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning](https://mlsanity.com/paper/2206.02604/) (2022)
- [Deep neural networks with dependent weights: Gaussian Process mixture limit, heavy tails, sparsity and compressibility](https://mlsanity.com/paper/2205.08187/) (2022)
- [On Measuring Excess Capacity in Neural Networks](https://mlsanity.com/paper/2202.08070/) (2022)
- [Koopman-based generalization bound: New aspect for full-rank weights](https://mlsanity.com/paper/2302.05825/) (2023)
- [Ghosts in Neural Networks: Existence, Structure and Role of Infinite-Dimensional Null Space](https://mlsanity.com/paper/2106.04770/) (2021)
- [Deep Learning with Kernels through RKHM and the Perron-Frobenius Operator](https://mlsanity.com/paper/2305.13588/) (2023)
- [How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning](https://mlsanity.com/paper/2407.05664/) (2024)
- [On generalization bounds for deep networks based on loss surface implicit regularization](https://mlsanity.com/paper/2201.04545/) (2022)
- [Implicit Compressibility of Overparametrized Neural Networks Trained with Heavy-Tailed SGD](https://mlsanity.com/paper/2306.08125/) (2023)
- [Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural Networks](https://mlsanity.com/paper/2303.00196/) (2023)
- [Generalization Guarantees via Algorithm-dependent Rademacher Complexity](https://mlsanity.com/paper/2307.02501/) (2023)
- [Slicing Mutual Information Generalization Bounds for Neural Networks](https://mlsanity.com/paper/2406.04047/) (2024)
- [Large Learning Rates Simultaneously Achieve Robustness to Spurious Correlations and Compressibility](https://mlsanity.com/paper/2507.17748/) (2025)
- [Bound to Disagree: Generalization Bounds via Certifiable Surrogates](https://mlsanity.com/paper/2602.23128/) (2026)
- [Why High-rank Neural Networks Generalize?: An Algebraic Framework with RKHSs](https://mlsanity.com/paper/2509.21895/) (2025)
- [Geometric Analysis of Neural Regression Collapse via Intrinsic Dimension](https://mlsanity.com/paper/2510.01105/) (2025)
- [Operator-Based Generalization Bound for Deep Learning: Insights on Multi-Task Learning](https://mlsanity.com/paper/2512.19184/) (2025)
- [Heating up decision boundaries: isocapacitory saturation, adversarial scenarios and generalization bounds](https://mlsanity.com/paper/2101.06061/) (2021)
- [Approximability and Generalisation](https://mlsanity.com/paper/2203.07989/) (2022)
- [Proximity to Losslessly Compressible Parameters](https://mlsanity.com/paper/2306.02834/) (2023)
- [Distilling the Unknown to Unveil Certainty](https://mlsanity.com/paper/2311.07975/) (2023)

## Abstract (arXiv)

One of the biggest issues in deep learning theory is the generalization ability of networks with huge model size. The classical learning theory suggests that overparameterized models cause overfitting. However, practically used large deep models avoid overfitting, which is not well explained by the classical approaches. To resolve this issue, several attempts have been made. Among them, the compression based bound is one of the promising approaches. However, the compression based bound can be applied only to a compressed network, and it is not applicable to the non-compressed original network. In this paper, we give a unified frame-work that can convert compression based bounds to those for non-compressed original networks. The bound gives even better rate than the one for the compressed network by improving the bias term. By establishing the unified frame-work, we can obtain a data dependent generalization error bound which gives a tighter evaluation than the data independent ones.