# A Theoretical Understanding of Neural Network Compression from Sparse Linear Approximation

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 30 references that are in the map.
- First posted on arXiv 11 Jun 2022.

## Builds on (most cited first, 18 of 18)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [You Only Look Once: Unified, Real-Time Object Detection](https://mlsanity.com/paper/1506.02640/) (2015)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Identity Mappings in Deep Residual Networks](https://mlsanity.com/paper/1603.05027/) (2016)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Channel Pruning for Accelerating Very Deep Neural Networks](https://mlsanity.com/paper/1707.06168/) (2017)
- [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021)
- [ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression](https://mlsanity.com/paper/1707.06342/) (2017)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Network Trimming: A Data-Driven Neuron Pruning Approach towards Efficient Deep Architectures](https://mlsanity.com/paper/1607.03250/) (2016)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Logarithmic Pruning is All You Need](https://mlsanity.com/paper/2006.12156/) (2020)
- [Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection](https://mlsanity.com/paper/2003.01794/) (2020)
- [Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds](https://mlsanity.com/paper/1804.05345/) (2018)
- [Data-Independent Neural Pruning via Coresets](https://mlsanity.com/paper/1907.04018/) (2019)
- [Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks](https://mlsanity.com/paper/2110.05667/) (2021)

## Built on by (most cited first, 5 of 5)

- [Pruning Deep Neural Networks from a Sparsity Perspective](https://mlsanity.com/paper/2302.05601/) (2023)
- [Probe Pruning: Accelerating LLMs through Dynamic Pruning via Model-Probing](https://mlsanity.com/paper/2502.15618/) (2025)
- [Provable Identifiability of Two-Layer ReLU Neural Networks via LASSO Regularization](https://mlsanity.com/paper/2305.04267/) (2023)
- [Leveraging KV Similarity for Online Structured Pruning in LLMs](https://mlsanity.com/paper/2512.07090/) (2025)
- [Width-Independent Compressibility of Deep Neural Networks](https://mlsanity.com/paper/2608.21752/) (2026)

## Abstract (arXiv)

The goal of model compression is to reduce the size of a large neural network while retaining a comparable performance. As a result, computation and memory costs in resource-limited applications may be significantly reduced by dropping redundant weights, neurons, or layers. There have been many model compression algorithms proposed that provide impressive empirical success. However, a theoretical understanding of model compression is still limited. One problem is understanding if a network is more compressible than another of the same structure. Another problem is quantifying how much one can prune a network with theoretically guaranteed accuracy degradation. In this work, we propose to use the sparsity-sensitive ℓq-norm (0<q<1) to characterize compressibility and provide a relationship between soft sparsity of the weights in the network and the degree of compression with a controlled accuracy degradation bound. We also develop adaptive algorithms for pruning each neuron in the network informed by our theory. Numerical studies demonstrate the promising performance of the proposed methods compared with standard pruning algorithms.