# Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection

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

## Key facts

- Cited by 70 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2020.

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

- [A Survey on Deep Neural Network Pruning-Taxonomy, Comparison, Analysis, and Recommendations](https://mlsanity.com/paper/2308.06767/) (2023)
- [Structured Pruning for Deep Convolutional Neural Networks: A survey](https://mlsanity.com/paper/2303.00566/) (2023)
- [Multi-Prize Lottery Ticket Hypothesis: Finding Accurate Binary Neural Networks by Pruning A Randomly Weighted Network](https://mlsanity.com/paper/2103.09377/) (2021)
- [Effective Sparsification of Neural Networks with Global Sparsity Constraint](https://mlsanity.com/paper/2105.01571/) (2021)
- [The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networks](https://mlsanity.com/paper/2203.04466/) (2022)
- [On the Soft-Subnetwork for Few-shot Class Incremental Learning](https://mlsanity.com/paper/2209.07529/) (2022)
- [CHEX: CHannel EXploration for CNN Model Compression](https://mlsanity.com/paper/2203.15794/) (2022)
- [AlphaPruning: Using Heavy-Tailed Self Regularization Theory for Improved Layer-wise Pruning of Large Language Models](https://mlsanity.com/paper/2410.10912/) (2024)
- [Topology-Aware Network Pruning using Multi-stage Graph Embedding and Reinforcement Learning](https://mlsanity.com/paper/2102.03214/) (2021)
- [Efficient Neural Network Training via Forward and Backward Propagation Sparsification](https://mlsanity.com/paper/2111.05685/) (2021)
- [GDP: Stabilized Neural Network Pruning via Gates with Differentiable Polarization](https://mlsanity.com/paper/2109.02220/) (2021)
- [Locally Free Weight Sharing for Network Width Search](https://mlsanity.com/paper/2102.05258/) (2021)
- [Consistent Sparse Deep Learning: Theory and Computation](https://mlsanity.com/paper/2102.13229/) (2021)
- [Pruning Deep Neural Networks from a Sparsity Perspective](https://mlsanity.com/paper/2302.05601/) (2023)
- [On the Effect of Pruning on Adversarial Robustness](https://mlsanity.com/paper/2108.04890/) (2021)
- [Data-Efficient Structured Pruning via Submodular Optimization](https://mlsanity.com/paper/2203.04940/) (2022)
- [Lottery Ticket Preserves Weight Correlation: Is It Desirable or Not?](https://mlsanity.com/paper/2102.11068/) (2021)
- [Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptions](https://mlsanity.com/paper/2209.08554/) (2022)
- [Auto-Train-Once: Controller Network Guided Automatic Network Pruning from Scratch](https://mlsanity.com/paper/2403.14729/) (2024)
- [RED++ : Data-Free Pruning of Deep Neural Networks via Input Splitting and Output Merging](https://mlsanity.com/paper/2110.01397/) (2021)
- [SGD and Weight Decay Secretly Minimize the Rank of Your Neural Network](https://mlsanity.com/paper/2206.05794/) (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)
- [Interpretations Steered Network Pruning via Amortized Inferred Saliency Maps](https://mlsanity.com/paper/2209.02869/) (2022)
- [Equal Bits: Enforcing Equally Distributed Binary Network Weights](https://mlsanity.com/paper/2112.03406/) (2021)
- [On the Neural Tangent Kernel Analysis of Randomly Pruned Neural Networks](https://mlsanity.com/paper/2203.14328/) (2022)
- [Jointly Training and Pruning CNNs via Learnable Agent Guidance and Alignment](https://mlsanity.com/paper/2403.19490/) (2024)
- [Stable Recovery of Entangled Weights: Towards Robust Identification of Deep Neural Networks from Minimal Samples](https://mlsanity.com/paper/2101.07150/) (2021)
- [Heavy Ball Momentum for Conditional Gradient](https://mlsanity.com/paper/2110.04243/) (2021)

## Abstract (arXiv)

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