When Are Neural Pruning Approximation Bounds Useful?
Authors: Mitchell A Gordon
Venue:  (2021)
Keywords: neural network
pruning
coreset
approximation

Abstract:    Approximation bounds for neural network pruning attempt to predict the trade-off between sparsity and fidelity while shrinking neural networks. In the first half of this paper, we empirically evaluate the predictive power of two recently proposed methods based on coreset algorithms. We identify several circumstances in which the bounds are loose or impractical to use and provide a brief analysis of the components of the bounds that contribute to those short-comings. In the second half, we examine the role of fine-tuning in prunability and observe that even tight approximation bounds would be poor predictors of accuracy after fine-tuning. This is because fine-tuning can recover large amounts of accuracy while simultaneously maintaining or increasing approximation error. We discuss the implications of these finding on the application of coreset-based pruning methods in practice and the role of approximation in the pruning community. Our code is available in the attached supplementary material.

Under review as a conference paper at ICLR 2021
WHEN ARE NEURAL PRUNING APPROXIMATION BOUNDS USEFUL?
Anonymous authors Paper under double-blind review
ABSTRACT
Approximation bounds for neural network pruning attempt to predict the trade- off between sparsity and fidelity while shrinking neural networks. In the first half of this paper, we empirically evaluate the predictive power of two recently proposed methods based on coreset algorithms. We identify several cireumstances in which the bounds are loose or impractical to use and provide brief analysis the
of the components of the bounds that contribute to those short-comings. second half, we examine the role of fine-tuning in prunability and observe that even tight approximation bounds would be poor predictors of accuracy after fine- tuning. This is because fine-tuning simultaneously maintaining or increasing approximation error. We discuss the implications of these finding on the application of coreset-based pruning methods in practice and the role of approximation in the pruning community. Our code is available the attached supplementary material.
recover large amounts of accuracy while
INTRODUCTION
Recent work has attempted to prune neural networks while providing a mathematical upper bound on the deviation from the original network. These bounds were first introduced as a component in proofs of generalization in statistical learning theory (Arora et al. (2018). Recent improvements on
these pruning methods have come from the field of randomized algorithms, leveraging the concept of coresets (Mussay al. 2020) (Baykal et al. 2019a (Baykal et al. (019b) (Liebenwein al.] 2019).
with empirical evaluations focusing on practical improvement in the sparsitylaccuracy trade-off.
However, surprisingly little attention has been given to evaluating the tightness of the proposed bounds or the predictive power of the guarantees they provide. the first half this paper, we fill this gap by empirically evaluating the tightness of two recently proposed coresct bounds, using them to predict the accuracy of neural networks after pruning. We conduct a series experiments of increasing difficulty, starting with networks that are known to be highly sparse and ending with networks in which no regularization is applied during training. We identify several circumstances in which the bounds are loose or impractical to and provide brief analysis of the bound compo- nents that contribute to those short-comings.
In the second half of the paper we introduce fine-tuning procedure after pruming, which is com- mon practice in the pruning community. Fine-tuning can drastically improve the accuracy achieved high levels of sparsity, taking some models from 40% accuracy after pruning to 98% accuracy after fine-tuning. However, we observe that this improvement does not usually include reduction in approximation eиror; indeed, fine-tuning can even increase approximation error in hidden lay- ers while simultaneously recovering the original performance of the network. We argue that this phenomenon limits the predictive power approximation bounds which are constructed "layer-by- layer" and which ignore the final softmax layer at the output. This motivates further discussion of the practical applications of soreset-based methods and whether "approximation" " is the correct goal for the pruning community.

---

Under review as a conference paper at ICLR 2021
2
RELATED WORK
Over-parameetrization A popular recipe for training neural networks is to make the network as large as possible such as to achieve 0 training loss, then regularize to encourage generalization (Karpathy] 2019). possible that such pver-parameterized networks have have favorable opti- mization properties (Li et al., 2020) (Du et al. (0188). However, parameterizzed networks are becoming increasingly burdensome to evaluate on consumer hardware, which has driven the inter- est in researching precise and effective pruning methods that can take advantage of sparsity in the discovered solutions.
Pruning With Guarantees Despite the massive literature on neural pruning techniques, few papers provide any kind of mathematical guarantee on the result of pruning. Besides the coreset methods which are discussed below, |Seraa et al. (2020) provide a method for "losslessly" compressing feed- forward neural networks by solving a mixed-integer linear program. They observe that applying LI regularization during training required achieve non-negligible lossless compression rates, which closely aligns with the observations in our work. Havasi et al.] (2018) provide an explicit compression/accuracy trade-off for Bayesian neural networks, but their compression method cannot be used to improve inference efficiency, only the memory needed to store the model.
Empirical Scaling Laws Frankel al. have observed that error after pruning can be empirically modeled as a function of network size, dataset size, and sparsity with good predictive results (Rosen- feld al. 2020). This can be seen more practical alternative formal guarantees on accurancy after pruning, where a few small-scale experiments are run to estimate the accuracy after pruning at larger scales.
CORESET APPROXIMATION BOUNDS
3.1 CORESET WEIGHT PRUNING
An algorithm from Baykal et al. (019b) for pruning the weights of single perceptron is presented in Algorithm|] [ it involves sampling from a distribution over weights, where the probability of being sampled roughly measures the weight's importance to maintaining the output. The algorithm keeps the selected weights (with some re- re-weighting) and prunes the rest. The resulting pruned perceptron is guaranteed to output values that are arbitrarily close to the original perceptron if sufficiently large number of samples is taken. The relationship between the closeness of the approximation and number of samples reguired is given by Theorem A..] Further details and required assumptions provided in Appendix [.1] The method can be used to sparsify a whole layer by sparsifying each
neuron individually, and bounds for pruning multi-layer neural networks can be constructed using "layer-by-layer" approach, which is discussed in Section 5.2
Deterministic Weight Pruning [aakkl al. (2019b) also present a deterministic version of their algorithm, which selects the weights with the lowest importances for pruning. This alternative algo- rithm is presented in Algorithm (aan and the corresponding guaranteed approximation error is presented in Theorem A.2 the proof of which is based on the probabalistic proof of Theorem A.
3.2 CORESET NEURON PRUNING
Whole neurons can be pruned rather than individual weights. In this case, importances are assigned to each neuron, creating probability distribution that can be sampled from. A method from Mussay et al. (2000) for pruning feed-forward neural networks with single hidden layer is shown in Algo- rithm 3 This algorithm data--ndependent:: it ignores the training data and instead only assumes that the inputs have bounded L2 norm. Neuron importance is determined by the L2 norm of the parameters of each neuron and the magnitude of the weights assigned to them in the next layer.
Similar to weight pruning, the approximation error can be bounded above depending the number of samples taken from the distribution over neurons. The relationship is expressed in Theorem Notice that unlike the mulriplicative approximation bound provided for weight pruning, this bound is an additive error bound, meaning that the guaranteed error term is constant, regardless of the seale of the "true" value. More details about this method are provided in Appendix A.3
2

---

Under review as a conference paper at ICLR 2021
Guaranteed Label- Consistency
Label May Change
51
max 92
min
(c)-Approx
((0++--Aprrx
Prunc
A-Aproxx
Prune
1/1 82
Figure 1: (Left) An illustration of how additive approximation bound can be used to guarantee label con- sistency. If each pre-softmax logit can only change by c, then is impossible for second- -lagest logit to surpass the largest logit under pertubation. However, the label may change if each logit can change by c', which is more than half the distance between them. (Right) In the laycr-by-layer approach, we start by pruning the "first" layer (which is closest to the input) with some approximation guarantee activations. This epsilon error can be "bubbled up" to the output for implied approximation guarantee on the output g(c). We proceed prune second hidden layer given the pruned first layer activations as input, again noting the guaranteed approximation error 3 and bubbling up to the output. This is repeated for each layer, accumulating approximation error for the deviations in each hidden layer.
the first layer hidden
3.3 EPSILON- -IRSIT AND SPARSITY-FIRST PRUNING
Pruning using randomized coreset methods involves sampling from distribution over weights or neurons. The number of samples taken can be determined in one of two ways, depending on whether there is strict requirement on approximation error on sparsity:
The number of samples determined by the desired epsilon guarantee on the output. Samples are taken with replacement, and sparsity is determined by the number of unique samples.
Epsilon-first:
Sparsity-fistt: Sample from the network until the number of unique samples equals the desired sparsity. Work backwards to infer the epsilon guarantee given that number of samples.
Each approach has its drawbacks. While epsilon-first pruning guarantees certain accuracy af- ter pruning, it cannot guarantee the sparsity achieved since sampling is done with replacement. Sparsity-first pruning, on the other hand, not guaranteed to terminate. For example, in the "easy case" experiments in the next section, it will be impossible for the algorithm to achieve 50% sparsity since less than 50% elements have non-zero probability of being sampled, which will cause the algorithm to run forever
We will use both approaches this work, preferring sparsity-fisst pruning when we must achieve a specific sparsity and preferring epsilon-first first pruning when familiar with what "reasonable" amount of approximation error looks like, which we discuss in the next section.
EVALUATING APPROXIMATION GUARANTEES
4.1 ACCURACY GUARANTEES
One obstacle to evaluating approximation guarantees is that it is difficult to determine what consti- tutes a reasonable amount approximation error. Our solution predict how many development set labels are guaranteed to remain correct and how many might flip to an incorrect label during pruning. This provides a more intuitive sense of the implications of the approximation bound.
use approximation bounds to
In order to convert an approximation bound into an accuracy guarantee, we must determine whether the output error is large enough to change the prediction of the neural network. Note that the pre- dicted label of a neural network which performs classification is simply the index of the largest
'The deterministic weight pruning algorithm can be implemented in a sparsity- first or epsilon first way. In both, we prune the weights with the lowest sensitivities first. The stopping condition can depend either on the desired sparsity or the desired epsilon approximation guarantee, which we call sparsity- first and epsilon first pruning, respectively. Unlike the randomized methods, the deterministic method of pruning does not have the associated drawbacks.
3

---

Under review as a conference paper at ICLR 2021
pre-softmax logit Whether the maximum logit will stay the maximum under some pertubation will depend on the distance between the maximum output logit and the second-larges output logit, which varies for each example in the development dataset. This is illustrated in Figure I and made precise in the following lemma:
Lemma 4.1 Let f: X' + y be neural network and x E X be an arbitrary input. Let denote the index of the largest pre-softmax logit, j = arg max; f()); Further, let j' denote the second largest pre-softmax logit f(r) 2 f()), # j. Finally, let f be an approximation of S. with guaranteed element-wise approximation error bound c. If the guarantee additive, then
c f(z);- - f(x)) = arg f(x); = arg max fxx);
2
If the bound is multiplicative, then
f(x), f(z),-((x) [)(z), + 15(x))p1
= argmax f(x), = arg max f(x);
This relationship allows us to determine the epsilon approximation bound that corresponds to some accuracy guarantee after pruning. For example, suppose we want to guarantee 95% of correct labels will stay correct. We would compute the pre-softmax logits of the original neural network on the development set, calculating the epsilon bound required to maintain each correct label. We would then select final epsilon value which is smaller than 95% of the values computed and prune to achieve that bound.
4.2 EASY, MODERATE, AND DIFFICULT CASES
To begin our evaluation, we start with the simplest circumstances: we prune only the final layer of LeNet300-100, small, two-layer feed-forward neural network trained to solve MNIST. We vary the training procedure to make easier or harder to prune the network while maintaining low ap- proximation error. More details about each of these cases can be found in Appendix B
Pre-pruned Neural Networks In the easiest case, we pre-prune the neural network to a high sparsity (95% for weight pruning and 90% for neuron pruning) using non-coreset-based heuristic methods and then re-train the network to re-gain all lost accuracy. We then re-initialize the pruned connec- tions to zero. The resulting network is known to be sparse and highly prunable while incurring approximation eтror. We should hope that coreset- based pruning methods will easily prune to the known sparsity while guaranteeing low amounts of approximation error.
Some Regularization In the more realistic moderate case, we apply mild L1 regularization (aka Lasso) during the training of the neural network. We set the I.1 regularizing penalty 0.001, which is the highest setting we could use which did not decrease development accuracy
No Regularization In the hardest case, we do not regularize the network. We expect this model to be the least amenable to approximation, and expect the coreset-based methods to appropriately predict that the network cannot be pruned. All models are trained to 98% development accuracy.
4.3 REPORT CARD: EPSILON-FIRST PRUNING
Figure shows the results for epsilon-first pruning the final layer of LeNer-300-100 100 under various training cireumstances, guaranteeing that 50% of the development set labels that correct will remain correct. The full results of these experiments, evaluated at different percentages of accuracy guarantees be found in Figure 6 As expected, all methods easily achieve high amounts of sparsity in the pre-pruned "easy" case. In the moderate case, less sparsity can be achieved, and in
the pre-softmax outputs. For neuron pruning, might suspect that dropout would be better choice than LI regularization to encourage prunability. However, this was not the case in our experiments. We discuss possible explanations and detail experiments in Appendix B.2
arg max; [softmax(f (f:))) arg max, f()),, where f(x)
4

---

Under review as a conference paper at ICLR 2021
Prune
Required Bound
Observed
Layer Size
Model Type
Case
Acc
Samples
Sparsity
Type
TcNNet
Wt Rnd
Fasy
0.46
0.04+-0.18 18
0.98
TK
271K
94.06
Mod
0,46
0.02-10.11
0.98
IK
IM
19.90
Diff
0.49
0.03-10.18
0.98
IK
1M
0.00
Wt Det
Easy
0,46
0.00-10.00
0.98
IK
94.06
Mod
0.46
0.01=00004
0.98
IK
657
34.95
Diff
0.49
0.01=0004
0.98
IK
927
8.22
Neuron
Easy
5.69
0.06=0.05
0.98
100
62K
90.00
Mod
3.30
0.04
0.98
100
97K
16.00
Diff
5.20
0.13:10.09
0.98
114K
0.00
VGG-16
Wt Rnd
Easy
0.31
0.01
0.93
10K
88K
98.90
Mod
0.52
0.04=0.11
0.92
10K
79K
91.19
Diff
0.58
0.04:10.22
0.92
10K
1.IM
2.84
Neuron
Easy
8,45
0.03++0.02
0.93
613K
99.00
Mod
6.63
0.01+00.03
0.92
IK
501K
95.00
Diff
8.17
0,00
0.92
1K
5.5M
0.00
Above the results for epsilon-first pruning the final layer of LeNet-300- 1000-000 and VGG-16 under various training circumstances (Section 4.2). guaranteeing that 50% correct will remain correct. We show the calculated epsilon bounds (multiplicative or additive) required to guarantee 50% accuracy (Section 4.11 along with the actual observed approximation error, average and standard deviation. We also show the layer size (number of neurons number of weights) well the number of samples required by the thcorem to meet the epsilon bound. Note that the sparsity may be different than the number of samples required, since sampling is done with replacement.
Figure 2:
development set labels that are
the difficult case almost no pruning can be done. However, we note some practical issues with the performance of these methods:
High Sample Complexity We can see (highlighted in red) that the number of samples required during pruning is unnecessarily high. Even in the easy case, in which we know the network is already sparse, the number of samples required is three orders of magnitude larger than the number of elements to sample from. We still able achieve some sparsity in the easy and moderate cases, however, since the probability distribution over weights and neurons is highly skewed. High sample complexity (< IM samples) can easily be handled by consumer hardware, but may grow impractical as the layers grow larger.
We also note that the observed approximation error is much lower than the provided bound (highlighted in orange). We guaranteed only 50% of the accuracy should be maintained, but cases 100% of the accuracy was maintained. The looseness of the bounds implies that much higher sparsities could be reached while still achieving the desired accuracy guarantee. Indeed, Figure shows that even the "difficult" case neural network can be pruned up to 90% sparsity before reaching 50% accuracy, whereas our best method only reached 8% sparsity. For neuron pruning, might suppose that the looseness bounds can be explained by laxness of the data-independence assumption. We explore this idea in Appendix C.1 but fail conclude that lax data assumptions are a sufficient cause loose bounds.
Loose Bounds
The deterministic version of weight pruning, while still providing significantly loose bounds, side- steps the sample complexity issue by not requiring any random sampling (highlighted in green). In opinion, this is the most promising future for these methods, which may leverage the benefits of probabalistic proof techniques while minimizing their drawbacks via de-randomization. However, none of these methods provide approximation bounds which are fine-graine enough predict the sparsity/accuracy trade-off. which we expect to become a theme of future work.
4.3.1 SPARSITY-FIRST PRUNING
The high sample complexity of epsilon-first pruning implies that sparsity-first pruning with random- ized methods will lead to incredibly vacuous approximation bounds. This is because the number of samples taken is usually less than the number of elements be sampled from. And indeed, Figure X shows that pruning a "moderate case" network at weight sparsities greater 35% lead to bounds that cannot guarantee any accuracy at all. Pruning at less that this sparsity causes the algorithm to
5

---

Under review as a conference paper at ICLR 2021
run forever. Sparsity-firs first pruning with deterministic weight pruning is easier to work with, but still under-estimates the achieved accuracy after pruning due to loose bounds.
4.3.2 WHAT DRIVES SAMPLE COMPLEXITY?
Two main components in each theorem drive sample complexity: the tightness of the epsilon bound and the "total sensitivity" of the layer. Sensitivity a measure of importance, so all neurons or weights are equally important then we will require large number of samples to achieve a good approximation. only few weights are important, then total sensitivity will be small and we will require fewer samples.
In the case of weight pruning, sample complexity scales linearly with total sensitivity, and the slope of the line is determined by the required epsilon bound and the probability of failure For LeNet, layers tend to have a relatively low total sensitivity (only 5% of the possible maximum). Even at the minimum total sensitivity, however, Theorem A. would require sampling 1.5x the number of weights for each perceptron. This seems to imply that sample complexity's quadratic dependence on epsilon is too restrictive for neural networks of the size typically deployed in practice, and that future work should focus on relaxing that dependence.
For neuron pruning in Theorem A.4, the sensitivity of each neuron is function of the norm of the inputs and the norm of the weights of each neuron. This leads us to Corollary C.2 which says that we can arbitrarily increase or decrease the sample complexity of any accuracy guarantee by scaling the appropriate weight matrices by a constant factor. We prove this using the positive homogeneity property of ReLU networks (Du al., 2018a o and verify it empirically investigating the full implications of this observation are out of the scope of this paper
Appendix C.2 However,
4.3.3 SCALING UP To LARGER NETWORKS
We might expect that results would be more compelling larger neural networks trained more realistic data, since coreset algorithms were originally applied to big-data streaming applications in which millions of elements are sampled from. To test this, we repeat the experiments above on a VGG-16 model trained to 92% development accuracy on CIFAR-10, 10, which has 10x the number of neurons in the previous experiments. We find that these models are more prunable via heuristic methods than LeNet; we can achieve 99% weight and neuron sparsity without decreasing accuracy.
The results for coreset-based methods, however, are qualitatively similar to earlier experiments (Fig- urd Appendix B.3). While the number of neurons has increased by 10x, so too has the number of samples required by deterministic weight pruning and randomized neuron pruning. Bounds are similarly loose for all methods. The relative increase in weight pruning sample complexity, however, much less than 10x (highlighted in blue), which we believe reflects the increased prunability of these models. This may imply that coreset-based methods may give non-vacuous sampling com- plexities for very large and very sparse layers. However, the scale required (10k+ hidden units) does not seem to overlap with sizes typically used in practice.
FINE-TUNING DOES NOT APPROXIMATE
In the sections above, we have only evaluated networks immediately after pruning, without any fine- tuning allowed. However, fine-tuning is an integral step in the pruning process. This is illustrated in Figure 3 in which we prune a "difficult case" neural network to 95% weight sparsity using a sparsity-first coreset method. Accuracy drops to below 40% after pruning. but recovers to 98% after fine-tuning, We call this discrepancy between accuracy before and after fine-tuning the "fine-tuning gap." While approximation bounds may improve accuracy prediction after pruning by tightening bounds, we will see in the following sections that they have no hope of predicting the size of the
We can determine the number of samples required by solving for m terms of e, see Corollary 5 of Baykal ct al. 2019b).
In ReL. networks, positive homogeneity means that multiplying weight matrix by a constant multiplies the pre-softmax output by the same factor. This "decreases the temperature" the softmax distribution. This scaling trick cannot be applied to Theorem A.1 for weight pruning, since the sensitivities and epsilon bounds scale-invariant.

---

Under review as a conference paper at ICLR 2021
Deterministic Weight Pruning LeNet-300-100
Accuracy
Approximation Error
1.0
80
Post Prune Approx Err
Post rinettuee Approx Err
0.8
Approximation Error
60
Accuray
0.6
30
Fine-tuning increases
Gap
80
Approx Error
0.4
30
0.2
Guara iteed Mccuracy
20
Post Accuracy
Post Finettue Accuracy
0.0
0.4 Sparsity
0.6
0.8
0.2
0.4
Sparsity
Figure 3: (Left) The results of pruning the final layer of "difficult case" LeNet-300- 100 with sparsity-fin first deterministic weight pruning. The provided accuracy guarantees vastly under-estimate the accuracy after prun- ing, which can attributed to loose bounds. Fine-tuning increases accuracy after pruning by more than 50%, which we call the fine-tuning gap. (Middle) Fine-tuning increases approximation error the pre-softmax logits rather than decrease it. This implies that approximation hounds would not be good predictor of the size of the fine-tuning gap. (Right) An illustration of softmax translation invariance, where = y C. Both pre-softmax activations lead exactly the same probability distribution over classes, since the output of softmax depends only on the difference between logits, not their magnitude.
fine-tuning gap while in their current form. This is because fine-tuning allows to recover accuracy while simultancously maintaining or increasing the approximation error measured by these bounds.
5.1 SOFTMAX TRANSLATION INVARIANCE
First, the methods described above measure approximation error before the softmax layer is applied. However, the softmax layer is translation invariant, which means that adding constant C' each pre-softmax logit will not change the output distribution. This is illustrated in Figure 3 (Right). This means gradient descent during fine-tuning will not have any incentive to reduce pre-softmax approximation error, but instead will be driven to adjust each logit locally with respect to the other logits the output. This is true both when the pruned network fine-tuned on the training data and when it is trained using knowledge distillation (Hinton et al. 2015).
This can be observed in Figure 3 which also shows the approximation error before and after fine- tuning the training data for "difficult case" network pruned using deterministic sparsity-firs: weight pruning. Although accuracy recovers from 30% to 98%, the pre-softmax approximation error increases stays the same after fine-tuning. Given the fragile relationship between accuracy and pre-softmax approximation error, we can expect methods which rely on such approximation bounds to be poor predictors of performance after fine-tuning.
5.2 LAYER-BY-LAYER BOUNDS
"layer-by-layer" approach may be used to prune multi-layer neural networks with approximation guarantees, as illustrated in Figure While layer-by-layer construction of approximation bounds is conceptually simpler and amenable to proof than working with the network as a whole, it requires that the pruned neural network approximate the original dense network at each hidden layer. If the approximation error at any intermediate layer is large, it "bubbles up" and greatly increases the approximation eиror at the output.
In practice, however, fine-tuning allows for later layers to compensate for large amounts of approx- imation error in layers close to the input. Consider the table below: prune the first layer of "difficult case" neural network to a high sparsity and observe the resulting approximation error in both the first hidden layer and the output. We then fine-tur the model approximate the original network's 's pre-softmax output activations, as in patient knowledge distillation (Sun et al. 2019
Athhouhh fine-tuning has incentive to approximate the original dense network's pre-softmax activations, we may artificially induce this behavior by explicitly minimizing the pre-softmax approximation during

---

Under review as a conference paper at ICLR 2021
Prune Type
Prune
Output
Hidden
Post-KD
Output
Hidden
Model
Prune
Acc
Error
Error
Acc
Error
Error
LeNet
Neuron
0.90
0,4809
6.78+:568
1,22+ 1.08
0.9513
2.95+22.3
1.72+1.44
Wt Det
0.95
0.773
1.3715.11
1,90=4.89
0.9762
0.71
1.96=5.10
VGG-16
Wt Det
0.99
0.2474
1.5115544
2.0515.57
0.92
0.8710.39
2.04
This process indeed reduces the pre-softmax approximation error of the pruned network and re- covers most of the development accuracy. However, the approximation enror in the hidden layer remains the same or increases (highlighted in red). This means that any layer-by-layer approxima- tion bound will be "bottlenecked" by this hidden error, even though the pruned neural network has low approximation error when considered as a whole.
5.3 PRUNABLE f APPROXIMABLE
The results of the previous sections highlights a subtle distinction between layers that are easy to approximate and layers which are prunable. Pruning layer may introduce large amount of ap- proximation error. If the layer is near the output, then the network may still output the correct labels by exploiting the translation invariance of softmax. If the layer near the input, then later layers may adapt to the approximation error by adjusting their weights. In the next section, we discuss the implications of this distinction on future work on pruning with approximation bounds.
5.4 WHEN ARE APPROXIMATION BOUNDS USEFUL?
Pruning Efficacy Given the subtle distinction between prunable and approximable networks, is not clear whether pruning methods which directly attempt to approximate the original neural network should be able to prune more effectively in terms of the development accuracy / sparsity trade-off. While Mussay al. (2020) do not compare to any heuristic methods after re-training, Baykal et al. (2019b) find only small improvements (1-2%) in development accuracy over magnitude weight pruning at the highest levels of sparsity
out the scope of this paper to evaluate these claims, since we are mainly concerned with the predictive power of these methods and the guarantees they provide. However, it is possible that minimizing approximation error improves the ability of gradient descent to find "other" global optima that are nearby. This would make sense in light of mode-connectiving (Garipov al.) 2018), which observes that neural networks may have many global optima connected by simple linear paths. However, a more rigorous analysis is required provide motivation and quantitative prediction of the benefits of approximation
Optimal Layer Sparsity Another claimed benefit of good approximation bounds is the ability to correctly predict the appropriate sparsity for each hidden layer or neuron, without having to empiri- cally test every possible sparsity combination. This done in Baakkal optimzation method to minimize the sum of the errors in each layer. However, we have observed that different layers can tolerate different amounts of approximation error due to the ability of later layers to compensate during fine-tuning. We believe it is unlikely that approximation error theory by itself will allow for useful predictions about optimal sparsity; optimizability of sparse networks dur-
(2019b) using a convex
gradient descent, which is similar in spirit to knowledge distillation (Hinton et al. 2015). However, training non-trivial due exploding gradients caused by the large difference in scale between pruned and original activations. Normalizing the activations by their 1.2-norm before calculating the loss can mitigate this, allows for inexact approximation during fine-tuning.
"It should he noted, however, that there is crisis in evaluating neural pruning methods, since the results notoriously difficult replicate (Blalock et al. (2020) (Gale al. 2019 Any claims that one pruning method "better" than another should be carefully evaluated. We should also take into consideration the complexity required to execute the methods. In terms of the ratio of performance to simplicity. we believe magnitude pruning and re-training remains paralleled.
"This might benefit from an extension of (Du et al. 2018b), which predicts the circumstances in which gradient descent will find a global optimum, the case of sparse training. An analysis might also benefit from the observation that re-winding the weights to initialization before fine-tuning can sometimes lead to hetter performance (Renda et al. 2020).
8

---

Under review as a conference paper at ICLR 2021
ing fine-tuning must be taken into account. It may also be the case that deviating from the original network may be a desirable characteristic, as the new optimum may be more generalizable.
Generalization Pruning approximation bounds were made recently popular by their application to proof's of generalization, and that is likely where they will remain useful. However, proof' of generalization which employ loose approximation bounds will likely result in loose generalization bounds, and so care should be taken by the consumer of these theorems.
CONCLUSION
There is still work to be done in order make neural pruning approximation bounds both practical and correct. Current methods tend to over-estimate the approximation error that will be observed in practice, and randomized methods require an impractical number of samples to be taken during pruning, limiting the sparsity that can be achieved while guaranteeing fidelity. There are a number of avenues to improve these short-comings, including focusing on derandomization, taking into ac- count the positive homogeneity of neural networks, and only applying coreset methods to networks of an appropriate scale.
However, while these improvements may tighten approximation bounds, they will still not be practi- cally predictive of performance unless they take into account the invariance of the softmax layer and accompanied by an analysis of the fine-tuning process. Both of these facets of neural network training allow pruned networks to accrue high amounts of approximation error in hidden layers while maintaining label-consistency with the original dense networks. Predicting the outcome of pruning and re-training, which an indispensible step in all effective pruning methods, will require more sophisticated analysis of the optimization of sparse neural networks via gradient descent.
REFERENCES
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. ICML, pp. 263, 2018. URI. http:
//proceedings .wl.engsmmlrr......rr pwwss/r.esssvvvse ppreess/880/rrraaBhbb html
aroral8b.
Cenk Baykal, Lucas Liebenwein, Igor Gilitschenski, Dan Feldman, and Daniela Rus. Data- dependent coresets for compressing neural networks with applications to generalization bounds. In International Conference on Learning Representations, 2019a. URL https:
net/ http://wweee/rrommmo//oadueaEaad
Cenk Baykal, Lucas Liebenwein, Igor Gilitschenski, Dan Feldman, and Daniela Rus. SiPPing neural networks: Sensitivity- informed provable pruning of neural networks. October 2019b.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? March 2020.
Simon Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Resa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 384-395. Curran Associates, Inc., 2018a.
Simon S. Du Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. CORR, (bb//811100880 20. /ttp:tttp///axxi... /rrg
Abs/1811 03804
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. February 2019.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling dnns. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems 31, pp. 8789- httpps..ccpppp/////
8798. Curran Associates, Inc., 2018. URL http::/ cersssuurfccssssmee mode- www.ectiiinn-eaeeeeeoeoo fast aa-t-aaaan-----t----eeaenninn---
pdf

---

Under review as a conference paper at ICLR 2021
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections
for efficient neural network. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems 28, pp. 1135- 1143. Curran Associates, Inc., 2015. URL http:://aapers.nissscc///e 1ed--eennin--ottheee. pdf
and-
network.
Marton Havasi, Robert Peharz, and José Miguel Hermánee--Loatoo Minimal random code learning: Getting bits back from compressed model parameters. September 2018.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. March 2015.
Andrej Karpathy, A recipe for training neural networks. https:/kkarpttty.githbbb io/
201 2019/04/25/rrs recps///eeppe/ee 2019.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes, 2014.
Zhuohan Li, Eric Wallace, Sheng Shen, Kevin Lin, Kurt Keutzer, Dan Klein, and Joseph E Gon- zalez. Train large, then compress: Rethinking model size for efficient training and inference of transformers. February 2020.
Lucas Liebenwein, Cenk Baykal, Harry Lang, Dan Feldman, and Daniela Rus. Provable filter pruming for efficient neural networks. ICLR 2020, 2019.
Christos Louizos, Max Welling, and Diederik P Kingma. Learning sparse neural networks through Lo regularization. December 2017.
Chris Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables, 2017.
Poorya Mianjy and Raman Arora. On dropout and nuclear norm regularization. volume 97 of Pro- ceedings of Machine Learning Research, pp. 4575-4584, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL
mllr. prwss/eessseee.. http://///m/a//nmmmm/ html
Ben Mussay, Margarita Osadchy, Vladimir Braverman, Samson Zhou, and Dan Feldman. Data- independent neural pruning via coresets. In International Conference Learming Representa- tions, 2020. URL
wwwprrreeeeieeeeefoouueeee -d-H1ll gmHaaKWW
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. March 2020.
Jonathan S. Rosenfeld, Jonathan Frankle, Michael Carbin, and Nir Shavit. On the predictability of pruning across scales, 2020.
Thiago Serra, Abhinav Kumar, and Srikumar Ramalingam. Lossless compression of deep neural networks. January 2020.
Siqi Sun, Yu Cheng, Zhe Gan, and Jingjing Liu. Patient knowledge distillation for BERT model compression. In Proceedings of the 2019 Conference on Empirical Methods in Natural Lan- guage Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 4314 4323, Stroudsburg, PA, USA, 2019, Association for Computational Linguistics.
A CORESET METHOD DETAILS
A.1 NOTATION
We are interested pruning feed-forward neural network with T. E N4 layers which defines a mapping f : X 2 y for an input X C dd to an output y E y C R Borrowing the notation of Baykal et al. (2019a), let (t()) E N_ denote the number of neurons in layer E [L], where [7] (1....,4, T.} denotes the index set. Note (1) d and rT(L) k. Further, let 1 "t
10

---

Under review as a conference paper at ICLR 2021
Algorithm/ 1: Randomized Coreset-based Weight Pruning of Single Neuron
Input: indices of non non-neganee -on-negatvve parameters; w: neuron parameters to sparsify; m: number of parameters to sample; S C P: batch of validation points; K: constant from Asm. A.3
Output: W: sparse weight tensor
2,3; 8j < maxxES Exer WanE Vij E I (Compute parameter importances]
= =83/Ekeri>e EI
K MULTINOMIAL.g,.
for
j do
K, (Re-weight entries to ensure unbiasedness of estimator } mqg
end
return Wi;
Algorithm 2: Deterministic Coreset-based Weight Pruning of Single Neuron
Input: indices of non non-negatis nnnneetaive parameters; w: neuron parameters to sparsify; m: number of parameters to sample; S C P: batch of validation points; K: constant from Asm. A.3)
Output: w: sparse weight tensor
Wy3, 8j <- maxzes Σxer waze Vj E I (Compute parameter importances]
I.m +- indices of the m largest values of (sj)jez where ties are broken arbitrarily;
for j Imm do
ú < Wy
end
return di;
Algorithm 3: Coreset-based Neuron Pruning of Single Hidden Layer
Input:
W E |Tnl)) xd, weights of hidden layer; W/(2) E ( weights of output layer; m: number of neurons sample; O: an upper bound on the L2 norm of the input values. Output: ((();; pruned hidden layer; (2); new weights for output layer.
max ui? 0(8) [( (D)
4j Σ Ey max4e(M) w ( Vjj E [n] {Compute neuron importances)
K MULTINOMIAL m);
for j [ do
ifK # then
wj (1)
K (2)
Vi E [k]
w
mgg
end else
10
Vi E [k]
w
5- 0
11 end
end
13 return (1) (2))
Figure 4: (Top, Middle) Algorithms from Baykal et al. (2019b) for pruming a single perceptron with positive weights via data-dependent coresct method. (Bottom) Algorithm from Mussay et al. (2020) for pruning single hidden-layer feed-forward neural network data-independent coreset method.
11

---

Under review as a conference paper at ICLR 2021
For each layer E (2....,L}, L). let W(O E xxn be the weight matrix for layer & with entries denoted by wiy and rows denoted by ws E RRix' For notational simplicity, we assume that the bias is embedded in the weight matrix. Finally, let p' nnz(W(()) be the number of parameters in the matrix ((O) and p² maX) p². We consider the activation to be the Rectified Linear Unit (RcLU) function, i.e., ((-) m f..x If the network is used for classification task, then the predicted label is arg max; [softmax (f [z)): = arg max; (a))):
A.2 WEIGHT PRUNING
When sparsifying weights with coreset-based methods, we guarantee that the output of the pruned perceptron is arbitrarily close to the original a sufficient number of samples taken. A bound on the approximation error given certain number of samples is presented in the following theorem:
Theorem A.1 Baykal et al. 2019b) Let K, K' E Th be constants that can be determined from Assumption A.3 Let I indicate the indices of the non-negative weights of the perceptron. For e (0, 1), invoking Alg I with m e N satisfying m > S, and a set S X composed of [ log(2p/8) i..d points drawn from D generates a perceptron iú such that nmz( ()) S m and for some x ~ D,
Pr([a(x) 2(x) cm² 8
where z(x) = EKET WKT 2(x) = EKET W.
$ m
(
$
$ m
6m
E (0.
m
$ = log(4/6), and S Ejer 8j
The theorem provides probabilistic guarantee, meaning our confidence that the guarantee will hold can be adjusted via a parameter Note that this result holds only when the weights of the neural network are positive. A generalization to all weights is given by Lemma of Baykal et al. (2019b). This involves sparsifying the positive and negative weights separately and then combining the results, which is how we implement this method for our experiments.
our experiments, we use 8 0.5 unless otherwise specified.
Baykal et al. (2019b) also present a deterministic version of their algorithm, which prunes the lowest- sensitivity weights first. The approximation error can also be bounded in this case using the follow- ing theorem:
Theorem A.2 (Baykal et al. 2019b) In the context of Theorem A.1 invoking Algorithm 2 generates perceptron w such that for some x ~ D.
8 Pr(( - 2 (m)(2)) S 2
where 2(x) Ekez WoT 2(x) Ekez WK and cm 3K ΣjE(ZYZ.,) $j
The proof of both weight pruning approximation bounds requires an assumption on the Cumulative Distribution Function (CDF) of the sensitivities of each weight. For our work, we use values of K' = 3 and K 2 which are recommended by the authors.
Assumption A.3 (aykal al. (019b)) Let 95(x) w/xz// ExET WKTK. for D. There exist universal constants K, K" >> O such that for all I. the CDF of the random variable g(x), for I ~ D. denoted by F,(.), satisfies F, K) & exp(-1/K'), where M, = min(y E [0, Fy(y) 1).
12

---

Under review as a conference paper at ICLR 2021
A.3 NEURON PRUNING
Neurons can be pruned rather than weights via Algorithm 3 A bound on the approximation error of the pruned neural network can be guaranteed if sufficient number of samples taken. This is expressed in the following theorem:
Theorem A.4 Mussay et al. (2020) Let W()) E Rr xd be the weights of the hidden layer and ( Rkxn be the weights of the output layer, and 3 be an upper bound on the L2-norm of I E X. as in Alg 3
Let
(2) 3j = max Wi ( (12)
[k(
be the sensitivities of each neuron for jj E (,) and = E, be the "total sensitivity. Let e >> 1 be a sufficiently large constant that can be determined from from the proof, and
at ( dlogt log e²
)))
111
1
m
be the sample size. Let W(),, (2) be the output call to Algorithm 3 Then, with probability at least 1 6,
Vi [k]. x Bo(0):
Σ |ED
(2) w ( x)
" o JEIn
E
x) SE
Se
To avoid the confusion introducing new notation, we have re-written this theorem using the no- tation used in Baykal et al.) (2019)). We also do not mention VC-dimension in this theorem, which needed for the general case. our case, the VC-dimension of single perceptron with ReLU activation is simply the input dimension, d.
Neuron pruning approximation bounds require knowing the maximum 1.2 norm of the input vectors. This be calculated naively; for example, MNIST has 784 input dimensions each within (0, 1). Then the maximum L2 norm is v784 28; could then bound the L2 norm of hidden activations by examining the eigenvalues of each weight matrix. In practice. however, MNIST has highly sparse inputs and observe the maximum L2 norm to be 25. this case, we set be the lower value and follow a similar empirical approach to estimate the appropriate maximum L2 norm of hidden activations.
B EXPERIMENTAL DETAILS
B.1 LENET TRAINING DETAILS
LeNet-300-100 is a simple two-layer feed-forward neural network with 300 hidden units the first layer and 100 hidden units in the second layer. All LeNet-300- 100 models are trained to achieve 98% development accuracy on MNIST. Training carried out 10 epochs with standard SGD optimizer at learning rate 0. momentum 0.5, and training batch size of 100.
Easy Case There are two "easy case" LeNet models, one which pre-prunes the neurons of the final hidden layer and one which pre- pre-prunes the weights of the final weight matrix. Weight pruning is done via magntiude weight thresholding (Han et al. 2015), which is the most popular form weight pruning.
Neuron pruning is accomplished via LO regularization, which adds a penalty to the loss function of neural network depending the number of neurons with non-zero weights (the L0-norm of the neurons). This loss function is computationally intractable to optimize exactly, but in practice can be optimized via stochastic relaxation (Louizos et al. 2017). In this method, each neuron multiplied
13

---

Under review as a conference paper at ICLR 2021
Leket 300-100 LO Proning Dey Asa
LeWell 500 100 Mega Miggrituule Pruring Dev Ass
0.4
0.0
Da De
0.1
07-
0.6
04-
Pos:-ruuM
Pail-rune
Pesc/tssture
Past-Pasdiun
0.
0.7
Spersity
spansiy
Figure 5: The development accuracy of LeNet-300-100 models after pruning the final layer using heuristic methods and also after fine-tuning. On the left is neuron pruning via LO regularization, and on the right is weight pruning via magnitude weight pruning.
by gate variable which probabilissically takes on values in [0, 1]. The gates are sampled from hard-concrete distribution (Maddison et al. (017), which is amenable to the re-parameterization trick (Kingma & Welling/ 2014) and therefore to optimization via backpropogation. After training, we prune the neurons whose gates have the highest probability of being "off." Specific values of LO
pruning hyperparameters can be found in our codebase.
Once easy-case networks are pruned, we re-train the sparse networks for another 10 epochs to regain all lost accuracy and then re-initialize the pruned weights to This results in networks that are known to be sparse and prunable with no approximation error. The development accuracies both before and after fine-tuning are shown in F
Moderate Case In the moderate case of training, apply mild L1 regularization on the weights. We tried regularization parameters [1, 0.1, 0.01, 0.001, 0.0001], and found that 0.001 was the largest value we could use without impacting development accuracy.
Difficult Case In the difficult case, we do not apply any additional regularization during training.
B.2 TRAINING WITH DROPOUT
While applying L1 regularization improved neuron prunability, applying dropout at rates of 0.2 and 0.5 did not (Figure [7). While at first surprising. this makes sense upon further consideration. Dropout is known "break co-adaptation" between neurons (Mianjy & Arora 2019), meaning that any random subset of the neurons should produce approximately the same answer. In turn, this means that no single neuron should have it's weights go zero; all neurons maintain roughly the same importance.
Because of this, each neuron is assigned roughly a uniform probability of being sampled by our coreset method. And because the sample complexity is higher than the number of neurons in the layer, this results in 0% sparsity being achieved. This is somewhat ironic, since any particular choice of 50% of the neurons should have resulted in decent post-pruning performance.
B.3 VG DETAILS AND RESULTS
VGG-16 a neural network architecture which composed of several convolutional layers followed by 3 feed-forwatt layers with 4096, 4096, and 1000 hidden units respectively. All VGG-16 models are trained to achieve 92% development accuracy on CIFAR-10. Training is carried out for 15 epochs with standard SGD optimizer at learning rate 0.001, momentum 0.9, and training batch size of 32. The full results of this section are shown in Figure T0
"Easy case" VGG-16 networks are pruned using either weight pruming and LO pruning, similar to the LeNet models. Unlike the LeNet models, the final layer of VGG-16 could be pruned to 99% before accuracy began decrease after fine-tuning (Figure
14

---

Under review as a conference paper at ICLR 2021
Easy Case
Hoderate Case
Dificul Case
2006-
Sparsity Acheved
Samplex Sag
Samplee fag Spersity Achreved
Samp Ran Sparsity Achiored
(Layer
J025
55K
10.0
7.5
3000K
10
Surples
1900K-
08
00
8000
0.4
Size
16
02
3.0
inpi od easion suarnnnee
mpi ed =Ed L4agE3000 Pug Otserved
mo E0C SUITOPOOE
lug desenved Emo-
Avg Obverved Em
0.4
0.-
Semples Reg Sparsily Achivved
Sa Samee Req Sparsity Ach eved
00
Determinittcc (Layer size
1K]
04
Samp Serrelp-feheeeed.
02
Impl od tusiion Quarantes Rog deserved brto
el Quarantos Sog atserved
ieried Quarances log oecervel
0.5
02
2.0
Accurey
Figure 6: The full results of pruning the final layer of LeNet-300-100 under easy, moderate, and difficult training circumstances (Section 4.2). Shown are the implied epsilon bounds required to reach each desired accuracy guarantee (additive for neuron pruning, multiplicative otherwise), as well as the observed approximation (average and standard deviation). We also show the number of samples required meet the epsilon bound well as the sparsity achieved after sampling.
15

---

Under review as a conference paper at ICLR 2021
LeNet-300-100 Neuron Pruning With Dropout=0.5
1.0
Samples Req
600K
Sparsity Achieved
0.8
500K
400K
0.6
300K
0.2
100K
0.0
0.0
0.2
0.4
0.6
0.8
Figure 7: Samples required and sparsity (which is 0) for pruning LeNet-300-100 neurons via coreset method, when dropout was applied during training at a rate of 0.5.
Sparsity-Firss Pruning
Neuron Pruning
Deterministic Weight Pruning
1.0
0.8
0.8
Accuracy
0.6
Accuracy
0.6
Guaranteed Accuracy
Guaranteed Accuracy
Post Prune Accuracy
Post Prune Accurracy
0.4
0.4
0.2
0.0
0.4
0.6
0.8
0.6 Sparsity
0.8
Sparsity
140
Guaranteed Error
Guarantéed Error Observed Err
Observed Err
120
Approximation Error
Approximation mattinn Error
100
0.4
0.6 Sparsity
0.8
0.6
0.8
Sparsity
Figure 8: Results for pruning "moderate case" LeNet-300-100 with sparsity-first methods. Shown are the accuracy and approximation error achieved during pruning. as well as the implied accuracy guarantee and implied approxiation error bound computed from the number of samples taken.
16

---

Under review as a conference paper at ICLR 2021
Vgy 16 . Puinng Dev Aaa
Vgy 16 Megnilbute Pruning Dev Aui.
0.4
0.0
Dav Dev
0.1
0.6
04-
Pol--rum Pest-htsttuee
Pail-rune
Past-rasiuue
0.
0.0
0.8
09
06
Spersity
spansty
Figure 9: The development accuracy of VGG-16 models after pruning the final layer using heuristic methods and also after fine-tuning. On the left is neuron pruning using LO regularization, and on the right weight pruning using magnitude weight pruning.
"Moderate case" VGG-16 16 models were trained with an I.1 regularization term of 0.001, which was determined in a similar manner to that of LeNet-300-100.
C FURTHER ANALYSIS OF SAMPLE COMPLEXITY
C.I DOES DATA-INDEPENDENCE MEAN LOOSE BOUNDS?
We might assume that the looseness of the neuron pruning bounds can be attributed to overly-lax assumptions about the data distribution (i.e. that the L2 norm of inputs is simply bounded above). To test this hypothesis, measure the approximation error on these inputs, with the results shown in Figure T1 Randomizing the inputs does increase approximation error, but does increase enough to justify the scale of the bounds. We believe this implies that the bounds can be made tighter while maintaining the Sata-independence assumption.
generate random points the sphere used bound input vectors and
C.2 MANIPULATING TOTAL SENSITIVITY
In this section will demonstrate that the number of samples required by coreset neuron pruning to guarantee label-consistency at any accuracy can be arbitrarily manipulated. This involves manip- ulating both the total sensitivity of the layer and the distance between pre-softmax logits. First we'll prove the following lemma:
Lemma C.1 Suppose Φ(.) max(0,-), -). Then the "total sensitivity" of a hidden layer, as defined in Theorem A.4 for pruning neurons, can be made arbitrarily small or large by multiplying the weight matrix W (1) by positive constant a. The resulting neural network is label-consistent with the original.
Proof:
The first statement is fairly straight-forward prove. Let W aW(I) be modified weight matrix of the first layer, where a > 0 is some arbitrary constant. Similarly, let be the resulting total sensitivity of the network which uses W7(()) rather than W(1), Then
i Σ $
Σ
(2) wi ((31)a0 (12) kE[k]
max
Σ max w 0 (ow (e(k]
max w (B = at () (11b2 = a Σ
So scaling (1) by a also scales the total sensitivity by a. The fourth equality holds because max(0, ax) = max(0, 0, æ) and ||aw||| = al|w||12-
17

---

Under review as a conference paper at ICLR 2021
Easy Casa
Samples Sparsity Achacod
Samplechhr Spursity Achaoee
Samp flc Sparaiss Achiovad
00
151
Dala lind Curesel
(Layer Size IKI
2M
04
02
141
0.
40-
Ingl od basiion ouaranses rig deserved bmr
Iript ed EpS Cuarsnnoe Sug otserved EIT
7Vg obcervell S1T
Impicd sps Ovarances
30-
20-
10-
Samples Fag
tarpuas Bog Spandity Achavved
Samppas Bac
5006
Spariity ichreeed
Spandity Ach
400K
LLayer Size 10K)
Dara Dep Coreset
2008
1028
ed cosiion suarnntee Avg deserved Emor
ol Observed
Ang Obverved
0.2
10000
3.0
8000
88
Data Dep
9000
Deteministicc
(Layer size 10K)
4300
2000
Samp Pac Sparstty Achicead
3.0
od Buarantos nog desenved bmr
rrgpl ed Quarattos utserved
Impiidd Eps Dusrarses rop Obsorva
0.6
0.0
00
0.2
0.4
03
2.0
2/4
0.5
0.5
0.0
08 Guaranteed Remaiing hocuracs
0.2
0,4
Gur arbeed Remaining Accurec
Gustanieed Remallin SccuraTy
Figure 10: Full results of pruming the final layer of VGG-16. See Figure 6 and Section B.3 If the number of samples required is IM, we refrain from performing the computation and assume that the sparsity is O. (Though in the easy and moderate cases, it would be > 0.)
18

---

Under review as a conference paper at ICLR 2021
Easy Case
Modercte Case
Difficutt Case
implaal Eos Qusrense
Imoiid Eyoilon Buaranten
14
Implaed Epuilan Quarurfoc
Ang Oiocrval Briat
Oloar roil brre bnfor
Ang clourvel
Nax
Irax error
4-
Figure 11: Approximation enror of neuron pruning with coreset method, when the imputs not taken from the training distribution but are instead drawn from the L2 ball with radius 3, which is the maximum 1.2 norm allowed by the assumptions of the approximation bound proof.
Proving consistess requires the positive homogeneity property of ReLU feed-forward neural networks (Du et al. 2018a), which says that multiplying weight matrix by results in scaling the output of the network by a. The proof is very similar to the reasoning above. Let f be the two-layer ReLU network with weights (W(1), W()), and be the network with weights (WV(1, W(2).. For any imput x E X, we have
f(x) 2(W()) ((ll a af(x)
Finally, we note that scaling the pre-softmax outputs by does not change the predicted label:
arg f(x); arg max af = arg max f(x);
A simple corollary of this idea is that arbitrarily increase decrease the number of samples required to achieve any accuracy guarantee. From Lemma C. we know that scaling a weight matrix by constant a increases the total sensitivity by a. At the same time, also increases the additive epsilon bound required guarantee each label's consistency, because the pre-softmax logits are multiplied by a. This is equivalent increasing or decreasing the temperature of the softmax distribution. Since sampling complexity grows roughly linearly with total sensitivity and shrinks quadratically with the size of the epsilon bound, the net result is that multiplying by a reduces the required number of samples to achieve any particular accuracy guarantee.
Corollary C.2 In the context of Theorem A.4 multiplying the weight matrix W(I) by positive constant a > 1 decreases the number of samples required to achieve any particular accuracy guar- antee.
And indeed, we can see in Figure 12 that when we scale the layer weights of LoNet-300-100 up by various magnitudes, the additive epsilon bound required guarantee any accuracy grows proportionally, which quadratically shrinks the number of samples required to meet the guarantee.
19

---

Under review as a conference paper at ICLR 2021
= 100
8 1000
2 10000
Serrpies Rog
Semppies Rog
Semplees Reg
Samplee Rog
2956
3040
1998
700
1000
300
8/1
U8
0
00
0.2
0/1
00
0.2
10
15
000
022
08
Inpract spaien Guarnnize: Aeg
Inpract spodon Aeg
Implist Egraton Guuruntoc
Implist Egraton Guuruntice
80/00
301000
820
2.000
150200
620
M000000
102
200
2020
Figure 12: Results for pruning LeNet-300-100 with a coreset based neuron pruning method, after multiplying the pruned layer's weight matrix by constant a.
20


Reviews:
[{"review_id": "nDfLQP176wa", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overall, I vote for accepting. I like the idea of analyzing the practical performance of coreset-based pruning methods and discussing the relation between sparsity, approximation bounds, and accuracy. \n\nPros:\n1. The paper provides an empirical evaluation that shows the theoretical bounds of coreset-based algorithms could be loose.  This is an important issue for the practicability of coreset-based algorithms.\n2. The paper shows the tight approximation bound is not a necessary condition for accuracy by analyzing fine-tuning. The quantitative results that fine-tuning increases approximation errors are interesting.\n\nCons:\n1. The paper regards the loose bounds as a shortage that weakens the predictive power of coreset-based pruning methods. But this can also be regarded as an advantage of coreset-based algorithms that can heavily increase sparsity while maintaining accuracy. I suggest the authors to give more discussions on both sides.\n2. The experiments only consider coreset-based pruning methods since they have provably guarantees. However, due to the empirical results of fine-tuning, we can recover accuracy after post-pruning. Then it is interesting to also compare with other commonly-used pruning methods, e.g., compare the sparsity of different pruning methods that achieve the same accuracy with fine-tuning. \n\nSome typos:\n1. Figure 2 -> Table 2", "extra_scores": {}, "extra_text": {}}, {"review_id": "FF-GFqOVODt", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper investigates when neural pruning approximation bounds useful from several perspectives. Showing that approximation bounds are loose and require a large sample size. It also explores the influence of fine-tuning after pruning by approximation bounds.\n\nHowever, I a bit concerned about the novelty and impact of the paper. I cannot find border impacts and applications on the topic discussed in the paper since all results are based on observation. No further insights on tighter bounds or discussion of the reasons proposed. I would increase my score if those insights provided.\n\nAlso, in the last line of page 6, the author mentions Figure 4.2 which does not appear in the paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "2B6gVZQj8dy", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies recent approximation bounds of coreset-based pruning strategies for neural networks.  It concludes that the bounds in certain cases can be very conservative (guarantee much lower accuracy than seen in practice), especially if the network can be fine-tuned after pruning,  and should not be used as a guide to estimate expected accuracy.  \n\nWhile the conclusion that the bounds can be conservative is not unreasonable -- that was not the point of the papers it tries to criticize, bounds do not have to be good estimates.  Furthermore, I find the paper to be poorly and confusingly written, with many questionable choices done in setting up error metrics, and the experiments (please see details below), so I recommend to reject it. \n\nA bound on performance and an estimate of performance serve different purposes.  Even tight bounds that can not be improved may give poor estimates, but they are still useful in providing theoretical understanding of a problem, and possibly in safety-critical applications where one needs to guarantee worst case results.  So the criticism of the paper may be besides the point of the papers it analyzes.  They are among the first to show that coreset-based methods allow any kind of theoretical approximation guarantees, but they do not claim that the bounds are good predictors of performance.   The present paper would have more value if it attempted to improve the bounds, or perhaps develop accurate estimators of accuracy vs. pruning level, or maybe propose a pruning method which is more effective empirically. \n\nFurthermore, for a given neural network that has been pruned it is fairly inexpensive to numerically evaluate the approximation accuracy w.r.t. to the full model on a validation set -- so I do not see much practical value of the exercise of trying to infer it from bounds.  Furthermore, for pruned networks that have later been fine tuned,  indeed the results of the papers do not apply, so the bounds unsurprisingly may have little to do with empirical results. \n\nDetailed comments (non-exhaustive list of issues, but sufficient for my rating):\n\n1) You go from additive and multiplicative bounds to error rates in lemma 3.1.  Just because epsilon > (f(x)i - f(x)i')/2  does not guarantee that it will make a mistake (it has the ability to make a mistake, but it does not have to).  Lemma 3.1. is on the one hand elementary, but on the other hand it introduces another layer of approximation between accuracy and pruning. \n2)  \"guaranteeing that 50% of the development set labels that are correct will remain correct\"...   The goal of approximating a neural net is to make sure that the output of the approximate NN matches the original one -- how is it relevant whether the original was correct or not w.r.t. to the target labels?  Why do you condition on predictions being correct?  \n3) 'fine tuning can recover large amounts of accuracy while simultaneously maintaining of increasing approximation error\" ... That doesn't make sense.  Do you mean 'improving' or 'reducing' approximation errors? \n4)  Sections 2.1 (and same for 2.2).   A lot of important details are left to appendix -- this section gives very little useful information to understand the method.  Where is algorithm 1 -- is it in your appendix or is it in Baykal's paper?  Where are the theorems -- in your paper / appendix / Baykal's paper?  What is the 'importance', how is it computed? A more informative intro would be much appreciated. \n5) The easy problem is a NN with 90 to 95% of weights set to 0.  The network is refitted, and 0-weights are re-enabled?  What does it mean for 0 weights to be re-enabled?  If the pruning strategy keeps the 0-edge -- does it mean the edge is active and the network is non-sparse?  This is very confusing (either poorly described, or this is an artificial corner case). It seems hard to imagine that a coreset pruning method that is given a sparse network will make it less sparse.  \nIf on the other hand the accuracy bounds somehow ignore edges which are already 0 -- then it seems like an easy opportunity to derive better bounds?\n6) For the above easy network (with mostly zero weights) -- the coreset algorithm gives more than 50% of elements with probability 0 of being sampled, so the conclusion is that if we ask for 50% sparsity -- it will run forever?  This whole discussion just seems very strange and confusing. \n7) does 90% sparsity mean that there are 90% zeros or 90% non-zeros?  Maybe use clearer language. \n8) The discussion of scaling up the bounds due to total homogeneity --  also seems very strange: the paper claims that positive homogeneity allows to 'arbitrarily increase or decrease sample complexity by scaling the appropriate weight matrices by a constant factor'.  Is this for the additive or multiplicative bound?  The paper says \"investigating the full implications of this observation are out of scope of this paper\".  I would expect some discussion here.  For the additive bound -- if you scale up the weigths in NN, the relative approximation error will be much smaller, so isn't it natural to require larger sample complexity? \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work studies corset-based pruning strategies for neural networks, and highlights the looseness of approximation bounds, the difference between approximation error and probability, and the importance of considering post-pruning fine-tuning. I found the empirical findings and concerns raised around the utility of approximation bounds for pruning guarantees interesting and important, and appreciated the benchmark with varying levels of difficulty. However, the empirical analysis was limited to coreset-based methods and a simple LeNet architecture, and could benefit from considering additional non-coreset based approaches, architectures, and datasets. While I agree with the authors that new methods are not required for their work to be valuable, I believe that a more thorough empirical analysis is needed to support that their claims that current approximation bounds are not useful across wider experimental settings.
Decision: Reject