Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection

Abstract

Recent empirical works show that large deep neural networks are often highly redundant and one can find much smaller subnetworks without a significant drop of accuracy. However, most existing methods of network pruning are empirical and heuristic, leaving it open whether good subnetworks provably exist, how to find them efficiently, and if network pruning can be provably better than direct training using gradient descent. We answer these problems positively by proposing a simple greedy selection approach for finding good subnetworks, which starts from an empty network and greedily adds important neurons from the large network. This differs from the existing methods based on backward elimination, which remove redundant neurons from the large network. Theoretically, applying the greedy selection strategy on sufficiently large {pre-trained} networks guarantees to find small subnetworks with lower loss than networks directly trained with gradient descent. Our results also apply to pruning randomly weighted networks. Practically, we improve prior arts of network pruning on learning compact neural architectures on ImageNet, including ResNet, MobilenetV2/V3, and ProxylessNet. Our theory and empirical results on MobileNet suggest that we should fine-tune the pruned subnetworks to leverage the information from the large model, instead of re-training from new random initialization as suggested in \citet{liu2018rethinking}.

ICML 2020

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
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Rethinking the Value of Network Pruning
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• Convergence Rate of Frank-Wolfe for Non-Convex Objectives
• MetaPruning: Meta Learning for Automatic Neural Network Channel Pruning
• Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit
• Proving the Lottery Ticket Hypothesis: Pruning is All You Need
• On the Equivalence between Herding and Conditional Gradient Algorithms
• A mean-field limit for certain deep neural networks
• Super-Samples from Kernel Herding
• Provable Filter Pruning for Efficient Neural Networks
• Data-Independent Neural Pruning via Coresets
• SiPPing Neural Networks: Sensitivity-informed Provable Pruning of Neural Networks

Cited by in corpus (15)

• DyNet: Dynamic Convolution for Accelerating Convolutional Neural Networks
• Locally Free Weight Sharing for Network Width Search
• Accelerate CNNs from Three Dimensions: A Comprehensive Pruning Framework
• A Gradient Flow Framework For Analyzing Network Pruning
• Efficient Neural Network Training via Forward and Backward Propagation Sparsification
• Multi-Prize Lottery Ticket Hypothesis: Finding Accurate Binary Neural Networks by Pruning A Randomly Weighted Network
• Adaptive Dense-to-Sparse Paradigm for Pruning Online Recommendation System with Non-Stationary Data
• Consistent Sparse Deep Learning: Theory and Computation
• DeepLight: Deep Lightweight Feature Interactions for Accelerating CTR Predictions in Ad Serving
• Effective Sparsification of Neural Networks with Global Sparsity Constraint
• Greedy Optimization Provably Wins the Lottery: Logarithmic Number of Winning Tickets is Enough
• Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks
• BWCP: Probabilistic Learning-to-Prune Channels for ConvNets via Batch Whitening
• The curious case of developmental BERTology: On sparsity, transfer learning, generalization and the brain
• AutoBSS: An Efficient Algorithm for Block Stacking Style Search