# Pruning is Optimal for Learning Sparse Features in High-Dimensions

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 55 references that are in the map.
- First posted on arXiv 12 Jun 2024.

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

- [The State of Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1902.09574/) (2019)
- [The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents](https://mlsanity.com/paper/2402.03220/) (2024)
- [Disentangling feature and lazy training in deep neural networks](https://mlsanity.com/paper/1906.08034/) (2019)
- [No Free Prune: Information-Theoretic Barriers to Pruning at Initialization](https://mlsanity.com/paper/2402.01089/) (2024)

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

- [Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics](https://mlsanity.com/paper/2408.07254/) (2024)
- [Robust Feature Learning for Multi-Index Models in High Dimensions](https://mlsanity.com/paper/2410.16449/) (2024)
- [On the creation of narrow AI: hierarchy and nonlocality of neural network skills](https://mlsanity.com/paper/2505.15811/) (2025)
- [From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD](https://mlsanity.com/paper/2510.21020/) (2025)
- [Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model](https://mlsanity.com/paper/2606.15219/) (2026)

## Abstract (arXiv)

While it is commonly observed in practice that pruning networks to a certain level of sparsity can improve the quality of the features, a theoretical explanation of this phenomenon remains elusive. In this work, we investigate this by demonstrating that a broad class of statistical models can be optimally learned using pruned neural networks trained with gradient descent, in high-dimensions. We consider learning both single-index and multi-index models of the form y = σ^*(boldsymbolVtop boldsymbolx) + ε, where σ^* is a degree-p polynomial, and boldsymbolV ∈ mathbbmRd × r with r ll d, is the matrix containing relevant model directions. We assume that boldsymbolV satisfies a certain ℓq-sparsity condition for matrices and show that pruning neural networks proportional to the sparsity level of boldsymbolV improves their sample complexity compared to unpruned networks. Furthermore, we establish Correlational Statistical Query (CSQ) lower bounds in this setting, which take the sparsity level of boldsymbolV into account. We show that if the sparsity level of boldsymbolV exceeds a certain threshold, training pruned networks with a gradient descent algorithm achieves the sample complexity suggested by the CSQ lower bound. In the same scenario, however, our results imply that basis-independent methods such as models trained via standard gradient descent initialized with rotationally invariant random weights can provably achieve only suboptimal sample complexity.