# Structured vs. Unstructured Pruning: An Exponential Gap

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 21 references that are in the map.
- First posted on arXiv 13 Feb 2026.

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

- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021)
- [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)
- [Proving the Lottery Ticket Hypothesis: Pruning is All You Need](https://mlsanity.com/paper/2002.00585/) (2020)
- [Structured Pruning for Deep Convolutional Neural Networks: A survey](https://mlsanity.com/paper/2303.00566/) (2023)
- [On the Power and Limitations of Random Features for Understanding Neural Networks](https://mlsanity.com/paper/1904.00687/) (2019)
- [Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient](https://mlsanity.com/paper/2006.07990/) (2020)
- [Pruning from Scratch](https://mlsanity.com/paper/1909.12579/) (2019)
- [Logarithmic Pruning is All You Need](https://mlsanity.com/paper/2006.12156/) (2020)
- [On the Existence of Universal Lottery Tickets](https://mlsanity.com/paper/2111.11146/) (2021)
- [On the Approximation Power of Two-Layer Networks of Random ReLUs](https://mlsanity.com/paper/2102.02336/) (2021)
- [Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity](https://mlsanity.com/paper/2003.04180/) (2020)
- [Most Activation Functions Can Win the Lottery Without Excessive Depth](https://mlsanity.com/paper/2205.02321/) (2022)
- [A General Framework For Proving The Equivariant Strong Lottery Ticket Hypothesis](https://mlsanity.com/paper/2206.04270/) (2022)
- [Convolutional and Residual Networks Provably Contain Lottery Tickets](https://mlsanity.com/paper/2205.02343/) (2022)
- [Lottery Tickets with Nonzero Biases](https://mlsanity.com/paper/2110.11150/) (2021)
- [Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets](https://mlsanity.com/paper/2311.09858/) (2023)

## Abstract (arXiv)

The Strong Lottery Ticket Hypothesis (SLTH) states that large, randomly initialized neural networks contain sparse subnetworks capable of approximating a target function at initialization without training, suggesting that pruning alone is sufficient. Pruning methods are typically classified as unstructured, where individual weights can be removed from the network, and structured, where parameters are removed according to specific patterns, as in neuron pruning. Existing theoretical results supporting the SLTH rely almost exclusively on unstructured pruning, showing that logarithmic overparameterization suffices to approximate simple target networks. In contrast, neuron pruning has received limited theoretical attention, despite its practical appeal for direct hardware speedups. In this work, we consider the problem of approximating a single bias-free ReLU neuron by pruning hidden units of a randomly initialized two-layer ReLU network, effectively isolating the intrinsic limitations of neuron pruning. We show that achieving an varepsilon-approximation requires a starting network size of Omega(1/varepsilon) for neuron pruning, whereas weight pruning succeeds with only O(log(1/varepsilon)) hidden units, revealing an exponential separation between the two approaches.