# No Free Prune: Information-Theoretic Barriers to Pruning at Initialization

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 53 of its 71 references that are in the map.
- First posted on arXiv 2 Feb 2024.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [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)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Linear Mode Connectivity and the Lottery Ticket Hypothesis](https://mlsanity.com/paper/1912.05671/) (2019)
- [Network In Network](https://mlsanity.com/paper/1312.4400/) (2013)
- [To prune, or not to prune: exploring the efficacy of pruning for model compression](https://mlsanity.com/paper/1710.01878/) (2017)
- [Rethinking the Value of Network Pruning](https://mlsanity.com/paper/1810.05270/) (2018)
- [What is the State of Neural Network Pruning?](https://mlsanity.com/paper/2003.03033/) (2020)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Learning Structured Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1608.03665/) (2016)
- [Pruning neural networks without any data by iteratively conserving synaptic flow](https://mlsanity.com/paper/2006.05467/) (2020)
- [The State of Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1902.09574/) (2019)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [Does Learning Require Memorization? A Short Tale about a Long Tail](https://mlsanity.com/paper/1906.05271/) (2019)
- [AMC: AutoML for Model Compression and Acceleration on Mobile Devices](https://mlsanity.com/paper/1802.03494/) (2018)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [EIE: Efficient Inference Engine on Compressed Deep Neural Network](https://mlsanity.com/paper/1602.01528/) (2016)
- [The Lottery Ticket Hypothesis for Pre-trained BERT Networks](https://mlsanity.com/paper/2007.12223/) (2020)
- [What's Hidden in a Randomly Weighted Neural Network?](https://mlsanity.com/paper/1911.13299/) (2019)
- [Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask](https://mlsanity.com/paper/1905.01067/) (2019)
- [Pruning Neural Networks at Initialization: Why are We Missing the Mark?](https://mlsanity.com/paper/2009.08576/) (2020)
- [Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks](https://mlsanity.com/paper/2006.13198/) (2020)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)

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

- [The Right to be Forgotten in Pruning: Unveil Machine Unlearning on Sparse Models](https://mlsanity.com/paper/2507.18725/) (2025)
- [Sign-In to the Lottery: Reparameterizing Sparse Training From Scratch](https://mlsanity.com/paper/2504.12801/) (2025)
- [Pruning is Optimal for Learning Sparse Features in High-Dimensions](https://mlsanity.com/paper/2406.08658/) (2024)
- [What Scalable Second-Order Information Knows for Pruning at Initialization](https://mlsanity.com/paper/2502.11450/) (2025)
- [TwIST: Rigging the Lottery in Transformers with Independent Subnetwork Training](https://mlsanity.com/paper/2511.03983/) (2025)
- [Theoretical Compression Bounds for Wide Multilayer Perceptrons](https://mlsanity.com/paper/2512.06288/) (2025)
- [Post-Training Neural Network Pruning using Graph Curvature](https://mlsanity.com/paper/2601.16366/) (2026)
- [Rethinking Reservoir Pruning: A Dynamical Perspective for Echo State Networks](https://mlsanity.com/paper/2608.04593/) (2026)

## Abstract (arXiv)

The existence of "lottery tickets" arXiv:1803.03635 at or near initialization raises the tantalizing question of whether large models are necessary in deep learning, or whether sparse networks can be quickly identified and trained without ever training the dense models that contain them. However, efforts to find these sparse subnetworks without training the dense model ("pruning at initialization") have been broadly unsuccessful arXiv:2009.08576. We put forward a theoretical explanation for this, based on the model's effective parameter count, peff, given by the sum of the number of non-zero weights in the final network and the mutual information between the sparsity mask and the data. We show the Law of Robustness of arXiv:2105.12806 extends to sparse networks with the usual parameter count replaced by peff, meaning a sparse neural network which robustly interpolates noisy data requires a heavily data-dependent mask. We posit that pruning during and after training outputs masks with higher mutual information than those produced by pruning at initialization. Thus two networks may have the same sparsities, but differ in effective parameter count based on how they were trained. This suggests that pruning near initialization may be infeasible and explains why lottery tickets exist, but cannot be found fast (i.e. without training the full network). Experiments on neural networks confirm that information gained during training may indeed affect model capacity.