Greedy Optimization Provably Wins the Lottery: Logarithmic Number of Winning Tickets is Enough
arXiv:2010.15969
Abstract
Despite the great success of deep learning, recent works show that large deep neural networks are often highly redundant and can be significantly reduced in size. However, the theoretical question of how much we can prune a neural network given a specified tolerance of accuracy drop is still open. This paper provides one answer to this question by proposing a greedy optimization based pruning method. The proposed method has the guarantee that the discrepancy between the pruned network and the original network decays with exponentially fast rate w.r.t. the size of the pruned network, under weak assumptions that apply for most practical settings. Empirically, our method improves prior arts on pruning various network architectures including ResNet, MobilenetV2/V3 on ImageNet.
References in corpus (16)
- Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation
- Deep Speech 2: End-to-End Speech Recognition in English and Mandarin
- SGDR: Stochastic Gradient Descent with Warm Restarts
- The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
- AMC: AutoML for Model Compression and Acceleration on Mobile Devices
- Variational Dropout Sparsifies Deep Neural Networks
- MetaPruning: Meta Learning for Automatic Neural Network Channel Pruning
- Proving the Lottery Ticket Hypothesis: Pruning is All You Need
- Soft Filter Pruning for Accelerating Deep Convolutional Neural Networks
- Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection
- A mean-field limit for certain deep neural networks
- Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization is Sufficient
- SiPPing Neural Networks: Sensitivity-informed Provable Pruning of Neural Networks
- Lottery Tickets in Linear Models: An Analysis of Iterative Magnitude Pruning
- Logarithmic Pruning is All You Need
- Steepest Descent Neural Architecture Optimization: Escaping Local Optimum with Signed Neural Splitting