# A Recovery Guarantee for Sparse Neural Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 43 references that are in the map.
- First posted on arXiv 24 Sep 2025.

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

- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains](https://mlsanity.com/paper/2006.10739/) (2020)
- [A Survey on Deep Neural Network Pruning-Taxonomy, Comparison, Analysis, and Recommendations](https://mlsanity.com/paper/2308.06767/) (2023)
- [Pruning Neural Networks at Initialization: Why are We Missing the Mark?](https://mlsanity.com/paper/2009.08576/) (2020)
- [Soft Threshold Weight Reparameterization for Learnable Sparsity](https://mlsanity.com/paper/2002.03231/) (2020)
- [Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks](https://mlsanity.com/paper/2002.10553/) (2020)
- [A Winning Hand: Compressing Deep Networks Can Improve Out-Of-Distribution Robustness](https://mlsanity.com/paper/2106.09129/) (2021)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Convex Geometry and Duality of Over-parameterized Neural Networks](https://mlsanity.com/paper/2002.11219/) (2020)
- [Recent Advances on Neural Network Pruning at Initialization](https://mlsanity.com/paper/2103.06460/) (2021)
- [Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositions](https://mlsanity.com/paper/2202.01331/) (2022)
- [A Survey of Lottery Ticket Hypothesis](https://mlsanity.com/paper/2403.04861/) (2024)
- [Penalising the biases in norm regularisation enforces sparsity](https://mlsanity.com/paper/2303.01353/) (2023)
- [Fantastic Weights and How to Find Them: Where to Prune in Dynamic Sparse Training](https://mlsanity.com/paper/2306.12230/) (2023)
- [Training Skinny Deep Neural Networks with Iterative Hard Thresholding Methods](https://mlsanity.com/paper/1607.05423/) (2016)
- [Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networks](https://mlsanity.com/paper/2110.09548/) (2021)
- [MISSION: Ultra Large-Scale Feature Selection using Count-Sketches](https://mlsanity.com/paper/1806.04310/) (2018)
- [Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time](https://mlsanity.com/paper/2402.03625/) (2024)
- [Dynamic Sparse Training versus Dense Training: The Unexpected Winner in Image Corruption Robustness](https://mlsanity.com/paper/2410.03030/) (2024)
- [IHT dies hard: Provable accelerated Iterative Hard Thresholding](https://mlsanity.com/paper/1712.09379/) (2017)
- [DRIVE: Dual Gradient-Based Rapid Iterative Pruning](https://mlsanity.com/paper/2404.03687/) (2024)
- [Learning a Sparse Neural Network using IHT](https://mlsanity.com/paper/2404.18414/) (2024)
- [Gradient-based Weight Density Balancing for Robust Dynamic Sparse Training](https://mlsanity.com/paper/2210.14012/) (2022)
- [Information Consistent Pruning: How to Efficiently Search for Sparse Networks?](https://mlsanity.com/paper/2501.15592/) (2025)

## Abstract (arXiv)

We prove the first guarantees of sparse recovery for ReLU neural networks, where the sparse network weights constitute the signal to be recovered. Specifically, we study structural properties of the sparse network weights for two-layer, scalar-output networks under which a simple iterative hard thresholding algorithm recovers these weights exactly, using memory that grows linearly in the number of nonzero weights. We validate this theoretical result with simple experiments on recovery of sparse planted MLPs, MNIST classification, and implicit neural representations. Experimentally, we find performance that is competitive with, and often exceeds, a high-performing but memory-inefficient baseline based on iterative magnitude pruning. Code is available at https://github.com/voilalab/MLP-IHT.