Data-Efficient Structured Pruning via Submodular Optimization
Authors: Marwa El Halabi
Suraj Srinivas
Simon Lacoste-Julien
Venue: NeurIPS 2022 Accept (2022)
Keywords: Structured pruning
weakly submodular optimization
neural networks compression

Abstract: Structured pruning is an effective approach for compressing large pre-trained neural networks without significantly affecting their performance. However, most current structured pruning methods do not provide any performance guarantees, and often require fine-tuning, which makes them inapplicable in the limited-data regime. We propose a principled data-efficient structured pruning method based on submodular optimization. In particular, for a given layer, we select neurons/channels to prune and corresponding new weights for the next layer, that minimize the change in the next layer's input induced by pruning. We show that this selection problem is a weakly submodular maximization problem, thus it can be provably approximated using an efficient greedy algorithm. Our method is guaranteed to have an exponentially decreasing error between the original model and the pruned model outputs w.r.t the pruned size, under reasonable assumptions. It is also one of the few methods in the literature that uses only a limited-number of training data and no labels. Our experimental results demonstrate that our method outperforms state-of-the-art methods in the limited-data regime. 

Data-Efficient Structured Pruning via Submodular Optimization
Marwa El Halabi' Samsung SAIT Al Lab, Montreal
Suraj Srinivas Harvard University
Simon Lacoste-Julien Mila, Université de Montreal Samsung SAIT AI Lab, Montreal Canada CIFAR AI Chair
Abstract
Structured pruning is an effective approach for compressing large pre-trained neural networks without significantly affecting their performance. However, current structured pruning methods do not provide any performance guarantees, and often require fine-tuning, which makes them inapplicable in the limited-data regime. We propose a principled data-efficient structured pruning method based on submodular optimization. In particular, for given layer, we select neurons/channels to prune and corresponding new weights for the next layer, that minimize the change in the next layer's input induced by pruning. We show that this selection problem is a weakly submodular maximization problem, thus it can be provably approximated using an efficient greedy algorithm. Our method is guaranteed to have an exponentially decreasing error between the original model and the pruned model outputs w.r.t the pruned size, under reasonable assumptions. It is also one of the few methods in the literature that uses only limited-numbee of training data and no labels. Our experimental results demonstrate that our method outperforms tate-of-thheart methods in the limited-data regime.
Introduction
As modern neural networks (NN) grow increasingly large, with some models reaching billions of parameters [McGuffie and Newhouse 2020), they require an increasingly large amount of memory, power, hardware, and inference time, which makes it necessary to compress them. This is especially important for models deployed on resource-constrainee devices like mobile phones and smart speakers, and for latency-critical applications such as self-driving cars.
Several approaches exist to compress NNs.
Some methods approximate model weights using Courbariaux et al. 2015 or low-rank approximation
quantization and hashing Gong et al.) 2014 4
and tensor factorization Denil et al.) 2013 Lebedev et al. 2015 Su et al., 2018). In another
class of methods called knowledge distillation, small network is trained to mimic much larger
network Bucila et al.) 2006 Hinton et al., 2015). Other methods employ sparsity and group-sparsity
regularisation during training, to induce sparse weights (Collins and Kohli 2014 Voita et al. 2019
In this work, we follow the network pruning approach, where the redundant units (weights, neurons or filters/chaneels) of pre-trained NN are removed; see [Kuzmin et al. 2019 Blalock et al. 2020
work done partially MIT, CSAIL.
work done partially at Idiap Research Institute, Switzerland.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Hoefler et al. [02T] for recent surveys. We also focus on the limited-data regime, where only few training data is available and data labels are unavailable. The advantage of pruning approaches is that, unlike weights approximation- based methods, they preserve the network structure, allowing retraining after compression, and unlike training-based approaches, they do not require training from scratch, which is costly and requires large training data. It is also possible to combine different
compression approaches to compound their benefits, see c.g., [Kuzmin et al. 2019 Section 4.3.4].
Existing pruning methods fall into two main categories: unstructured pruning methods which prune individual weights leading to irregular sparsity patterns, and structured pruning methods which prune regular regions of weights, such as neurons, channels, or attention heads. Structured pruning methods are generally preferable as the resulting pruned models can work with off fff-the-shelf hardware or kernels, as opposed to models pruned with unstructured pruning which require specialized ones.
The majority of existing structured pruning methods are heuristics that do not offer any theoretical guarantees. Moreover, most pruning methods are inapplicable in the limited-data regime, as they rely on fine-tuning with large training data for at least a few epochs to recover some of the accuracy lost with pruning. Mariet and Sra [015 proposed "reweighting" procedure applicable to any pruning method, which optimize the remaining weights of the next layer minimize the change in the input to the next layer. Their empirical results on pruning single linear layers suggest that reweighting can provide a similar boost to performance as fine min-ttnnnn, without the need for data labels.
Our contributions We propose a principled data-efficient structured pruning method based on submodular optimization. In each layer, our method simultaneously selects neurons to prune and new weights for the next layer, that minimize the change in the next layer's input induced by pruning. The optimization with respect to the weights, for a fixed selection of neurons, is the same one used for reweighting in Mariet and Sra 2015]. The resulting subset selection problem is intractable, but we show that it can be formulated as weakly submodular maximization problem (see Definition 2. We can thus use the standard greedy algorithm to obtain a - e solution, where y is non-zero if we use sufficient training data. We further adapt our method to prune any regular regions of weights; we focus in particular on pruning channels in convolution layers. To prune multiple layers in the network, we apply our method to each layer independently or sequentially.
( >>approxiimattonn to the optimal
We show that the error induced by pruning with our method on the model output decays with an O(e->k) rate w.r.t the number k of neurons/channels kept, under reasonable assumptions. Our method uses only limited training data and no labels. Similar to [Mariet and Sra. 2015], we observe that reweighting provides significant boost in performance not only to our method, but also to other baselines we consider. However unlike [Mariet and Sra 2015]. we only use a small fraction of the training data, around 1% in our experiments. Our experimental results demonstrate that our method outperforms state-of-the-ar pruning methods, even when reweighting is applied to them too, in the limited-data regime, and it is among the best performing methods in the standard setting.
Related work A large variety of structured pruning approaches has been proposed in the literature, based on different selection schemes and algorithms to solve them. Some works prune
neurons/channels individually based on some importance score [He et al. 2014 Li et al. 2017
Liebenwein et al. 2020 Mussay et al., 2020 202T Molchanov et al. 2017] Srinivas and Babu 2015]. Such methods are efficiett and easy to implement, but they fail to capture higher-order interactions between the pruned parameters. Most do not provide any performance guarantee, One exception
are the sampling-basee based methods of [Liebenwein al. 2020, Mussay et al., 2020 202T]. who show an ((1/k) error rate, under some assumptions on the model activations.
methods that aim to prune neurons/channels that minimize the change induced by pruning in the output of the layer being pruned, or its input to the next layer [Luo et al. 2017 He et al., 2017 Zhuang et al., 2018 Ye al. 2020b]. These criteria yield an intractable combinatorial problem. Existing methods either use a heuristic greedy algorithm to solve it [Luo al. 2017 Zhuang al. 2018). or they solve instead its f--relaxation using alternating minimization [e et al.] 2017]. or a greedy algorithm with Frank- Wolfe like updates ([ee et al. 2020b]. Among these works only YYe et al. 2020b) provides theoretical guarantees, showing an O(e oR error rate. Their method is more expensive than ours, and only optimize the scaling of the next layer weights instead of the weights themselves. A global variant of this method is proposed in Ye et al. [2020a]] b). which aim to prune neurons/channels that directly minimize the loss of the pruned network. A similar greedy algorithm with Frank- Wolfe like updates is used to solve the E -ereeaxxtiio of the selection problem. This method has an O(1kk2) error rate and is very expensive, as it requires full forward
Closer to our approach
2

---

pass through the network at each iteration. See Appendix A for more detailed comparison of our method with those Ye et al. 2020a|b
Mariet and Sra 20155 depart from the usual strategy of pruning parameters whose removal influences the network the least. They instead select subset of diverse neurons to keep in each layer by sampling from a Determinantal Point Process, then they apply their reweighting procedure. Their experimental results show that the advantage of their method is mostly due to reweighting (see Figure therein).
2 Preliminaries
We begin by introducing our notation and some relevant background from submodular optimization.
Notation:
Given ground set V (1,2. ... d} and
function F :2 + R4, we denote
the marginal gain of adding a set / C V to amother set S C V by F(I S) F(SUI) - F(S), which quantifies the change in value when adding / to S. The cardinality of a set S is written as (S]. Given a vector Rd we denote its support set by supp(æ)
{i E V|2; * 0}, and its 2--nomm by ||]]|2- Given matrix X Rdd'xd, we denote its i-th column by X,, and its Frobenius norm by ||X] Given set S _ V. X is the matrix with columns X; for all E S, and 0 otherwise, and 1 the indicator vector of S, with [1s] for all E S. and 0 otherwise.
Algorithm 1 GREEDY
Input: Ground set V, set function F 2V - R2,, budget E N+
2: S =- 0
3: while |S| < k do
4: i' + arg max F(il
5: S (t
6: end while
7: Output: S
Weakly submodular maximization: A set function is submodular if it has diminishing marginal gains: F(i S) 2 F(i 7) for all C.. V (.. We say that F is normalized if F(6) 0. and non-decreasing if F(S) I. F(T) for all CT Given a non-decreasing submodular function F, selecting a S C V with cardinality |S| S that maximize F(S) can be done efficiently using the GREEDY algorithm (Alg. []. The returned solution is guaranteed to satisfy F(S) 2 (1 - 1/ee) max]s|ss
F(S) Nemhauser et al. 1978 In general though maximizing a non-submoo -onsuubood function over cardinality constraunt Is NP-Hard [Natarajan] 1995]. However, Das and Kempe (20IT) introduced a notion of weak submodularity which is sufficient to obtain constant factor approximation with the GREEDY algorithm.
Definition 2.1. Given a set function F 2V IR, V,K E N4, we say that F is yu,k-weaki submodular, with YU > if
TUU (OLKF(S Σ F((LT))
LES
for every two disjoint sets L,S S.C. such that L S U, <
The parameter TU.& is called the submodularity ratio of F. It characterizes how close set function to being submodular. If F is non-decreasing then YU E [0, 1], and F is submodular and only if yU, = 1 for all U C V, k E N4. Given non-decreasing V/.. " -weakly submodular function F, the
Greedy algorithm is guaranteed to return solution Å satisfying F($) 2 (1 (1-e- -?s..) max]s|<* F(S) Flenberg et al. 2016 Das and Kempe 2011 Hence, the closer F to being submodular, the better the approximation guarantee.
3 Reweighted input change pruning
In this section, we introduce our approach for pruning neurons in a single layer. Given a large pre- trained NN, n training data samples, and layer with ny neurons, goal is to select a small number
3

---

k out of the ny neurons to keep, and prune the rest, in a way that influences the network the least. One way achieve this by minimizing the change in input the next layer + 1, induced by pruning. However, simply throwing away the activations from the dropped neurons is wasteful. Instead, we optimize the weights of the next layer to reconstruct the inputs from the remaining neurons.
Formally, let A E _2xx be the activation matrix of layer & with columns af.-.. ,hh where af E IR" is the vector of activations of the ith neuron in layer l for each training input, and let we-1 E - be the weight matrix of layer L + 1 with columns wi+1
"241" where wi +1 E Th is the vector of weights connecting the ith neuron in layer + 1 to the neurons in layer When a neuron is pruned in layer L, the corresponding column of weights in W and row in W removed. Pruning ni k neurons in layer E reduces the number of parameters and computation cost by (ng- - /n/ for both layer and 8+1
Let Ve {1.-.. ,ee. Given a set S Ve. we denote by A the matrix with columns af for all i S, and otherwise. That is, A is the activation matrix of layer after pruning. We choose set of neurons S C V2 to keep and new weights W E RReexnee that minimize:
||A' - A
min 1
(1)
Note that AW are the original inputs of layer / + 1, and A& are the inputs after pruning and reweighting, i.e., replacing the weights We+t of layer l + with the new weights W
3.1
Greedy selection
Solving Problem ① exactly is NP-Hard Natarajan, 1995 However, we show below that can be formulated as weakly submodular maximization problem, hence it can be efficiently approximated.
Let
F(S) [|A
|| min W -AGW W
then Problem 1 is equivalent to sa F(S).
Proposition 3.1. Given U S V. E N+, F is normalized non-decreasing YU, weakly submodular function, with
min 14 + ||
'U maX/ AA=11
The proof of Proposition
3.1 follows by writing as the sum of ne+1 sparse linear regression millsgpp/@s IC A A - A A 11 and from the relation
problems F(S)
A
w
established Elenberg et al.
2016
Das and Kempe 2011
between weak submodularity and sparse
eigenvalues of the covariance matrix (see Appendix B.1b
We use the GREEDY algorithm to select set $ S V, of l neurons to keep in layer E. As discussed in Section the returned solution guaranteed to satisfy
F($) 2 (1-e -7 max F(S)
SS
Computing the lower bound on the submodularity ratio 75, in Proposition 3.1 is NP-Hard Das and
min(2k; ne) columns of A are linearly independent. If the number of training data is larger than the number of neurons, i.e., n >> ngg this is likely to be satisfied. We verify that this indeed the case in our experiments in Appendix We also discuss the tightness of the lower bound in Appendix F
Kempe, 2011) It is non-zero if any min (2k,
We show in Appendix that F satisfies an even stronger notion of approximate submodularity than weak submodularity, which implies a better approximation guarantee for GREEDY than the one provided in Eq. 43. Though, this requires stronger assumption: any A + 1 columns of AA' should be linearly independent and all rows of W should be linearly independent. In particular, we would need that ni 14+11 which is not always satisfied.
In Section we show that the approximation guarantee of Greedy implies an exponentially decreasing bound on the layerwise error, and on the final output error under mild assumption.

---

3.2 Reweighting
For a fixed S S Ve, the reweighted input change || | A W is minimized by setting
W = x (A
(4)
where (A9) R is the matrix with columns x. (a.) such that
x
$ (af) E arg min |/a - AxI for all j E Ve.
(5)
supp(a)[S
E+1 for all i E S, and w for all $ S, m Vi-1- Namely, the new weights merge the weights from the dropped neu- rons into the kept ones. This is the same reweighting procedure introduced in (Mariet and Sra 2015]. But instead of applying it only at the end to the selected neurons S, it is implicitly done at each iteration of our pruning method, as it required to evaluate F. We discuss next how this can be done efficiently.
Note that the new weights are given by w 2-1 + Egslæ (A w
3.3
Cost
Each iteration of GREEDY requires (nn) function evaluations of F. Computing F(S) from scratch needs Ol: (ne-ne-1 + (ne - ne+1)) time, naive implementation of GREEDY is too expensive. The following Proposition outlines how we can efficiently evaluate F(S + a) given that F(5) computed in the previous iteration.
was
Proposition 3.2. Given S S Ve such that |S| S k, i $ S. let projs (a)) = A's (az) be the projection of a' onto the column space of Alg, Rs(a)) of - projs(af and arg min, Re(a())eER lla5- =112 the corresponding residual and the projection of a onto it. We can write
(a)) E
meil
F(ISS)
Σ llpro () 1
where projnn (Avis) ) is the matrix with columns proing (af)) for all of S, otherwise. Assuming F(S), projs(af) and x (a()) ( for all j & S were computed in the previous iteration, we can compute F(S i), (r))s+((a)) and x (a (df) all j & (S +8++) in
O (n441 + + k)) time.
The optimal weights in Eq. can then be computed in O(k ne- n8411) time, at the end of GREEDY.
The proof is given in Appendix B.2 and relies on using optimality conditions to construct the least
squares solution (a,)) from x=' (af).
In total GREEDY'S ' runtime is then O(k (mz)². (mz-1 +n+ . In other words, our pruning method costs as much as (A)) forward passes in layer f+ 1 with batch of size n (assuming n6+1 O (n.) ))
Using a faster variant of GREEDY, called STOCHASTIC- GGREDDY MMrzasoleiman et al. 2015
further reduces the cost to (log(1/e) ( + n +)), or equivalently Oloo forward passes in layer & + 1 with batch of size n, while maintaining almost the same approximation guarantee (1
7 c) in expectation.
Note also that computing the solutions for different budgets k/ < ko can be done at the cost of one by running GREEDY with budget k. Our method is more expensive than methods which prune neurons individually (He et al. 2014 Li et al. 2017, Liebenwein et al., 2020 Mussay et al. 2020 2021
Molchanov al. 2017 Srinivas and Babu 2013 but much less expensive than loss-based method
like
Ye et al. 2020a b which requires (k) forward passes in the full network, for each layer.
Pruning regular regions of neurons
In this section, discuss how adapt our approach to pruning regular regions of neurons. This easily achieved by mapping any set of regular regions to the corresponding set neurons, then applying the same method in Section
In particular, focus pruming channels in CNNs.
Mirzasoleiman et al. 2015 only consider submodular functions, but it is straighforward to extend their
result weakly submodular functions Appendix B.3
5

---

Given a layer E with ny output channels, let X E [R"RexnxXH, X be its activations for each output channel and training input, where Pe is number of patches obtained by applying a filter of size ry X Tw- and let F++1 E R R Xmexra X be the weights of layer f. + 1, corresponding to ne filters of size rh X for each of its output channels. When an output channel is pruned in layer f, the corresponding weights in F and Fé+1 are removed. Pruning n4 k output channels in layer & reduces the number of parameters and computation cost by (ng - k)/ne g for both layer and E + 1. If layer & is followed by a batch norm layer, the weights therein corresponding to the pruned channels are also removed.
We arrange the activations X E R RTPEXTATT of each channel с into Thew columns of Similarly, we arrange the weights FL+1
A E RaPeene-Th i.e., A "X,,",,,""" Re XTw of each channel e into Th Iw rows of W E RT XM441, i... (W++1)T [0F9T (1% ]T. Recall that V2 {1,... me). and let V. = (1, rrTwwee) We define a function M 2 + 2% which maps every channel c to its corresponding Farw columns in A Let G(S) F(M(S)), with F defined in Eq. 2 then minimizing the reweighted input change || | - Alr(s) W++ ||3 with budget & equivalent to sax G(S). The following proposition shows that this remains weakly submodular maximization problem.
Proposition 4.1. Given U C V2, k N4, G is a normalized non-decreasing " -weakly submodular function, with
mil1sllsssLMMMMbssrr0000 ||A
V maxx|pppp==a/|HHosssrrr... || =A
Proof sketch. G is weakly submodular iff F satisfies YUE F(M(S) Lies (L))) for every two disjoint sets L, S C Vv, such that L C U, <
<
The proof follows by extending the relation established in [Elenberg et al. 2016 Das and Kempe 2011 between weak submodularity and sparse eigenvalues of the covariance matrix to this case.
As before, we use the GREEDY algorithm, with function G, to select a set 3 S Ve of & channels to keep in layer f. We get the same approximation guarantee G($) 2 (1 -e 78.*) max]sis* G(S). The submodularity ratio S is non-zero if any min (2k,, ne Frr columns of A are linearly independent. In our experiments, we observe that in certain layers linear independence only holds for l very small, e.g., < 0.01ng. This due to the correlation between patches which overlap. To remedy this, we experimented with using only TAT", random patches from each image, instead of using all patches. This indeed raises the rank of A but certain layers have very small feature map size so that even the small number of random patches have significant overlap, resulting in still very small range where linear independence holds, c.g., kt S 0.08n, (see Appendix B for more details). The results obtained with random patches were worst than the ones with all patches, we thus omit them. Note that our lower bounds on Y/3 k are not necessarily tight (see Appendix F). Hence, having linear dependence does not necessarily imply that ys, = O; our method still performs well in these cases.
For fixed S Ve, the optimal weights are again given by W x M(5) (A*) The cost of running GREEDY and reweighting is the same as before (see Appendix B.2)
5
Pruning multiple layers
In this section, we explain how apply our pruning method to prune multiple layers of NN.
5.1
Reweighted input change pruning variants
We consider three variants of our method: CHANGE. In LAYERINCHANGE, we prune each layer independently, i.e.. we apply exactly the method in Section 3 or according to the layer's 's type. This is the fastest variant; it has the same cost as pruning single layer, each layer can be pruned in parallel, and it only requires one forward pass to get the activations of all layers. However, it does not take into account the effect of pruning one layer on subsequent layers.
LAYERINCHANGE, SEQINCHANGE, and ASYMIN-
In SHAINC we prune each layer sequentially, starting from the earliest layer to the latest one. For each layer É, we apply our method with A replaced by the updated activations Be after

---

having pruned previous layers, i... we solve min [S]sA. ( [B'W - -B I| In ASYMINCHANGE, we also prune each layer sequentially, but to avoid the accumulation of error, we use an asymmetric formulation of the reweighted input change, where instead of approx- imating the updated input B B'++, we approximate the original input A A' i.e., we solve mill W E 1 || - B
11g This problem is still weakly submodular max- imization problem, with the same submodularity ratio given in Propositions 3.1 and 4.1 with A in the
replaced by Be therein (see Appendix [..1 Hence, the same approximation guarantee symmetric formulation holds here. Moreover, a better approximation guarantee can again be obtained under stronger assumptions (see Appendix D) The cost of running GREEDY with the asymmetric formulation and reweighting is also the same as before (see Appendix B.2
In Section 6 show that the sequential variants of our method both have an exponential error rate, which is faster for the asymmetric variant. We evaluate all three variants in our experiments. As expected, ASYMINCHANGE usually performs the best, and LAYERINCHANGE the worst.
5.2 Per-layer budget selection
Another important design choice is how much to prune in each layer, given a desired global compres- sion ratio (see Appendix for the effect of this choice on performance). In our experiments, we use the budget selection method introduced [Kuzmin et al. 2019, Section 3.4. 1]. which can be applied to any layerwise pruning method, thus enabling us to have a fair comparison.
Given a network with L layers to prune, let c original size be the desired compression ratio. We want pruned size
to select for each layer f, the number of neurons/channels kg = Og to keep, with ag chosen from We define a layerwise accuracy metric
a fixed set of possible values, e-g.. 0g E {0.05, 00..5,0.1,... 0.1,.... 1}. (ke) as the accuracy obtained after pruning layer É, with a budget ke, while other layers are kept intact, evaluated on a verification set. We set aside a subset of the training set to use as verification set. Let Pagg be the original model accuracy, Corig the original model size, and C(ki,.... , .kz)) the pruned model size. We select the per-layer budgets that minimize the per-layer accuracy drop while satisfying the required compression ratio:
min { : VL [ck,)((ke) 2 Pang - T, C(k1, ,,k) S Con
(6)
We can solve the selection problem 6 using binary search, if the layerwise accuracy Pε(ke) is non- decreasing function of ky. Empirically, this is not always the case, the general trend is non-decreasing. but some fluctuations occur. In such cases, we use interpolation ensure monotonicity.
Alternatively, another simple strategy is to prune each layer until the perlayer error (the reweighted input change in our case) reaches some threshold and vary to obtain the desired compression ratio, as done in Zhuuan et al.) 2018 Ye et al. 2020a
Error convergence rate
In this section, provide the error rate of our proposed method. The omitted proofs are given in Appendix C We first show that the change in input to the next layer induced by pruning with our method, with both the symmetric and asymmetric formulation, decays with exponentially fast rate.
Proposition 6.1. Let Š be the output of the GREEDY algorithm and We++ the corresponding optimal weights (Eq. 4 ) then
| - 13 -AG--A-A11111 Se Te. k/ne w/
and
BBWWe+-BBBre Se k/m
To k/me)
min wi+
xx
This follows by extending the approximation guarantee of GREEDY in Elenberg et al. 2016 Das
and Kempe 2011 to F(S)= 2 (1 Ss. k/me) max F(S). Note that this bounds uses the submodularity ratio "s.ne for which the lower bound in Proposition 3.1 is non-zero only if all columns of A are linearly independent, which is more restrictive. Though as discussed earlier, this
7

---

bound is not necessarily tight. We can further extend this exponential layerwise enror rate to an exponentially rate on the final output error, if we assume as in [Ye et al., 2020b] that the function corresponding to all layers coming after layer l is Lipschitz continuous.
Corollary 6.2. Let y E R be the original model output, I E IR" the output after layer is pruned using method, and H the function corresponding to all layers coming after layer l, i.e y H(AA (A'Wtt1), (A's We+l). ). If (AA
is Lipschitz continuous with constant || [ Ilp.. then
ly - 1 S 78, H Táp 1
Proof. Since H is Lipschitz continuous, we have l1y 111 The claim then follows from Proposition 6.1
<
H Lip A
- 1
This matches the exponential convergence rate achieved by the local imitation method in YYe et al. 2020b, Theorem 1], albeit with different constant. Under the same assumption, we can show that pruning multiple layers with the sequential variants of our method, SEQINCHANGE and ASYMIN- CHANGE, also admits an exponential convergence rate:
Corollary 6.3. Let y E IR" be the original model output, y St, y E RR the outputs after layers to I are sequentially pruned using SEQINCHANNE and ASYMINCHANGE, respectively, and He the function corresponding to all (umpraned) layers coming after layer f. If every function Hg is Lipschitz continuous with constant
[Helliip then
1 -
Su
1s mp ke/ /11 [e P2p | 1W
t=1
and
Ily
y 34
112 -
(1 8= 8=
II
and be belne (eeeee 78 Re/me He
The result is obtained by iteratively applying Proposition 6.1 to the error incurred after each layer is pruned. The rate of SEQINCHANGE matches the exponential convergence rate achieved by the local imitation method in YYe all 2020b Theorem 6]. The bound on ASYMInCHANGe is stronger, confirming that the asymmetric formulation indeed reduces the accumulation of errors.
7 Empirical Evaluation
In this section, we examine the performance of our proposed pruning method in the limited-daa regime. To that end, we focus on one-shot pruning, in which pre-trained model is compressed in single step. without any fine-tuning. We study the effect of tine-tuning with both limited and sufficient data in Appendix H We compare the three variants of our method, LAYERINCHANGE, SEOINCHANGE, and ASYMINCHANGE, with the following baselines:
LAYER (Ye et al. 2020a]: for each layer, first removes all neurons/channels in that layer, then gradually adds back the neuron/channel that yields the largest decrease of the loss, evalu- ated on one batch of training data. Layers are pruned sequentially from the input to the output layer.
Liebenwein et al. 2020 : samples neurons/channels, in each layer, with probabilities proportional sensitivities based on (activations weights), and prunes the rest.
ACTGRAD Molchanov et al., 2017]: prunes neurons/channels with the lowest (activations x gradients), averaged over the training data, with layerwise l fy-normalization.
LAYERACTGRAD: prunes neurons/channels with the lowest (activations x gradients), averaged over the training data, in each layer. This is the layerwise variant of ACTGRAD.
LAYERWEIGHTNORM [Li et al. 2017 : prunes neurons/channels with the lowest output
weights & normm in each layer.
RANDOM: prunes randomly selected neurons/channels globally across layers in the network.
LAYERRANDOM: prunes randomly selected neurons/channels in each layer.

---

We also considered the global variant of WLAYERWEIGHTYE exclude it from plots, as is always the worst performing method. We evaluate the performance of these methods on the LeNet model (LeCun et al.
proposed in [He et al.
2014]. but we
1989 on the MNIST dataset [Lecun et al. 1998].
and on the ResNet56 (He et al. 2016] and the VGGI1 [Simonyan and Zisserman 2015] models on the CIFAR-10 10 dataset (rizhevsky et al. 2009). To ensure a fair comparison, all experiments are based on our own implementation of all the compared methods. To compute the gradients and activations used for pruning in LAYERSAMPLING ACTGRAD, LAYERACTGRAN and our method's variants, we use four batches of 128 training images, i.e., n = 512, which corresponds to ~ 1% of the training data in MNIST and CIFARIO. We consider two variants of the method proposed in (Ye et al., 2020a]: a limited- data variant LAYERGREEDY which only uses the same four batches of data used in our method, and full-data variant LAYERGREEDY FS-dd -fd with access to the full training data.
We report top-1 accuracy results evaluated on the validation set, as we vary the compression ratio original size pruned size Unless otherwise specified, we use the per-layer budget selection method described in Sec- tion 2onp22for for all the layerwise pruning methods, except for LAYERSAMPLIN for which we use its own budget selection strategy provided in [Liebenwein al. 2020 We use a subset of the training set, of the same size as the validation set, as a verification set for the budget selection method. To disentangle the benefit of using our pruning method from the benefit of reweighting (Section 3.2). report results with reweighting applied to all pruning methods, or none of them. Though, we will focus our analysis on the more interesting results with reweighting, with the plots without reweighting mostly serving as a demonstration of the benefit of reweighting. Results are averaged over five random runs, with stan- dard deviations plotted as error bars. We report the speedup (onginal number FL.PPs and pruning time pruned number of FLOPS/ values in Appendix ! For additional details on the experimental set-up, see Appendix G The code for reproducing all experiments is available at
LeNet on MNIST We pre-train LeNet model on MNIST achieving 97.75% top-1 1 accuracy. We (left). All three vari- ants of our method consistently outperform other baselines, even when reweighting is applied to them, with ASYMINCH ANGE doing the best and LAYERINCHANGE the worst. We observe that reweighting significantly improves the performance of all methods except LAYERGREEDY variants.
prune all layers except the last classifier layer. Results are presented in Figure |
ResNet56 on CIFAR-10 We use the ResNet56 model pre-trained on CIFAR-10 provided in ShrinkBench Blalock et al. 2020). which achieves 92.27% top-1 accuracy. We prune all layers except the last layer in each residual branch, the last layer before each residual branch, and the last classifier layer. Results are presented in Figure [ (middle). The sequential variants of our method perform the best. Their performance is closely matched by LAYERW EIGHTNORM and ACTGRAD (with reweighting) for most compression ratios, except very very large ones. LAYERINCHAME significantly worst here than the sequential variants of our method. This is likely due to the larger number of layers pruned in ResNet56 compared to LeNet (27 vs 4 layers). which increases the effect of pruning earlier layers subsequent ones. Here also reweighting improves the performance of all methods except the LAYERGREEDYFS variants.
performs
VGG11 on CIFAR-10 We pre-train VGG11 model on CIFAR- 10 obtaining 90.11% top-1 accuracy. We prune all layers except the last features layer and the last classifier layer. Results are presented in Figure I (right). The three variants of our method perform the best. Their performance is matched (with reweighting). LAYER to the sequential variants of our method here, even slightly better at compression ratio 32, probably because the number of layers being pruned is again relatively small (9 layers). As before, reweighting benefits all methods except the LAYERGREEDYFS variants.
by ACTGRAD and WAYERWEIGHHNONS
performs similarly
Discussion
We summarize our observations from the empirical results:
Our proposed pruning method outperforms state-of-the-an structured pruning methods in various one shot pruning settings. As expected, ASYMINCHANGE is the best performing variant of our method, and LAYERINCHANGE the worst, with its performance deteriorating with deeper models. Our results also illustrate the robustness of our method, as it reliably yields the best results in various settings, while other baselines perform well in some settings but not in others.
Reweighting significantly improves performance for methods, except LAYER GREEDYFS and LAYERGREEDY We suspect that reweighting does not help in this case because this

---

0.8
0.8
0.8
Toe-3 accuracy
accuracy
accuracy
0.6
TOP-1
0.4
0.4
0.4
0.0
4
3
16
32
64
126
0.0
16
32
64
128
0.0
1
16
32
64
126
compression ratia
compression ratio
compression rati
1.0
AsymerChance
SedtChange
0.8
0.8
Leperectred
Acticsc
0.8
Meprachange
Top-1 arcuracy
0.6
Acttral
Layeth
accuracy
0.6
Lepertampiing
Rander
Actrad
LayethCrange
Loyenilighthooe
Lagar Crowey
Livertanctine
00000
0.4
0.4
Laysstanders
Layenlanders Layertrenles
Layertrennits
0.2
0.2
0.2
0.0
32 compression ratio
4
8
16
64
128
0.0
16 32 compression ratio
64
128
0.0
16
32
64
128
compression ratio
Figure 1: Top-1 Accuracy of different pruning methods applied to LeNet MNIST (left), ResNet56 on CIFARIO (middle), and VGGI on CIFAR 10 (right), for several compression ratios (in log-scale), with (top) and without (bottom) reweighting. We include the three reweighted variants of our method in the bottom plots (faded) for reference.
method already scales the next layer weights, and takes into account this scaling when selecting neurons/channels to keep, replacing it with reweighting hurt performance.
The choice of how much to prune in each layer given global budget can have drastic effect performance, as illustrated in Appendix
Fine-tuning with full-training data boosts performance more than reweighting, while fine-tuning with limited data helps less, as illustrated in Appendix H Reweighting still helps when fine-tuning with limited-data, except for LAYERGREEDYTS variants, but can actually deteriorate perfor- mance when fine-tuning with full-data. Our method still outperforms other baselines after fine- tuning with limited-data, and is among the best performing methods even in the full-data setting.
8 Conclusion
We proposed data-efficient structured pruning method, based on submodular optimization, By casting the layerwise subset selection problem as a weakly submodular optimization problem, we are able to use the GREEDY algorithm to provably approximate it. Empirically, our method consistently outperforms existing structured pruning methods on different network architectures and datasets.
Acknowledgment and Disclosure of Funding
We thank Stefanie Jegelka, Debadeepta Dey, Jose Gallego-Posada for their helpful discussions, and Yan Zhang, Boris Knyazev for their help with running experiments. We also acknowledge the MIT SuperCloud and Lincoln Laboratory Supercomputing Center (supercloud. mit edu). Compute Canada (www. wwwputecanada..cc.ooooooo..ma... ca). Calcul Quebec wwww. www.clqueeec..coooooo ca), WestGrid (www. westgrid. ACENET (ace-net. ca), the Mila IDT team, Idiap Research Institute and Machine Learning Research Group at the University of Guelph, for providing HPC resources that have contributed to the research results reported within this paper. This research was partially supported by the Canada CIFAR AT Chair Program. Simon Lacoste-Julle Julien is CIFAR Associate Fellow in the Learning Machines & Brains program.
10

---

References
A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek. Guarantees for greedy maximization of non-submodular functions with applications. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 198-500.JMMRR org, 2017. (Cited on 22
D. Blalock, J. J. G. Ortiz, J. Frankle, and J. Guttag. What is the state of neural network pruning? arXiv preprint FrXXi:2003.030333 2020. (Cited on
26
C. Bucila, R. Caruana, and A. Niculescu-Mizll Model compression. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '06, page 535-541, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1 1595933395. doi: 10.1 (0.1144/1110 150402. 1550644. URL URLhttts: https: http:::://oo...r////.
org/ 10. 11w...111111100000000 1150464 (Cited
on |
S. Buschjäger, P.-J. Honysz, and K. Morik. Very fast streaming submodular function maximization, 2020. (Cited on 26)
M. D. Collins and P. Kohli. Memory bounded deep convolutional networks. arXiv preprint arXiv:1412.1442, 2014. (Cited on M
M. Courbariaux, Y. Bengio, and J.-P. David. Binaryconnect: Training deep neural networks with binary weights during propagations. In Advances neural information processing systems, pages 3123-3131, 2015. (Cited on
A. Das and D. Kempe. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. arXiv preprint arXiv:1102.3975, 2011. (Cited on
D
M. Denil, B. Shakibi, L. Dinh, M. A. Ranzato, and N. de Freitas. Predicting parameters in deep learning. In C. J. C. Burges, L.. Bottou, M. Welling, Z. Ghahramani, and K. Q Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Cur- Associates, Inc., 2013. URL https: httttp::/pproceednngg nwwrinur..... wiw.ips.ccm httpiips.cpppppee pccpppp///21///lee (Cited on
/fec306d1 Beco/cdde66bbb////6222222222
pdf
M. El Halabi, F. Bach, and V. Cevher. Combinatorial penalties:
Structure preserved by convex relaxations. Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, 2018 (Cited on 2
E. Elenberg, R. Khanna, weak submodularity. arXiv preprint
Dimakis, and Negahban. Restricted strong convexity implies 2016. (Cited on 3
16
Y. Gong, L. Liu, M. Yang, and L.. Bourdev. Compressing deep convolutional networks using vector quantization. arXiv preprint arXiv:1412.611 2014. (Cited on [
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016. (Cited on
He, Y. Fan, Y. Qian, Tan, and K. Yu. Reshaping deep neural network for fast decoding by node-pruning In 20/4 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 245-249 IEEE, 2014. (Cited on
Y. He, X. Zhang, and J. Sun. Channel pruning for accelerating very deep neural networks. In Proceedings of the IEEE international conference on computer vision, pages 1389-1397, 2017. (Cited on
G. Hinton, O. Vinyals, and J. Dean. Distilling the knowledge in neural network. Neural Information Processing Systems (NeurIPS) Workshops, 2015. (Cited on T
T. Hoefler, D. Alistarh, T. Ben-Nun, N. Dryden, and A. Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. arXiv preprint arXiv:2 102.00544, 2021. (Cited on 2
11

---

A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009. (Cited on
A. Kuzmin, M. Nagel, S. Pitre, S. Pendyam, T. Blankevoort, and M. Welling. Taxonomy and evalua- tion of structured compression of convolutional neural networks. arXiv preprint 1rX0v:111..09802, 2019. (Cited 7
V. Lebedev, Ganin, M. Rakhuba, Oseledets, and V. Lempitsky. Speeding-up convolutional neural networks using fine-tuned cp-decomposition. In International Conference on Learning Representations, 2015. (Cited on
Y. LeCun, B. Boser, S. Denker, Henderson, R. E. Howard, W. Hubbard, and L.. D. Jackel. Backpropagation applied to handwritten zip code recognition. Neural computation, 1(4):541-551, 1989. (Cited on
Y. Lecun, C. Cortes, and C. Burges. The mnist databaseof handwritten digits, 1998. (Cited on y
B. Lehmann, D. Lehmann, and N. Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55(2):270-29) 296, 2006. (Cited on 22
H. Li, A. Kadav, I. Durdanovic, H. Samet, and H. P. Graf. Pruning filters for efficient convnets. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26. 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https://oppnreviiii net/
forum?gd-xJqFOTsLg (Cited on
W. Li, M. Feldman, Kazemi, and Karbasi. Submodular maximization in clean linear time, 2022.
URL https::/t///st:t wwwparwwww.....iiia..ee.ee...eee Bargg/abs//0 abob 093227 (Cited on 15 30
L. Liebenwein, C. Baykal, H. Lang, D. Feldman, and D. Rus. Provable filter pruning for efficient neural networks. In International Conference on Learning Representations, 2020. URL https
//openreview.o www.tetefoouneee dddmeiidddBxBD- (Cited on 5
26
J. Luo, J. Wu, and W. Lin. Thinet: A filter level pruning method for deep neural network compression. In Proceedings of the IEEE international conference on computer vision, pages 5058-5066, 2017. (Cited on 2
Z. Mariet and S. Sra. Diversity networks: Neural network compression using determinantal point processes. arXiv preprint arXiv:1511.05077 2015. (Cited on
K. McGuffie and Newhouse. The radicalization risks of gpt-3 and advanced neural language models. arXiv preprint arXiv:2009.0680) 2020. (Cited on
B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi, J. Vondrák, and A. Krause. Lazier than lazy greedy, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015. (Cited on S
20
P. Molchanov, S. Tyree, T. Karras, T. Aila, and J. Kautz. Pruning convolutional neural networks for resource efficient inference. ICLR, 2017. (Cited on
B. Mussay, M. Osadchy, V. Braverman, S. Zhou, and Feldman. Data-independent neural pruning via coresets. In International Conference on Learning Representations, 2020. URL. https
//openreview.o wwt.:neetnrme.... hww.forrmmid-Heeeii.e Hd=HHgdHaEKHH (Cited on 5
//ppereevee..ee//oorrmm
B. Mussay, D. Feldman, S. Zhou, V. Braverman, and M. Osadchy. Data-independent structured pruning of neural networks via coresets. IEEE Transactions on Neural Networks and Learning Systems, pages 1-13, 2021. doi: 10.1109/TNNL
(Cited on 5
B. K. Natarajan. Sparse approximate solutions to linear systems. SIAM journal on computing, 24(2): 227-234, 1995. (Cited on
G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of approximations for maximizing submodular set functions - I. Mathematical Programming, 14(1):265-294, 1978. (Cited on
A. Paszke, S. Gross, S. Chintala, G. Chanan, Yang, DeVito, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer. Automatic differentiation in pytorch. 2017. (Cited on 26
12

---

H. Phan. huyviphan/pytorch. cifar10, 1, Jan. 2021. URL https://do1.org/10.. 001p:/10.5281/200000 1431043 (Cited on 26
K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. In Y. Bengio and Y. LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL
attp://arxiv wweeziivv.rrroooooooooo argg/bs//444 1e0ss/149.... 1556 (Cited on
S. Srinivas and R. V. Babu. Data-free parameter pruning for deep neural networks. In Proceedings of the British Machine Vision Conference (BMVC), pages 31.1-31.12. BMVA Press, September 2015. (Cited on 2
Su, Li, B. Bhattacharjee, and F. Huang. Tensorial neural networks: Generalization of neural networks and application to model compression. arXiv preprint wrXiv:1805.10333 2018. (Cited on
M. Sviridenko, J. Vondrák, and J. Ward. Optimal approximation for submodular and supermodular optimization with bounded curvature. Mathematics of Operations Research, 42944:1197-12118
2017. (Cited on 22 23
E. Voita, D. Talbot, F. Moiseev, R. Sennrich, and I. Titov. Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned. In Proceedings of the 57th Anmual Meeting of the Association for Computational Linguistics, pages 5797-5808, 2019. (Cited on !
M. Ye, C. Gong, L. Nie, D. Zhou, A. Klivans, and Q. Liu. Good subnetworks provably exist: Pruning greedy forward selection. ICML, 2020a. (Cited on
M. Ye, L. Wu, and Q. Liu. Greedy optimization provably wins the lottery: Logarithmic number of winning tickets is enough. Advances in Neural Information Processing Systems, 33:16409-11620,
2020b. (Cited on 2 g 15
Z. Zhuang, M. Tan, B. Zhuang, Liu, Y. Guo, Q. Wu, Huang, and J. Zhu. Discrimination-awwac channel pruning for deep neural networks. S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianche and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31, Curran Associates, Inc., 2018, URL httptttpppppoeeeeeeteeeep
neur neurips cc/paper/ pdf
(Cited on
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We specify that our focus is on the limited-data regime in both the abstract and introduction. See also the discussions on lines 143-151 and 207-213 on when our approximation guarantee is non-zero, and on lines 173-181 the cost of our method.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] We include the code with instructions on how reproduce all our experimental results in the supplemental material.
13

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section and Appendix G
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix G
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See Appendix G
(b) Did you mention the license of the assets? [Yes] The license of the assets we used are included in the code provide.
(c) Did you include any assets either in the supplemental material URL? [Yes]
We include our code in the supplemental material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "hSqN-Vyj3E6", "reviewer": "Reviewer_aJkM", "summary": "The paper proposes a neural network node pruning method and shows that the objective is essentially a form of weakly-submodular function optimization. Therefore, the pruning of a single layer can be solved using the greedy algorithm with a theoretical guarantee. The paper also shows that using a limited number of data, the proposed method is able to achieve the best performance compared to baselines.", "questions": "1. Can authors estimate the weakly-submodular factors gamma in the experiments and report the corresponding guarantees? Can authors also discuss high tight are the estimates of such factors provided in Proposition 3/4?\n\n2. Can authors provide wall clock running time of the optimization algorithm on the experiments and discuss the limitations of the complexity?\n\n3. For multiple layer pruning, it seems that the changes of one layer could affect the pruning of other layers. Can the authors provide some insights about the empirical behaviors of convergence of the proposed methods?", "limitations": "Yes.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper draws a very intriguing and solid connection between neural network pruning and submodular optimization. More specifically, the weakly-submodular optimization factor is closely related to the activation matrix.\n\n2. The paper studies the problem in a comprehensive manner, including pruning of regular regions of neurons, strategies of pruning multiple layers, and speed-up tricks for the submodular optimization.\n\n3. The proposed method empirically achieves the best performance compared to baselines on some network structures under a limited number of samples.\n\nWeaknesses:\n1. The proposed approach has relatively high computational complexity. It seems that scaling would be a problem for scenarios such as larger network structures or utilizing a large number of data samples for pruning.\n\n2. Given the limitation of the complexity, I guess that the empirical experiments could be hardly extended to more complex datasets (e.g., ones with larger image dimensions) or larger network structures.\n\n3. The proposed framework only works for one layer. For pruning of multiple layers the paper proposes some heuristics.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hNvFdOJVlM", "reviewer": "Reviewer_455Y", "summary": "This paper propose a network pruning approach via sub modular optimization. The proposed method uses a greedy fashion to layer-wisely select neuron that improves the performance most. This paper shows that the returned solution given by the greedy algorithm is able to well approximate the optimal solution (of a NP hard problem). To reduce the cost, a computation-saving approach is also proposed. Empirical results shows that the approach is able to achieve good performance when the available training data at pruning is small.", "questions": "See above.", "limitations": "Yes", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall I find this paper quite interesting, especially its performance when there is limited number of training data at pruning. The theoretical guarantee is also stronger and does not require stronger assumptions. However, I do have some concerns:\n\n1. It seems the proposed method in general is very similar to Ye at al.. Both methods are greedy forward selection and the different seems subtle. Could you give more discussion in terms of methodology?\n\n2. Following up Q1, it seems that an main improvement over Ye at al is to reduce the computation cost. However, [1] also propose a new technical to reduce the cost and I was wondering how does your method compares with [1]?\n\n3. What would max_{|S|\\le k} F(S) looks like? I understand that it is NP hard but it would be interesting to show how this quantities looks like.\n\n4. Can we empirically verify the \\gamma_{U,k} as this is an important quantity?\n\n[1] Greedy Optimization Provably Wins the Lottery: Logarithmic Number of Winning Tickets is Enough\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hI64rsShb4j", "reviewer": "Reviewer_9DXV", "summary": "Goal: effective and efficient structured pruning of a pre-trained NN-network if only small amount of unlabeled training data is available\n\nContributions: \n1) The authors propose a new technique (called \"principled data-efficient structured pruning\") that alters the existing  \"reweighting\" method [Mariet and Sra, 2015]. Unlike [Mariet and Sra,2015]:\n     * submodular optimization ... they  formulate the subset selection problem of  structured pruning as a weakly submodular maximization problem  and solve it approximately by greedy search\n     * extended pruning: pruning of regular regions of neurons (e.g., channels) and three strategies for pruning of multliple layers \n     * limited number of training data (cca. 1% of the original training data) with no labels and one-shot pruning (without fine-tuning)\n2) Theoretical justification of the method and its performance (in the Supplementary material).\n3) Experimental evaluation of a solid scope with promising results.\n", "questions": "1. In the abstract,  you write that \"current structured pruning methods do not provide any performance guarantees\". Later on, e.g., on lines 75-78,  you mention one such method. You should add something like \"most of\" into the abstract to be fair. \n\n2. To confirm the novelty of your method, it would be nice to analyze in a more concrete way, what the  [Mariet and Sra,2015] method uses instead of submodular optimization and greedy search. Did you compare your approach to  [Mariet and Sra,2015]  exactly?", "limitations": "OK: The authors try to analyze both strengths and limitations of the paper in the experimental part.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths (significance and quality):\n1) The problem of effective structured pruning of a pre-trained NN-network in the presented limited-data regime is important. Most of the existing structured pruning techniques require greater amount of training data and fine-tuning to work well. The proposed method (or even its particular parts) appears to be a valuable contribution with this respect.   \n2) The experimental evaluation of a solid scope offers promising (outstanding and stable) results.\n3) Theoretical performance guarantee.\n4) The authors try to be fair in their comparisons with concurrent techniques (e.g. the application of reweighting, various parameter settings...) and analyze also the weaknesses of their method.\n\nClarity:\n1) The submission is relatively clearly written and easy to read (except the theoretical parts and the figures). If there was enough place, I would prefer to move more experimental results from the supplementary into the main paper.  The figures (e.g. Figure 1) are small and less comprehensible. It would maybe help to scale the graphs differently, to highlight the variants of the proposed method or to change the used colors. \n\nNovelty:\n1) The novelty of the contribution is slightly limited. The proposed method is based on previous work by [Mariet and Sra,2015]. The original method is altered using the principles of submodular optimization to be advantageous in the new context of  limited-data. \n2) The related work is cited and addressed adequately. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "03JakGViR7", "reviewer": "Reviewer_ULbp", "summary": "The authors propose a layerwise pruning method that formulates the problem of eliminating neurons as a weakly submodular optimization problem for which the well-known greedy algorithm gives an approximation guarantee.  They illustrate the practical performance of three different variants of their strategy when extended to prune the entire network on a variety of tasks.", "questions": "It would be nice to see some discussion of the practical computational cost among the various methods in the main text.  While I don't see the cost of this method as overly limiting, it is nice to get a sense of how taxing the methods really are. \n\nAlso, some thoughts about why the approach seems to do much better in some regimes while only comparable in others?", "limitations": "Some limitations were discussed, though I don't see the focus on the data limited regime as a limitation of the methodology necessarily.  Or am I missing something important?", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The idea of formulating the pruning problem to take advantage of weak submodularity is novel to me.  Although it does build somewhat crucially on existing work.\n\nQuality:  The technical and experimental results seem to be well-executed to the best of my assessment.  One can always add more competitors and try on a wider variety of architectures, but I found the selected experiments to be illustrative and compelling.\n\nClarity:  The exposition was clear overall though I found Figure 1 tough to read even after significant zooming.\n\nSignificance:  While it may be more expensive than some other approaches, the cost of this procedure is typically only born once.  So, I can see this as being a very useful tool in practice and may spur pruning research in novel directions.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept