# Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Apr 2018.

## Built on by (most cited first, 30 of 43)

- [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021)
- [Structured Pruning for Deep Convolutional Neural Networks: A survey](https://mlsanity.com/paper/2303.00566/) (2023)
- [Lost in Pruning: The Effects of Pruning Neural Networks beyond Test Accuracy](https://mlsanity.com/paper/2103.03014/) (2021)
- [The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networks](https://mlsanity.com/paper/2203.04466/) (2022)
- [Compressing Neural Networks: Towards Determining the Optimal Layer-wise Decomposition](https://mlsanity.com/paper/2107.11442/) (2021)
- [Pruning's Effect on Generalization Through the Lens of Training and Regularization](https://mlsanity.com/paper/2210.13738/) (2022)
- [Gradient-Free Structured Pruning with Unlabeled Data](https://mlsanity.com/paper/2303.04185/) (2023)
- [Pruning Deep Neural Networks from a Sparsity Perspective](https://mlsanity.com/paper/2302.05601/) (2023)
- [Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms](https://mlsanity.com/paper/2203.02474/) (2022)
- [Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptions](https://mlsanity.com/paper/2209.08554/) (2022)
- [A Unified Approach to Coreset Learning](https://mlsanity.com/paper/2111.03044/) (2021)
- [A Probabilistic Approach to Neural Network Pruning](https://mlsanity.com/paper/2105.10065/) (2021)
- [Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks](https://mlsanity.com/paper/2110.05667/) (2021)
- [Sparse Flows: Pruning Continuous-depth Models](https://mlsanity.com/paper/2106.12718/) (2021)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [On Measuring Excess Capacity in Neural Networks](https://mlsanity.com/paper/2202.08070/) (2022)
- [Recall Distortion in Neural Network Pruning and the Undecayed Pruning Algorithm](https://mlsanity.com/paper/2206.02976/) (2022)
- [Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regions](https://mlsanity.com/paper/2301.07966/) (2023)
- [Coresets for Data Discretization and Sine Wave Fitting](https://mlsanity.com/paper/2203.03009/) (2022)
- [Obstacle Aware Sampling for Path Planning](https://mlsanity.com/paper/2203.04075/) (2022)
- [Data-Efficient Training of CNNs and Transformers with Coresets: A Stability Perspective](https://mlsanity.com/paper/2303.02095/) (2023)
- [A Theoretical Understanding of Neural Network Compression from Sparse Linear Approximation](https://mlsanity.com/paper/2206.05604/) (2022)
- [Low-Regret Active learning](https://mlsanity.com/paper/2104.02822/) (2021)
- [Robust Learning of Parsimonious Deep Neural Networks](https://mlsanity.com/paper/2205.04650/) (2022)
- [A Deeper Look into Convolutions via Eigenvalue-based Pruning](https://mlsanity.com/paper/2102.02804/) (2021)
- [Probabilistic fine-tuning of pruning masks and PAC-Bayes self-bounded learning](https://mlsanity.com/paper/2110.11804/) (2021)
- [The Effect of Data Dimensionality on Neural Network Prunability](https://mlsanity.com/paper/2212.00291/) (2022)
- [How Informative is the Approximation Error from Tensor Decomposition for Neural Network Compression?](https://mlsanity.com/paper/2305.05318/) (2023)
- ["Forgetting" in Machine Learning and Beyond: A Survey](https://mlsanity.com/paper/2405.20620/) (2024)
- [Provable Pruning for Efficient 3D Gaussian Splatting via Coresets](https://mlsanity.com/paper/2607.02721/) (2026)

## Abstract (arXiv)

We present an efficient coresets-based neural network compression algorithm that sparsifies the parameters of a trained fully-connected neural network in a manner that provably approximates the network's output. Our approach is based on an importance sampling scheme that judiciously defines a sampling distribution over the neural network parameters, and as a result, retains parameters of high importance while discarding redundant ones. We leverage a novel, empirical notion of sensitivity and extend traditional coreset constructions to the application of compressing parameters. Our theoretical analysis establishes guarantees on the size and accuracy of the resulting compressed network and gives rise to generalization bounds that may provide new insights into the generalization properties of neural networks. We demonstrate the practical effectiveness of our algorithm on a variety of neural network configurations and real-world data sets.