Data-Independent Neural Pruning via Coresets

Abstract

Previous work showed empirically that large neural networks can be significantly reduced in size while preserving their accuracy. Model compression became a central research topic, as it is crucial for deployment of neural networks on devices with limited computational and memory resources. The majority of the compression methods are based on heuristics and offer no worst-case guarantees on the trade-off between the compression rate and the approximation error for an arbitrarily new sample. We propose the first efficient, data-independent neural pruning algorithm with a provable trade-off between its compression rate and the approximation error for any future test sample. Our method is based on the coreset framework, which finds a small weighted subset of points that provably approximates the original inputs. Specifically, we approximate the output of a layer of neurons by a coreset of neurons in the previous layer and discard the rest. We apply this framework in a layer-by-layer fashion from the top to the bottom. Unlike previous works, our coreset is data independent, meaning that it provably guarantees the accuracy of the function for any input $x\in {\mathbb{R}}^d$, including an adversarial one. We demonstrate the effectiveness of our method on popular network architectures. In particular, our coresets yield 90\% compression of the LeNet-300-100 architecture on MNIST while improving the accuracy.

References in corpus (7)

• Exploiting Linear Structure Within Convolutional Networks for Efficient Evaluation
• Network Trimming: A Data-Driven Neuron Pruning Approach towards Efficient Deep Architectures
• A Convergence Theory for Deep Learning via Over-Parameterization
• The State of Sparsity in Deep Neural Networks
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• Compression-aware Training of Deep Networks
• A Note on Randomized Element-wise Matrix Sparsification

Cited by in corpus (7)

• Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection
• Sanity-Checking Pruning Methods: Random Tickets can Win the Jackpot
• Coresets for Classification -- Simplified and Strengthened
• Coresets for Clustering with Missing Values
• Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks
• Statistical Mechanical Analysis of Neural Network Pruning
• Symmetric Norm Estimation and Regression on Sliding Windows