# Why Random Pruning Is All We Need to Start Sparse

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 62 references that are in the map.
- First posted on arXiv 5 Oct 2022.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [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)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Learning Sparse Neural Networks through L0 Regularization](https://mlsanity.com/paper/1712.01312/) (2017)
- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [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)
- [Retiring Adult: New Datasets for Fair Machine Learning](https://mlsanity.com/paper/2108.04884/) (2021)
- [Scalable Training of Artificial Neural Networks with Adaptive Sparse Connectivity inspired by Network Science](https://mlsanity.com/paper/1707.04780/) (2017)
- [Comparing Rewinding and Fine-tuning in Neural Network Pruning](https://mlsanity.com/paper/2003.02389/) (2020)
- [What's Hidden in a Randomly Weighted Neural Network?](https://mlsanity.com/paper/1911.13299/) (2019)
- [Towards Understanding Grokking: An Effective Theory of Representation Learning](https://mlsanity.com/paper/2205.10343/) (2022)
- [Learning to Prune Deep Neural Networks via Layer-wise Optimal Brain Surgeon](https://mlsanity.com/paper/1705.07565/) (2017)
- [Sparse Networks from Scratch: Faster Training without Losing Performance](https://mlsanity.com/paper/1907.04840/) (2019)
- [Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask](https://mlsanity.com/paper/1905.01067/) (2019)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Pruning Neural Networks at Initialization: Why are We Missing the Mark?](https://mlsanity.com/paper/2009.08576/) (2020)
- [Drawing Early-Bird Tickets: Towards More Efficient Training of Deep Networks](https://mlsanity.com/paper/1909.11957/) (2019)
- [Soft Threshold Weight Reparameterization for Learnable Sparsity](https://mlsanity.com/paper/2002.03231/) (2020)
- [Deep Rewiring: Training very sparse deep networks](https://mlsanity.com/paper/1711.05136/) (2017)
- [Winning the Lottery with Continuous Sparsification](https://mlsanity.com/paper/1912.04427/) (2019)
- [The Unreasonable Effectiveness of Random Pruning: Return of the Most Naive Baseline for Sparse Training](https://mlsanity.com/paper/2202.02643/) (2022)
- [Sparse Training via Boosting Pruning Plasticity with Neuroregeneration](https://mlsanity.com/paper/2106.10404/) (2021)

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

- [A Simple and Effective Pruning Approach for Large Language Models](https://mlsanity.com/paper/2306.11695/) (2023)
- [Spectral Graph Pruning Against Over-Squashing and Over-Smoothing](https://mlsanity.com/paper/2404.04612/) (2024)
- [Masks, Signs, And Learning Rate Rewinding](https://mlsanity.com/paper/2402.19262/) (2024)
- [Mask in the Mirror: Implicit Sparsification](https://mlsanity.com/paper/2408.09966/) (2024)
- [The Larger the Merrier? Efficient Large AI Model Inference in Wireless Edge Networks](https://mlsanity.com/paper/2505.09214/) (2025)
- [Short-LVLM: Compressing and Accelerating Large Vision-Language Models by Pruning Redundant Layers](https://mlsanity.com/paper/2507.23362/) (2025)
- [Sign-In to the Lottery: Reparameterizing Sparse Training From Scratch](https://mlsanity.com/paper/2504.12801/) (2025)
- [Understanding MLP-Mixer as a Wide and Sparse MLP](https://mlsanity.com/paper/2306.01470/) (2023)
- [Self-Regulated Neurogenesis for Online Data-Incremental Learning](https://mlsanity.com/paper/2403.14684/) (2024)
- [On the Sparsity of the Strong Lottery Ticket Hypothesis](https://mlsanity.com/paper/2410.14754/) (2024)
- [Understanding Sparse Neural Networks from their Topology via Multipartite Graph Representations](https://mlsanity.com/paper/2305.16886/) (2023)
- [The Strong Lottery Ticket Hypothesis for Multi-Head Attention Mechanisms](https://mlsanity.com/paper/2511.04217/) (2025)
- [Routing Absorption in Sparse Attention: Why Random Gates Are Hard to Beat](https://mlsanity.com/paper/2603.02227/) (2026)
- [Cyclic Sparse Training: Is it Enough?](https://mlsanity.com/paper/2406.02773/) (2024)
- [Sparsifying dimensionality reduction of PDE solution data with Bregman learning](https://mlsanity.com/paper/2406.12672/) (2024)
- [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)
- [Trading-off Accuracy and Communication Cost in Federated Learning](https://mlsanity.com/paper/2503.14246/) (2025)
- [NuWa: Deriving Lightweight Class-Specific Vision Transformers for Edge Devices](https://mlsanity.com/paper/2504.03118/) (2025)
- [Gibbs randomness-compression proposition](https://mlsanity.com/paper/2505.23869/) (2025)
- [Long-Tailed Data Classification by Increasing and Decreasing Neurons During Training](https://mlsanity.com/paper/2507.09940/) (2025)
- [The Quest for Winning Tickets in Low-Rank Adapters](https://mlsanity.com/paper/2512.22495/) (2025)
- [HORST: Composing Optimizer Geometries for Sparse Transformer Training](https://mlsanity.com/paper/2605.21104/) (2026)
- [Compositionality Emerges in a Narrow Depth-Connectivity Regime: Architecture Constraints and Solution Manifolds](https://mlsanity.com/paper/2606.19941/) (2026)
- [Emergent Sparsity in Frozen Random CNN Feature Extractors for Deep Reinforcement Learning](https://mlsanity.com/paper/2607.26059/) (2026)
- [Input-Layer Starvation: Why Per-Layer Pruning Breaks IoT Intrusion Detectors](https://mlsanity.com/paper/2609.30729/) (2026)

## Abstract (arXiv)

Random masks define surprisingly effective sparse neural network models, as has been shown empirically. The resulting sparse networks can often compete with dense architectures and state-of-the-art lottery ticket pruning algorithms, even though they do not rely on computationally expensive prune-train iterations and can be drawn initially without significant computational overhead. We offer a theoretical explanation of how random masks can approximate arbitrary target networks if they are wider by a logarithmic factor in the inverse sparsity 1 / log(1/sparsity). This overparameterization factor is necessary at least for 3-layer random networks, which elucidates the observed degrading performance of random networks at higher sparsity. At moderate to high sparsity levels, however, our results imply that sparser networks are contained within random source networks so that any dense-to-sparse training scheme can be turned into a computationally more efficient sparse-to-sparse one by constraining the search to a fixed random mask. We demonstrate the feasibility of this approach in experiments for different pruning methods and propose particularly effective choices of initial layer-wise sparsity ratios of the random source network. As a special case, we show theoretically and experimentally that random source networks also contain strong lottery tickets.