A Recovery Guarantee for Sparse Neural Networks
This addresses the challenge of memory efficiency in sparse neural networks for machine learning practitioners, offering a novel theoretical foundation with practical benefits.
The paper tackles the problem of recovering sparse weights in ReLU neural networks, proving the first theoretical guarantees for exact recovery using an iterative hard thresholding algorithm with linear memory growth. Experimental results show competitive or superior performance compared to a memory-inefficient baseline in tasks like MNIST classification and implicit neural representations.
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.