mlsanityData to 14 Oct 2026

A Recovery Guarantee for Sparse Neural Networks

arXiv 2509.20323 ↗First posted 24 Sep 2025cs.LG math.OC stat.MLcited by 0

Not on the map. Why?

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.

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

25 of 43 references.

References · 25

  1. 2020Scaling Laws for Neural Language Modelscited by 6,586
  2. 2018The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networkscited by 2,262
  3. 2020Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domainscited by 2,200
  4. 2023A Survey on Deep Neural Network Pruning-Taxonomy, Comparison, Analysis, and Recommendationscited by 202
  5. 2020Pruning Neural Networks at Initialization: Why are We Missing the Mark?cited by 182
  6. 2020Soft Threshold Weight Reparameterization for Learnable Sparsitycited by 151
  7. 2020Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networkscited by 98
  8. 2021A Winning Hand: Compressing Deep Networks Can Improve Out-Of-Distribution Robustnesscited by 62
  9. 2014On Iterative Hard Thresholding Methods for High-dimensional M-Estimationcited by 53
  10. 2020Convex Geometry and Duality of Over-parameterized Neural Networkscited by 49
  11. 2021Recent Advances on Neural Network Pruning at Initializationcited by 41
  12. 2022Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model Classes and Cone Decompositionscited by 31
13 more
  1. 2024A Survey of Lottery Ticket Hypothesiscited by 24
  2. 2023Penalising the biases in norm regularisation enforces sparsitycited by 19
  3. 2023Fantastic Weights and How to Find Them: Where to Prune in Dynamic Sparse Trainingcited by 17
  4. 2016Training Skinny Deep Neural Networks with Iterative Hard Thresholding Methodscited by 16
  5. 2021Path Regularization: A Convexity and Sparsity Inducing Regularization for Parallel ReLU Networkscited by 14
  6. 2018MISSION: Ultra Large-Scale Feature Selection using Count-Sketchescited by 11
  7. 2024Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Timecited by 11
  8. 2024Dynamic Sparse Training versus Dense Training: The Unexpected Winner in Image Corruption Robustnesscited by 11
  9. 2017IHT dies hard: Provable accelerated Iterative Hard Thresholdingcited by 10
  10. 2024DRIVE: Dual Gradient-Based Rapid Iterative Pruningcited by 3
  11. 2024Learning a Sparse Neural Network using IHTcited by 2
  12. 2022Gradient-based Weight Density Balancing for Robust Dynamic Sparse Trainingcited by 1
  13. 2025Information Consistent Pruning: How to Efficiently Search for Sparse Networks?cited by 1

Built on by

Not cited yet.