# Pruning at Initialization -- A Sketching Perspective

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 67 of its 89 references that are in the map.
- First posted on arXiv 27 May 2023.

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

- [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)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (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)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Linear Mode Connectivity and the Lottery Ticket Hypothesis](https://mlsanity.com/paper/1912.05671/) (2019)
- [Learning Sparse Neural Networks through L0 Regularization](https://mlsanity.com/paper/1712.01312/) (2017)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [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)
- [Picking Winning Tickets Before Training by Preserving Gradient Flow](https://mlsanity.com/paper/2002.07376/) (2020)
- [Robust Loss Functions under Label Noise for Deep Neural Networks](https://mlsanity.com/paper/1712.09482/) (2017)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [Scalable Training of Artificial Neural Networks with Adaptive Sparse Connectivity inspired by Network Science](https://mlsanity.com/paper/1707.04780/) (2017)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Speeding up Convolutional Neural Networks with Low Rank Expansions](https://mlsanity.com/paper/1405.3866/) (2014)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [Tensorizing Neural Networks](https://mlsanity.com/paper/1509.06569/) (2015)
- [Neural Architecture Search without Training](https://mlsanity.com/paper/2006.04647/) (2020)
- [What's Hidden in a Randomly Weighted Neural Network?](https://mlsanity.com/paper/1911.13299/) (2019)
- [Dynamic Network Surgery for Efficient DNNs](https://mlsanity.com/paper/1608.04493/) (2016)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Zero-Cost Proxies for Lightweight NAS](https://mlsanity.com/paper/2101.08134/) (2021)
- [Parameter Efficient Training of Deep Convolutional Neural Networks by Dynamic Sparse Reparameterization](https://mlsanity.com/paper/1902.05967/) (2019)
- [A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks](https://mlsanity.com/paper/1810.02281/) (2018)
- [Drawing Early-Bird Tickets: Towards More Efficient Training of Deep Networks](https://mlsanity.com/paper/1909.11957/) (2019)

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

- [Diverse Subset Selection via Norm-Based Sampling and Orthogonality](https://mlsanity.com/paper/2406.01086/) (2024)
- [Beyond Structural Symmetries: Linear Mode Connectivity via Neuron Identifiability](https://mlsanity.com/paper/2606.04754/) (2026)

## Abstract (arXiv)

The lottery ticket hypothesis (LTH) has increased attention to pruning neural networks at initialization. We study this problem in the linear setting. We show that finding a sparse mask at initialization is equivalent to the sketching problem introduced for efficient matrix multiplication. This gives us tools to analyze the LTH problem and gain insights into it. Specifically, using the mask found at initialization, we bound the approximation error of the pruned linear model at the end of training. We theoretically justify previous empirical evidence that the search for sparse networks may be data independent. By using the sketching perspective, we suggest a generic improvement to existing algorithms for pruning at initialization, which we show to be beneficial in the data-independent case.