# SHRIMP: Sparser Random Feature Models via Iterative Magnitude Pruning

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 63 references that are in the map.
- First posted on arXiv 7 Dec 2021.

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

- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [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)
- [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [Double Trouble in Double Descent : Bias and Variance(s) in the Lazy Regime](https://mlsanity.com/paper/2003.01054/) (2020)
- [Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient](https://mlsanity.com/paper/2006.07990/) (2020)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Logarithmic Pruning is All You Need](https://mlsanity.com/paper/2006.12156/) (2020)
- [A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent](https://mlsanity.com/paper/2006.05013/) (2020)
- [On weight initialization in deep neural networks](https://mlsanity.com/paper/1704.08863/) (2017)
- [Implicit Regularization of Random Feature Models](https://mlsanity.com/paper/2002.08404/) (2020)
- [On the Convergence of the SINDy Algorithm](https://mlsanity.com/paper/1805.06445/) (2018)
- [Efficient Lottery Ticket Finding: Less Data is More](https://mlsanity.com/paper/2106.03225/) (2021)
- [Lottery Tickets in Linear Models: An Analysis of Iterative Magnitude Pruning](https://mlsanity.com/paper/2007.08243/) (2020)
- [Generalization Bounds for Sparse Random Feature Expansions](https://mlsanity.com/paper/2103.03191/) (2021)
- [Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks](https://mlsanity.com/paper/2110.05667/) (2021)
- [Interpretable Approximation of High-Dimensional Data](https://mlsanity.com/paper/2103.13787/) (2021)
- [Additive Approximations in High Dimensional Nonparametric Regression via the SALSA](https://mlsanity.com/paper/1602.00287/) (2016)
- [Conditioning of Random Feature Matrices: Double Descent and Generalization Error](https://mlsanity.com/paper/2110.11477/) (2021)
- [Additive function approximation in the brain](https://mlsanity.com/paper/1909.02603/) (2019)
- [Sparse Recovery With Non-Linear Fourier Features](https://mlsanity.com/paper/2002.04985/) (2020)

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

- [HARFE: Hard-Ridge Random Feature Expansion](https://mlsanity.com/paper/2202.02877/) (2022)
- [Random Feature Models for Learning Interacting Dynamical Systems](https://mlsanity.com/paper/2212.05591/) (2022)
- [Concentration of Random Feature Matrices in High-Dimensions](https://mlsanity.com/paper/2204.06935/) (2022)
- [SRMD: Sparse Random Mode Decomposition](https://mlsanity.com/paper/2204.06108/) (2022)
- [Cauchy Random Features for Operator Learning in Sobolev Space](https://mlsanity.com/paper/2503.00300/) (2025)
- [SPADE4: Sparsity and Delay Embedding based Forecasting of Epidemics](https://mlsanity.com/paper/2211.08277/) (2022)
- [ANOVA-boosting for Random Fourier Features](https://mlsanity.com/paper/2404.03050/) (2024)
- [Generative Feature Training of Thin 2-Layer Networks](https://mlsanity.com/paper/2411.06848/) (2024)
- [Differentially Private Random Feature Model](https://mlsanity.com/paper/2412.04785/) (2024)

## Abstract (arXiv)

Sparse shrunk additive models and sparse random feature models have been developed separately as methods to learn low-order functions, where there are few interactions between variables, but neither offers computational efficiency. On the other hand, ℓ2-based shrunk additive models are efficient but do not offer feature selection as the resulting coefficient vectors are dense. Inspired by the success of the iterative magnitude pruning technique in finding lottery tickets of neural networks, we propose a new method -- Sparser Random Feature Models via IMP (ShRIMP) -- to efficiently fit high-dimensional data with inherent low-dimensional structure in the form of sparse variable dependencies. Our method can be viewed as a combined process to construct and find sparse lottery tickets for two-layer dense networks. We explain the observed benefit of SHRIMP through a refined analysis on the generalization error for thresholded Basis Pursuit and resulting bounds on eigenvalues. From function approximation experiments on both synthetic data and real-world benchmark datasets, we show that SHRIMP obtains better than or competitive test accuracy compared to state-of-art sparse feature and additive methods such as SRFE-S, SSAM, and SALSA. Meanwhile, SHRIMP performs feature selection with low computational complexity and is robust to the pruning rate, indicating a robustness in the structure of the obtained subnetworks. We gain insight into the lottery ticket hypothesis through SHRIMP by noting a correspondence between our model and weight/neuron subnetworks.