Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection

By Mao Ye, Chengyue Gong, Lizhen Nie, Denny Zhou, Adam R. Klivans, Qiang Liu. 2020

123 citations recorded by the source corpus.

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}.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Efficiency & Compression

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Simon Lacoste-Julien
2. Marwa El Halabi
3. Suraj Srinivas
4. Qiang Liu
5. Lemeng Wu
6. Mao Ye
7. Yang He
8. Lingao Xiao

In Computer Vision and Pattern Recognition

1. Simon Lacoste-Julien
2. Marwa El Halabi
3. Suraj Srinivas
4. Lemeng Wu
5. Mao Ye
6. Yang He
7. Lingao Xiao
8. Qiang Liu

In Efficiency & Compression

1. Simon Lacoste-Julien
2. Marwa El Halabi
3. Suraj Srinivas
4. Mao Ye
5. Yang He
6. Lingao Xiao
7. Qiang Liu
8. Lemeng Wu

Citations in the corpus

• Data-Efficient Structured Pruning via Submodular Optimization (2022, methodology): “Among these works only [Ye et al., 2020b] provides theoretical guarantees, showing an O ( e − ck ) error rate.”
• Structured Pruning for Deep Convolutional Neural Networks: A Survey (2023, background): “2 Adjacent Layer ThiNet [66], AOFP [67], GFS [68]”
• Effective Sparsification of Neural Networks with Global Sparsity Constraint (2021, unknown): “Network Pruning [10, 8, 39, 21, 24, 14, 41, 17, 34, 30, 38] has been extensively studied in recent years to reduce the model size and improve the inference efficiency of deep neural networks.”
• A Survey on Deep Neural Network Pruning: Taxonomy, Comparison, Analysis, and Recommendations (2023, unknown): “Additionally, the results in [140], [192] show that fine-tuning is necessary for better performance on sparse mobile networks than training from scratch.”
• Greedy Optimization Provably Wins the Lottery: Logarithmic Number of Winning Tickets is Enough (2020, methodology): “, 2020), greedy forward selection (Ye et al., 2020).”