# How Sparse Can We Prune A Deep Network: A Fundamental Limit Perspective

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 47 references that are in the map.
- First posted on arXiv 9 Jun 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [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)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Pruning Filters for Efficient ConvNets](https://mlsanity.com/paper/1608.08710/) (2016)
- [Linear Mode Connectivity and the Lottery Ticket Hypothesis](https://mlsanity.com/paper/1912.05671/) (2019)
- [To prune, or not to prune: exploring the efficacy of pruning for model compression](https://mlsanity.com/paper/1710.01878/) (2017)
- [Filter Pruning via Geometric Median for Deep Convolutional Neural Networks Acceleration](https://mlsanity.com/paper/1811.00250/) (2018)
- [SkipNet: Learning Dynamic Routing in Convolutional Networks](https://mlsanity.com/paper/1711.09485/) (2017)
- [PyHessian: Neural Networks Through the Lens of the Hessian](https://mlsanity.com/paper/1912.07145/) (2019)
- [Dynamic Network Surgery for Efficient DNNs](https://mlsanity.com/paper/1608.04493/) (2016)
- [Pruning Neural Networks at Initialization: Why are We Missing the Mark?](https://mlsanity.com/paper/2009.08576/) (2020)
- [NetAdapt: Platform-Aware Neural Network Adaptation for Mobile Applications](https://mlsanity.com/paper/1804.03230/) (2018)
- [Designing Energy-Efficient Convolutional Neural Networks using Energy-Aware Pruning](https://mlsanity.com/paper/1611.05128/) (2016)
- [Relative Flatness and Generalization](https://mlsanity.com/paper/2001.00939/) (2020)
- [Sanity-Checking Pruning Methods: Random Tickets can Win the Jackpot](https://mlsanity.com/paper/2009.11094/) (2020)
- [The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networks](https://mlsanity.com/paper/2203.04466/) (2022)
- [Fast as CHITA: Neural Network Pruning with Combinatorial Optimization](https://mlsanity.com/paper/2302.14623/) (2023)
- [Unmasking the Lottery Ticket Hypothesis: What's Encoded in a Winning Ticket's Mask?](https://mlsanity.com/paper/2210.03044/) (2022)
- [Rare Gems: Finding Lottery Tickets at Initialization](https://mlsanity.com/paper/2202.12002/) (2022)
- [How many degrees of freedom do we need to train deep networks: a loss landscape perspective](https://mlsanity.com/paper/2107.05802/) (2021)
- [spred: Solving L1 Penalty with SGD](https://mlsanity.com/paper/2210.01212/) (2022)

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

- [CoLA: Compute-Efficient Pre-Training of LLMs via Low-Rank Activation](https://mlsanity.com/paper/2502.10940/) (2025)
- [Wanda++: Pruning Large Language Models via Regional Gradients](https://mlsanity.com/paper/2503.04992/) (2025)
- [Deep Weight Factorization: Sparse Learning Through the Lens of Artificial Symmetries](https://mlsanity.com/paper/2502.02496/) (2025)
- [LaX: Boosting Low-Rank Training of Foundation Models via Latent Crossing](https://mlsanity.com/paper/2505.21732/) (2025)
- [Cut Less, Fold More: Model Compression through the Lens of Projection Geometry](https://mlsanity.com/paper/2602.18116/) (2026)
- [Differentiable Sparsity via D-Gating: Simple and Versatile Structured Penalization](https://mlsanity.com/paper/2509.23898/) (2025)
- [Routing the Lottery: Adaptive Subnetworks for Heterogeneous Data](https://mlsanity.com/paper/2601.22141/) (2026)
- [Pruning-induced phases in fully-connected neural networks: the eumentia, the dementia, and the amentia](https://mlsanity.com/paper/2603.12316/) (2026)
- [Breaking the Compression Barrier: Cross-Architecture Compression Boundary Learning via Reverse Regrowth](https://mlsanity.com/paper/2608.16010/) (2026)

## Abstract (arXiv)

Network pruning is a commonly used measure to alleviate the storage and computational burden of deep neural networks. However, the fundamental limit of network pruning is still lacking. To close the gap, in this work we'll take a first-principles approach, i.e. we'll directly impose the sparsity constraint on the loss function and leverage the framework of statistical dimension in convex geometry, thus enabling us to characterize the sharp phase transition point, which can be regarded as the fundamental limit of the pruning ratio. Through this limit, we're able to identify two key factors that determine the pruning ratio limit, namely, weight magnitude and network sharpness. Generally speaking, the flatter the loss landscape or the smaller the weight magnitude, the smaller pruning ratio. Moreover, we provide efficient countermeasures to address the challenges in the computation of the pruning limit, which mainly involves the accurate spectrum estimation of a large-scale and non-positive Hessian matrix. Moreover, through the lens of the pruning ratio threshold, we can also provide rigorous interpretations on several heuristics in existing pruning algorithms. Extensive experiments are performed which demonstrate that our theoretical pruning ratio threshold coincides very well with the experiments. All codes are available at: https://github.com/QiaozheZhang/Global-One-shot-Pruning