Source-linked AI summary
Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection
Mao Ye, Chengyue Gong, Lizhen Nie, Denny Zhou, Adam Klivans, Qiang Liu
TL;DR
Network pruning has empirical success, but its theoretical guarantees, efficient search, and ability to outperform direct training remain open questions. The paper proposes greedy forward selection from pretrained networks and reports theoretical advantages and improved ImageNet pruning results. It also identifies limits in the theoretical analysis, which covers two-layer networks and mean-field parameterization.
Problem
Despite empirical pruning successes, theoretical understanding of why and how it works remains limited, including whether good subnetworks exist, can be found efficiently, and outperform same-size networks trained from scratch.
Source: §1 · p. 1Method
Results
Takeaways & Limitations
The authors emphasize using sufficiently large pretrained models and fine-tuning selected subnetworks rather than retraining them from random initialization.
Source: §6 · p. 9The analysis covers two-layer networks and mean-field parameterization; generalization to deep networks and other parameterizations remains future work.
Source: §3.6 · pp. 5–6
Abstract
from arXiv · showhide
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}.
1. Introduction
The paper addresses whether good, small subnetworks exist inside large neural networks, how to find them efficiently, and whether they can outperform same-size networks trained from scratch. It proposes greedy forward selection and presents theoretical guarantees and empirical results for this approach.
1. Introduction
- The paper asks whether large pretrained networks contain small subnetworks with nearly as good performance, how to find them efficiently, and whether they beat same-size networks trained from scratch.Source: §1 · p. 1
2. Problem and Method
- Greedy forward selection starts from an empty network and sequentially adds neurons from the pretrained model that yield the largest immediate loss decrease.The method contrasts with pruning approaches that begin with a large network and remove redundant neurons.Source: §1 · p. 1, Figure 1 · p. 2
1. Introduction
- For two-layer networks, a size-n subnetwork has loss O(1/n) + L*_N, and sufficiently over-parameterized networks yield O(1/n^2), including with randomly drawn weights.L*_N is the optimal loss achievable with all N neurons in the pretrained network.Source: §1 · pp. 1–2
- The authors argue the O(1/n^2) rate implies pruning sufficiently over-parameterized models can find more accurate small networks than direct gradient-descent training.Source: §1 · p. 2
- Under fixed FLOPs constraints, forward selection achieves better accuracy than prior pruning methods on ImageNet ResNet, MobileNetV2, ProxylessNet, and MobileNetV3, and leads MobileNetV2 across FLOPs constraints.The authors report the best top-1 accuracy for MobileNetV2 under any FLOPs constraint.Source: §1 · p. 2
- For MobileNetV2 and MobileNetV3, fine-tuning pruned subnetworks performs much better than retraining from random initialization; larger pretrained models also yield better subnetworks.The authors recommend fine-tuning to leverage information in the large model's structure and parameters.Source: §1 · p. 2
3. Theoretical Analysis
The analysis establishes convergence guarantees for greedy subnetwork selection, including a faster rate under over-parameterization that supports lower loss than direct gradient-descent training of same-size networks. It also extends the rate to randomly weighted networks and compares forward selection with backward elimination.
3. Theoretical Analysis
- Under the stated assumptions, greedy selection achieves O(1/n^2), which is provably better than the O(1/n + ε) loss bound for size-n gradient-descent training from scratch.The comparison is for sufficiently over-parameterized large networks that can fit bounded perturbations of the training labels.Source: §3 · p. 3
3.1. General Convergence Rate
- Under boundedness and smoothness, a selected subnetwork has loss O(1/n) + L*_N, where L*_N is the best loss achievable by convex combinations of the large network’s neurons.This general rate applies to an original network of any size; a larger network can make L*_N smaller.Source: §3.1 · p. 3, §3 · p. 3
3.2. Faster Rate With Over-parameterized Networks
- The faster O(1/n^2) rate requires sufficient over-parameterization to fit bounded label perturbations, and holds with high probability for sufficiently large networks trained by gradient descent under the stated assumptions.The paper’s numerical comparison also matches the O(1/n^2) pruning rate and O(1/n) gradient-descent rate.Source: §3.2 · p. 4, §3.3 · p. 5, Figure 2 · p. 5
3.4. Pruning Randomly Weighted Networks
- The O(1/n^2) bound also holds when the large network’s weights are drawn i.i.d. from the initialization distribution without pretraining.The result follows because the theorem applies at training time T = 0.Source: §3.4 · p. 5
3.5. Greedy Backward Elimination
- The analyzed backward-elimination counterpart lacks the forward method’s O(1/n) and O(1/n^2) rates, and forward selection outperforms it on ResNet34 and MobileNetV2 for ImageNet.The empirical comparison is reported in Appendix 11, Table 5.Source: §3.5 · p. 5
3.6. Further Discussion
- The theory analyzes two-layer networks and cannot characterize whether pruning finds good deep-network structure; its analysis also relies on the mean-field parameterization.The paper identifies generalizing the theory to deep networks and other parameterizations as future work.Source: §3.6 · pp. 5–6
- For practical pruning, the layer-wise algorithm selects neurons sequentially from input to output and then fine-tunes the resulting subnetwork.It starts from a pretrained network and adds neurons that yield the largest immediate loss decrease.Source: §3.6 · p. 6
4. Practical Algorithm and Experiments
The practical algorithm prunes deep networks layer by layer by greedily adding neurons, then fine-tunes the selected subnetwork from the original weights. On ImageNet, it improves on prior pruning results, while experiments also favor fine-tuning over retraining and pruning from larger source models.
4. Practical Algorithm and Experiments
- The greedy method sequentially prunes layers by adding neurons that most reduce loss, then fine-tunes the subnetwork from the original model’s weights.The process proceeds from input to output layers; fine-tuning uses the original weights as initialization.Source: §4 · p. 6
4.1. Finding Subnetworks on ImageNet
- The method consistently outperforms prior pruning methods on compact ImageNet models, including ResNet, MobileNetV2/V3, and ProxylessNet.On MobileNetV2, Figure 3 reports higher top-1 accuracy than other methods at every FLOPs level.Source: §4 · p. 6, Figure 3 · p. 6
- At 106M FLOPs, the method raises Meta Pruning’s top-1 accuracy from 65.0% to 66.9%.On MobileNetV3-Small, it improves 65.4% to 65.8% below 50M FLOPs; on ProxylessNet-Mobile, 72.9% to 74.0% below 240M FLOPs.Source: §4.1 · p. 8
4.2. Rethinking the Value of Finetuning
- For pruned MobileNetV2 models at 219M and 169M FLOPs, fine-tuning outperforms retraining; at 169M FLOPs, retraining decreases top-1 accuracy from 70.4% to 69.0%, demonstrating the importance of initializing pruned models with weights learned by the large model.Source: §4.2 · p. 8
4.3. On the Value of Pruning from Large Networks
- At 96M FLOPs, the pruned model from full-size MobileNetV2 reaches 66.2% top-1 accuracy, compared with 64.9% from MobileNetV2×0.5.The comparison uses pruned models with similar FLOPs from source networks of different sizes.Source: §4.3 · p. 8, Table 3 · p. 8
5. Related Works
The related-work discussion distinguishes greedy forward selection from backward elimination and other pruning strategies. It frames the approach as direct loss minimization over neurons in a pretrained network, with theoretical and practical contrasts to alternative frameworks.
Structured Pruning
- Structured pruning removes neurons, channels, or other units, and the proposed method directly minimizes final loss rather than using weight norms, reconstruction error, or sensitivity proxies.The paper contrasts structured pruning with weight pruning, which specifies network connectivity.Source: §5 · p. 8
Forward Selection vs. Backward Elimination
- Unlike backward elimination, forward selection grows a subnetwork; Zhuang et al. (2018) use a similar greedy channel strategy but optimize a gradient-based sensitivity measure and provide no theoretical guarantees.The proposed strategy instead selects neurons using the actual loss.Source: §5 · p. 9
Sampling-based Pruning
- Sampling-based pruning offers output-difference concentration bounds, while the paper claims greedy selection attains a faster O(1/n²) rate in overparameterized cases.The authors also distinguish their framework by justifying pruning from large models over direct gradient training.Source: §5 · p. 9
Frank-Wolfe Algorithm
- Frank-Wolfe neuron addition requires a challenging global optimization at each step; the proposed method restricts search to neurons in a pretrained overparameterized network.The paper argues this restriction gives an approximation to the original nonconvex problem.Source: §5 · p. 9
Sub-modular Optimization; Lottery Ticket; Re-train After Pruning
- The paper says its objective is not submodular, so weak-submodular analysis bounds comparison with size-n subnetworks rather than the best convex combination of all neurons.For lottery-ticket and retraining approaches, it distinguishes fine-tuning from pretrained weights from retraining with random or original-seed initialization.Source: §5 · p. 9
6. Conclusion
The paper proposes greedy selection to construct subnetworks from pretrained large networks. Its theory and experiments support pruning from overparameterized models and fine-tuning selected subnetworks, with improvements over prior pruning results on several architectures.
6. Conclusion
- Greedy selection constructs subnetworks from pretrained large models, and the paper reports theoretical support for pruning overparameterized models and empirical gains on ResNet-34 and MobileNetV2.The conclusion also emphasizes fine-tuning selected subnetworks rather than retraining them.Source: §6 · p. 9
7. Details for the Toy Example
The toy example compares greedy pruning with direct gradient-descent training on synthetic data. Its setup uses a large network for pruning and does not fine-tune the resulting subnetworks.
7. Details for the Toy Example
- Direct gradient-descent training of an n-neuron network has loss O(1/n + ε) with high probability, where ε is the mean-field-limit network’s loss at training time T.The cited analysis says that under regularity conditions this mean-field loss tends to zero as T increases.Source: §7 · p. 12
- The synthetic dataset has 100 training examples, with inputs sampled from a 10-dimensional standard Gaussian and labels generated by a neural network.The generator uses 1,000 units with Gaussian weights and biases sampled uniformly from −5 to 5.Source: §7 · p. 12
- The pruning setup uses a 1,000-neuron network, does not fine-tune pruned models, and trains all networks for the same sufficiently long time to converge..Source: §7 · p. 12
8. Finding Sub-Networks on CIFAR-10/100
The algorithm further compresses models already pruned by network slimming on CIFAR-10 and CIFAR-100, with little or no accuracy drop reported. The section illustrates this on pretrained VGG19 on CIFAR-10.
8. Finding Sub-Networks on CIFAR-10/100
- The experiments apply the algorithm to pretrained models already pruned by Liu et al. (2019b), then fine-tune them using the ImageNet experimental setting.Source: §8 · p. 12
- Pruning 44% of original VGG19 channels yielded 93.78% ± 0.16% accuracy on CIFAR-10, versus 93.81% ± 0.14% after Liu et al. (2017) pruned 30%.The authors describe the accuracies as almost the same.Source: §8 · p. 12
- Table 4 reports that on CIFAR-100 and CIFAR-10, the algorithm further prunes models pruned by Liu et al. (2017), without or with only little accuracy drop.For pretrained VGG19 on CIFAR-10, Liu et al. (2017) pruned 30% of channels with 93.81% ± 0.14% accuracy; the proposed algorithm pruned 44% of the original model with 93.78% ± 0.16%, nearly matching the strong baseline reported by Liu et al. (2019b). Reported numbers are averaged over five runs.Source: Table 4 · p. 12, §8 · p. 12
9. Discussion on Assumption 2 and 5
The discussion frames Assumptions 2 and 5 through whether the target vector lies inside marginal polytopes formed from feature maps. It notes that replacing interiority with relative interiority is a possible relaxation left for future work.
9. Discussion on Assumption 2 and 5
- For a dataset, each neuron’s feature map is its vector of scaled outputs, and the marginal polytope is the convex hull of those feature maps.The finite-network polytope uses the feature maps of its neurons.Source: §9 · p. 12
- Assumption 2 is equivalent to requiring the scaled target vector to lie in the interior of the finite network’s marginal polytope, with a positive-radius ball around it contained there.The discussion gives a corresponding ball-containment condition for Assumption 5 using M and γ*.Source: §9 · pp. 12–13
- The authors note that relative-interior conditions could relax the assumptions, but leave the required refined analysis for future work.Source: §9 · p. 13
10. Pruning Randomly Weighted Networks
The paper extends its theoretical analysis to greedy pruning of networks with randomly initialized weights. Under stated assumptions and sufficiently large networks, the result holds with high probability without further gradient-descent training.
10. Pruning Randomly Weighted Networks
- With i.i.d. weights drawn from an absolutely continuous, bounded-support distribution, greedy forward selection has the stated guarantee with probability at least 1 − δ when N is sufficiently large.The corollary assumes Assumptions 1, 5, and 6 for the initial weight distribution.Source: §10 · p. 13
- The randomly weighted-network result is the zero-training-time case of Theorem 3, so Assumption 4 is not needed for this corollary.Source: §10 · p. 13
11. Forward Selection is Better Than Backward Elimination
The comparison favors forward selection over backward elimination both empirically and theoretically. Forward selection keeps access to the full neuron set and can reuse neurons, whereas elimination’s candidate set shrinks and each neuron can be deleted only once.
11. Forward Selection is Better Than Backward Elimination
- Backward elimination’s search set shrinks at each step, while forward selection chooses from the full original set and may select a neuron repeatedly.Source: §11 · p. 13
- The authors report that backward elimination lacks forward selection’s O(1/n) or O(1/n^2) guarantees and give counterexamples to similar rates.Source: §11 · pp. 13–14
- Because backward elimination returns subnetworks in which each neuron appears at most once, its best achievable loss has a lower-bound disadvantage relative to forward selection, which can reuse neurons.Source: §11 · pp. 13–14
- A constructed instance has backward elimination’s loss bounded away from zero for n in [38], while forward selection reaches zero loss using two neurons.The forward-selection construction selects one feature four times and another once.Source: §11 · p. 14
- Forward selection tends to achieve better top-1 accuracy than backward elimination in all reported ResNet34 and MobileNetV2 ImageNet cases.Table 5 compares the two methods on ImageNet.Source: Table 5 · p. 15, §11 · p. 15
12. Proofs
The proofs use Frank–Wolfe updates to control the greedy algorithm’s error, while distinguishing its loss-minimizing selection from Frank–Wolfe’s linearized objective. The later proofs establish the stated results through high-probability approximation and boundedness arguments.
12.1. Proof of Proposition 1
- The greedy selection proof uses Frank–Wolfe updates to bound error, although the algorithm minimizes loss rather than Frank–Wolfe’s linear approximation.With step size ξ_k = 1/k, the target bound is ℓ(u_k) = O(1/k) + L*_N.Source: §12.1 · pp. 15–16
12.2. Proof of Theorem 2
- Under Assumption 2, the Theorem 2 proof targets ℓ(u_k) = O(1/(k max(1, γ))^2) by bounding an auxiliary sequence.The proof uses that the ball B(y, γ) is contained in M_N.Source: §12.2 · pp. 16–17
12.3. Proof of Theorem 3
- Theorem 3 follows from the preceding lemmas, including a high-probability result under Assumptions 1, 3, 4, 5, and 6.The lemma is stated for sufficiently large N and arbitrary δ > 0.Source: §12.3 · p. 18, §12.3.1 · p. 18
12.3.2. PROOF OF LEMMA 7
- Lemma 7’s proof argues that when M_N approximates M, it contains a smaller ball around y with high probability.The proof develops this from the assumption that M contains a ball centered at y.Source: §12.3.2 · p. 18
- The Lemma 7 proof reaches a contradiction by combining a supporting-hyperplane construction with a distance bound.It constructs E in the hyperplane and derives ∥B − E∥ ≥ ∥B − A′∥ > 1/(6γ*).Source: §12.3.2 · pp. 18–19
13. Technical Lemmas
The technical lemmas supply boundedness, sampling, and coupling results used in the proofs. They rely on finite-time bounds and high-probability statements as the network width grows.
13.1. Proof of Lemma 8
- For finite training time T, Lemma 8 bounds the neuron parameters, feature vectors, and feature Lipschitz constants by a finite constant.The proof says the bounds also hold for training a network with infinitely many neurons.Source: §13 · p. 19, §13.1 · p. 21
13.2. Proof of Lemma 9
- Lemma 9’s bound uses the VC dimension of the function class, which is at most d + 1.The proof states a uniform bound involving (4/N)(d_VC log 2N + log(8/δ)).Source: §13.2 · p. 21
13.3. Proof of Lemma 10
- The Lemma 10 proof chooses a radius with Cr_0 ≤ ε, then combines Assumption 6, Lemma 9, and Lemma 8 to establish its result.The argument applies for sufficiently large N with probability at least 1 − δ.Source: §13.3 · pp. 21–22
13.4. Proof of Lemma 11
- The Lemma 11 proof couples finite-network training dynamics with an infinite-width process and invokes propagation of chaos at finite T.It then combines that bound with Lemma 10 to obtain a high-probability result for sufficiently large N.Source: §13.4 · p. 22