Advancing Model Pruning via Bi-level Optimization
Authors: Yihua Zhang
Yuguang Yao
Parikshit Ram
Pu Zhao
Tianlong Chen
Mingyi Hong
Yanzhi Wang
Sijia Liu
Venue: NeurIPS 2022 Accept (2022)
Keywords: pruning
bi-level optimization

Abstract: The deployment constraints in practical applications necessitate the pruning of large-scale deep learning models, i.e., promoting their weight sparsity. As illustrated by the Lottery Ticket Hypothesis (LTH), pruning also has the potential of improving their generalization ability. At the core of LTH, iterative magnitude pruning (IMP) is the predominant pruning method to successfully find ‘winning tickets’. Yet, the computation cost of IMP grows prohibitively as the targeted pruning ratio increases. To reduce the computation overhead, various efficient ‘one-shot’ pruning methods have been developed, but these schemes are usually unable to find winning tickets as good as IMP. This raises the question of how to close the gap between pruning accuracy and pruning efficiency? To tackle it, we pursue the algorithmic advancement of model pruning. Specifically, we formulate the pruning problem from a fresh and novel viewpoint, bi-level optimization (BLO). We show that the BLO interpretation provides a technically-grounded optimization base for an efficient implementation of the pruning-retraining learning paradigm used in IMP. We also show that the proposed bi-level optimization-oriented pruning method (termed BiP) is a special class of BLO problems with a bi-linear problem structure. By leveraging such bi-linearity, we theoretically show that BiP can be solved as easily as first-order optimization, thus inheriting the computation efficiency. Through extensive experiments on both structured and unstructured pruning with 5 model architectures and 4 data sets, we demonstrate that BiP can find better winning tickets than IMP in most cases, and is computationally as efficient as the one-shot pruning schemes, demonstrating $2-7\times$ speedup over IMP for the same level of model accuracy and sparsity.

Advancing Model Pruning via Bi-level Optimization
Yihua Zhang
Yuguang Yao!
Parikshit Ram?
Pu Zhao
Tianlong Chen'
Mingyi Hong
Yanzhi Wang"
Sijia Liu
'Michigan State University. IBM Research, 'Nottheaster University, *University of Texas at Austin, University of Minnesota, Twin Cities "qqual contribution
Abstract
The deployment constraints in practical applications necessitate the pruning of large-scale deep learning models, i.e., promoting their weight sparsity. As illus- trated by the Lottery Ticket Hypothesis (LTH), pruning also has the potential of improving their generalization ability. At the core of LTH, iterative magnitude pruning (IMP) is the predominant pruning method to successfully find 'winning tickets'. Yet, the computation cost of IMP grows prohibitively as the targeted pruning ratio increases. To reduce the computation overhead, various efficient 'one-shot' pruning methods have been developed but these schemes are usually unable to find winning tickets as good as IMP. This raises the question of how to close the gap between pruning accuracy and pruning efficiency? To tackle it, we pursue the algorithmic advancement of model pruning. Specifically, we formulate the pruning problem from a fresh and novel viewpoint, bi-level optimization (BLO). We show that the BLO interpretation provides technically-grone grroundd optimization base for an efficient implementation of the pruning suuiingrettaining learning paradigm used in IMP. We also show that the proposed bi-level crtimization-oriente pruning method (termed B1P) is a special class of BLO problems with a bi-linear problem structure. By leveraging such bi-linearity, theoretically show that BIP be solved as easily as first-order optimization, thus inheriting the computation efficiency. Through extensive experiments both structured and unstructured pruning with model architectures and data sets, we demonstrate that BIP can find better winning tickets than IMP in most cases, and computationally as efficient as the one-shot pruning schemes, demonstrating 2-7x speedup over IMP for the same level of model accuracy and sparsity. Codes available httpss///gihuubb.cm//PPP/
Introduction
While over- parameterized structures are key to the improved generalization of deep neural networks (DNNs) [I, they create new problems- the millions or even billions of parameters not only increase computational costs during inference, but also pose serious deployment challenges on resource-limited devices (4. As result, model pruning has seen a lot of research interest in recent years, focusing on reducing model sizes by removing (or pruning) redundant parameters 8). Model sparsity (achieved by pruning) also benefits adversarial robustness [9, out-of-distribution generalization [10), and transfer learning []. Some pruning methods (towards structured sparsity)
facilitate model deployment on hardware 12 13
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Among various proposed model pruning algorithms [S 27], the heuristics based Iterative Magnitude Pruming (IMP) is the current dominant approach to achieving model sparsity without suffering performance loss, as suggested and empirically justified by the Lottery Ticket Hypothesis
(L.TH) [7]. The L.TH hypothesizes the existence of a subnetwork (the so-called 'winning ticket")
when trained in isolation (e.g., from either random initialization [17] or an early-rewinding point of
dense model training [19), can match the performance of the original dense model [S] (7 [7]
The core idea of IMP is to iteratively prune and retrain the model while progressively pruning a small ratio of the remaining weights in each iteration, and continuing till the desired pruning ratio has been reached. While IMP often finds the winning ticket, it incurs the cost of repeated model retraining from scratch, making it prohibitively expensive for large datasets or large model architectures [28 22 To improve the efficiency of model pruning, numerous heuristics based one-shot pruning methods [1
21 25 e.g. one-shot magnitude pruning (OMP), have been proposed. These schemes directly prune the model to the target sparsity and are significantly more efficient than IMP. Yet, the promise of current one-shot pruning methods is tottaset/model-specfff [22] 30 and
mostly lies in the low pruning ratio regime [25]. As systematically studied in (22 (1], there exists
a clear performance gap between one-shot pruning and IMP, As an alternative to heuristics-based
schemes, optimization-based pruning methods p 15
26 27 still follow the pruning-retraining paradigm and adopt sparsity regularization 32 3 or parameterized masking [9] T6 27 to prune
16
models efficiently. However, these methods do not always match the accuracy of IMP and thus have not been widely used to find winning tickets [17 21 23 25 22)] The empirical results showing that
optimization underperforms heuristics motivate us to revisit the algorithmic fundamentals of pruning.
To this end, we put forth a novel perspective of model pruning as bi-level optimization (BLO) problem. In this new formulation, we show that BLO provides a Sehhiicallyggounddee optimization basis for an efficient
96.0
95.5
Dense Model
IMP
BiP (ours)
E95.
ResNet-18
294.5
[
94.0
implementation of the pruning-retrainngg paradigm, the key algorithmic component used in IMP. To the best of our knowledge, we make the first rigorous connec- tion between model pruning and BLO. Technically, we propose a novel bi-level optimization-enalle pruning method (termed BıP) We further show how BiP takes advantage of the bi-linearity of the pruning problem to avoid the computational challenges of common BL.O methods, and is as efficient as any first-order alternating optimization scheme. Practically, we demonstrate the superiority of the proposed BiP in terms of accuracy, sparsity, and computation efficiency through extensive experiments. BıP finds the best winning ticket nearly in all settings while taking time comparable to the one-shot OMP. In Fig. I. we present a snapshot of our empirical results for CIFAR- 10 with 3 ResNet architectures at 74% pruning ratio. In all cases, B1P (+) finds winning tickets, improving accuracy over the dense model (o) and matching IMP ), while being upto 5x faster than IMP.
93..5
ResNet-56
93.0
_ 92.5
92.0
ResNet-20
91.5%
100
200
300
400
500
(min)
Figure 1: A performance snapshot of the pro- posed BiP method vs. the IMP bascline and the original dense model across three pruned ResNet models (ResNet-20, ResNet-56, and ResNet- 18) with 74% sparsity CIFAR-10. The marker size indicates the relative model size. The uni- color region corresponds to the same model type used by different pruning methods.
Our contributions can be summarized as follows:
(Formulation) We rethink the algorithmic foundation of model pruning through the lens of BLO (bi-level optimization). The new BLO-oriented formulation disentangles pruning and retraining variables, providing the flexibility to design the interface between pruning and retraining.
(Algorithm) We propose the new bi-level pruning (BıP) algorithm, which is built upon the aforemen- tioned BLO formulation and the implicit gradient-based optimization theory. Unlike computationally intensive standard BLO solvers, we thcorctically show that BIP is as efficient as any first-order optimization by taking advantage of the bi-linear nature of the pruning variables.
(Experiments) We conduct extensive experiments across datasets (CIFAR-10. CIFAR-100, Tiny- ImageNet and ImageNet), 5 model architectures, and 3 pruning settings (unstructured pruning, filter-wise structured pruning, and channel-wise structured pruning). We show that (i) BiP achieves higher test accuracy than IMP and finds the best winning tickets nearly in all settings, (ii) BIP is highly efficient (comparable to one-shot pruning schemes), that is able to achieve 2-7x speedup over IMP for the same level of model accuracy and sparsity, and (ii) BIP is able to find subnetworks that achieve better performance than the dense model regardless of initialization rewinding.
2

---

2 Related Work and Open Question
Neural network pruning. As neural networks become deeper and more sophisticated, model pruning technology has gained increasing attention over the last decade since pruned models are necessary for the deployment of deep networks in practical applications [4 33 35]. With the goal of finding highly-sparse and highly-accuran of pruning methods have been developed such heuristics-based pruning 17 21
subnetworks from original dense models, a variety
23
25 29
36
and optimization- based pruning 16
26 [7]. The former identifies redundant model weights by 22
leveraging heuristics- basse metrics such as weight magnitudes 17 19
37 31
36 (8),
gradient magnitudes [21 23 24
39
40) and Hessian statistics 441 1 The latter is typically built on:
1) sparsity-promoting optimization [5 33 47450), where model weights are trained by penalizing
their sparsity-inducin norms, such as to and & norms for irregular weight pruning, and & norm for structured pruning: 2) parameterized masking [16] 9 55) where model weight scores optimized to filter the most important weights and achieve better performance.
Iterative vs. one-shot pruning, and motivation. Existing schemes can be further categorized into one-shot or iterative pruning based on the pruning schedule employed for achieving the targeted model sparsity. Among the iterative schemes, the IMP (Iterative Magnitude Pruning scheme) [17 20 [6
651 [6]] has played a significant role in identifying high-quality 'winning tickets', as postulated
by LTH (Lottery Ticket Hypothesis) [18 19]. To enable consistent comparisons among different
methods, we extend the original definition of winning tickets in [17] to 'matching subnetworks' [20]
so to cover different implementations of winning tickets, e.g., the use of early-epoch rewinding for
model re-initialization [18] and the no-rewinding (i.e., fine-tuning) variant [66]. Briefly, the matching
subnetworks should match or surpass the performance of the original dense model [2].. In this work,
if a matching subnetwork is found better than the winning ticket obtained by the same method that
follows the original LTH setup [88 19], ticket throughout the paper.
we will also call such matching subnetwork a winning
For example, the current state-of-the- art (SOTA) implementation of IMP in
10"
92
Spornng
Time Consumption (min)
90
[2) can lead a pruned ResNet-20 on CIFAR-10 with 74% sparsity and
88
Dense Model
92.12% test accuracy, matching the per- formance of the original dense model (see red * in Fig. Left). The IMP algo- rithm typically contains two key ingre- prun- ing schedule to progressively increase model sparsity over pruning iterations, and (ii) the pruning- retrainng learning mechanism applied at each pruning iter- ation. With a target pruning ratio of p% with T pruning iterations, an example pruning schedule in (i) could be as follows - each iteration prunes (p%)** // of the currently unpruned model weights, progressively pruning fewer weights in each iteration. For (ii), the unpruned weights in each pruning iteration are re-set to the weights at initialization or at an early-training epoch [8] and re-trained till convergence. In brief, IMP repeatedly prunes, resets, and trains the network over multiple iterations.
86
CMP
10
3 surr titse
Graup
Snip
SynFlow
80
40
60
80
100
20
40
60
80
100
dients: (i) a temporally-evolve
Pruning Rabio (%)
Pruning (96)
Figure Illustration of the pros and cons of different pruning methods executed over (ResNet-20,, CIFAR-10). Left: test ac- curacy vs. different pruning ratios of IMP and one-shot pruning methods (OMP [77. GRASP 2 SNIP 20, SYNFLOOw (24 Right: comparison of the efficiency with different sparsity.
However, winning tickets found by IMP incur significant computational costs. The sparsest winning ticket found by IMP in Fig. Left (red *) utilizes 7 = 6 pruning iterations. As shown in Fig. Right, this takes 3x more time than the original training of the dense model. To avoid the computational cost of IMP, different kinds of "accelcrated" pruning methods were developed [17] 21 23/25) (2)] and many fall into the one-shot pruning category: The network is directly pruned to the target sparsity and retrained once. In particular, OMP (one-shot magnitude pruning) is an important baseline that simplifies IMP [7]. It follows the pruning-retrainin retraining paradigm, but prunes the model to the target ratio with single pruning iteration. Although one-shot pruning schemes are computationally cheap (Fig-2 Right,, they incur a significant accuracy drop compared to IMP ( Even if IMP is customized with reduced number of training epochs per pruning round, the pruning accuracy also drops largely (see Fig. A2). Hence, there is need for advanced model pruning techniques to find winning tickets like IMP, while being efficient like one-shot pruning.
3

---

Different from unstructured weight pruning described above, structured pruning takes into consid- eration the sparse patterns of the model, such as filter and channel-win -wiee pruning [3
48
5T
67
71] Structured pruning is desirable for deep model deployment in the presence of hardware con- straints 4 [4]. However, compared to unstructured pruning, maintain the performance and find structure- winning tickets [28] 29).
usually more challenging to
Open question. As discussed above, one-shot pruning methods are unable to match the predic- tive performance of IMP, and structure-aware winning tickets are hard to find. Clearly, the best optimization foundation of model pruning is underdeveloped. Thus, we ask:
Is there an optimization basis for successful pruning algorithm that can attain high pruned model accuracy (like IMP) and high computational efficiency (like one-shot pruning)?
The model pruning problem has a natural hierarchical structure prune model parameters, and then, given the mask, find the best model weights for the unpruned model parameters. Given this hierarchical structure, we believe that the bi-level optimization (BI.O) framework is one promising optimization basis for a successful pruning algorithm.
need find the best mask to
Bi-level optimization (BLO). BLO a general hierarchical optimization framework. where the upper-level problem depends on the solution to the lower-level problem. Such a nested structure makes the BLO in its most generic form very difficult to solve, since it hard to characterize the influence of the lower-level optimization on the upper-level problem. Various existing literature focuses on the design and analysis of algorithms for various special cases of BLO. Applications range from the classical approximate descent methods (72-74], penalty- -baed methods [75] 766.. to recent BigSAM [77] and its extensions 778 79). It is also studied in the area of stochastic algorithms (80-82) and backapropagation based algorithms (83885) BLO has also advanced adversarial training (86). meta-learning [87). data poisoning attack generation [8), neural architecture search [89] as well as reinforcement learning [90]. Although BLO was referred in (50) for model pruning, it actually called an ordinary alternating optimization procedure, without taking the hierarchical learning structure of BLO into consideration. To the best of our knowledge, the BLO framework has not been considered for model pruning in-depth and systematically. We will show that model pruning yields a special class of BLO problems with bi-linear optimization variables. We will also theoretically show that this specialized BLO problem for model pruning can be solved as efficiently as first-order optimization. This is in a sharp contrast existing BLO applications that rely on heuristics-based BLO solvers (e.g., gradient unrolling in meta learning (87 and neural architecture search 88 91)).
3 BIP: Model Pruning via Bi-level Optimization
In this section, we re-investigate the problem of model pruning through the lens of BLO and develop the bi-level pruning (BIP) algorithm. We can theoretically show that BiP can be solved as easily as the first-order alternating optimization by taking advantage of the bi-linearity of pruning variables.
BLO viewpoint on model pruning As described in the previous section, the pruning- learning paradigm covers two kinds of tasks: 1 pruning that determines the sparse pattern of model weights, and training remaining non-zero weights to recover the model accuracy. In existing optimization-based pruning methods 95) the tasks 1-@ are typically achieved by optimizing model weights, together with penalizing their sparsity-inducing norms, e.g., the & and &g norms (6] Different from the above formulation, we propose to separate optimization variables involved in the pruning tasks and @ This leads to the (binary) pruning mask variable m E {0, 13"" and the model weight variable 0 RT. Here n denotes the total number of model parameters. Accordingly, the pruned model is given by (m @ 0). where C denotes the element- teinenttwisseee multiplication. As will be evident later, this form of variable disentanglement enables us to explicitly depict how the pruning and retraining process co-evolve, and helps customize the pruning task with high flexibility.
We next elaborate on how BLO can be established to co-optimize the pruning mask m and the retrained sparse model weights 0. Given the pruning ratio p%, the sparsity constraint is given by m E S, where S {ml m E {0, 13", 1" 1nmm < k] and k (1 - p%)n. Our goal is to prune the original model directly to the targeted pruning ratio p% (i.e., without calling for the IMP-like sparsity schedule as described in Sec. 2) and obtain the optimized sparse model (m @ 0). To this

---

end, we interpret the pruning task (i.e., and the model retraining task (i.e., 2 as two optinization levels, where the former is formulated as an upper-level optimization problem, and it relies on the optimization of the lower-level retraining task. We thus cast the model pruning problem as the following BLO problem (with @ being nested inside 1):
g
minimize mES
c(m @ O (m)))
subject to 0 (m) = arg min {m @ 0) OER"
1011 2
Pruning usk
@: Spunsty-fixed model retraining
where e denotes the training loss (e.g., cross- cooss-nntrppy,, m and O are the upper-level and lower-level optimization variables respectively, 0* (mm) signifies the lower-level solution obtained by minimizing the objective function 9 given the pruning mask m, and 7 > O is a regularization parameter introduced to convexify the lower-level optimization so as to stabilize the gradient flow from 0 (mm) to m and
thus the convergence of BLO 82 197. In sharp contrast to existing single-level optimization-base model pruning methods
952 the BLO formulation T brings in two advantages.
First, BLO has the flexibility to use mismatched pruning and retraining objectives at the upper and lower optimization levels, respectively. This flexibility allows us regularize the lower-level training objective function in (T) and customize the implemented optimization methods at both levels. To be more specific, one can update the upper-level pruning mask m using a data batch (called B²) distinct from the one (called B1) used for obtaining the lower-level solution 0* (m). The resulting BLO procedure can then mimic the idea of meta learning to improve model generalization 198) where the
lower-level problem fine-tunes O using B1, and the upper-level problem validates the generalization of the sparsity- -aware finetuned model (m @ 0* (m) using B2.
Second, BLO enables us to explicitly model and optimize the coupling between the retrained model weights 0" (m) and the pruning mask m through the implicit gradient (IG)-based optimization routine. Here IG refers to the gradient of the lower-level solution 0" (m) with respect to (w.r.t)) the upper-level variable m. and its derivation calls the implicit function theory (76). The use of IG makes our proposed BLO-oriented pruning (I) significantly different from the greedy alternating minimization [99] that learns the upper-level and lower-level variables independently (i.e., minimizes one variable by fixing the other). We refer readers to the following section for the detailed IG theory. We will also show in Sec. F the pruning strategy from ① can outperform IMP many pruning scenarios but is much more efficient as it does not call for the scheduler of iterative pruning ratios.
Optimization foundation of BıP. The key optimization challenge of solving the BIP problem lies in the computation of IG (implicit gradient). Prior to developing an effective solution, first elaborate on the IG challenge, the unique characteristic of BLO. In the context of gradient descent, the gradient of the objective function in ( yields
dm @ 0 (m)) (m O O" (m))
d(0"(m)
Vol(m 0" (m)))
dmn
dmn
Gradicet ebjective
where mm and Ve denote the partial derivatives of the bi-vari function 8(m c 0) w.r.t. the variable m and 0 respectively, d0 /dm R=*x denotes the vector-wise full derivative, and for ease of notation, we will omit the transpose T when the context is clear. In (2). the IG challenge refers to the demand for computing the full gradient of the implicit function O* (m) = arg ming g (m, 0) w.r.t.
m, where recall from (1 that g(m, 0) == f(m @ 0) 10 1/
Based on the fact that 0 (m) satisfies the stationarity condition for the lower-level objective function in (2) it is not difficult to obtain that (see derivation in Appendix(A) A)
Next, we derive the IG formula following the rigorous implicit function theory 76
82
d0'(m) V e (m 0' (')[V 0*) +)++++++
dm
where 2 e
l and V3dl denote the second-order partial derivatives of l respectively, and (-)-1 denotes the matrix inversion operation.
Yet, the exact IG formula (3) remains difficult to calculate due to the presence of matrix inversion and second-order partial derivatives. To simplify it, we impose the Hessian-free assumption, V = O, which is mild in general; For example, the decision boundaries of neural networks with ReLU
5

---

activations are piece-wise linear in tropical super-surface [100], and this assumption has been widely used in BLO-involved applications such as meta learning [TOT] and adversarial learning [86]. Given og = O, the matrix inversion in (3) can be then mitigated, leading to the IG formula
dl (m)
V mo 0*))
(4)
dm
At the first glance, the computation of the simplified IG (4) still requires the mixed (second-order) partial derivative V m.f. However, BiP a special class of BLO problems with bi-linear variables (m @ 0). Based on this bi-linearity, we can prove that IG in 4 can be analytically expressed using
only first-order derivatives; see the following theorem.
Proposition 1 Assuming eige and defining Val(z) Vz((z) |x moo the implicit gradient is then given by
(m)
- diagg(
dm
Further, the gradient of the objective function given by (2 becomes
dē(m 0-) -0 vz((z)) Va((z),
(6)
dm where @ denotes the element-wist multiplicattin.
Proof: Using chain-rule, we can obtain that Vol(m @ 0*) diag(m)
@ Va((z);
(7)
similarly, mm @ 0*) diag(0") Vv = @ V.((z)
(8)
where diag(-) represents a diagonal matrix with being the main diagonal vector. Further, we can convert
me 8 0') m @ Vz((z)) chain rale diag V (z)())) (iaa
diagg( Vxf(z)) diag(m) (ding( (diag("") [z)) diag((a((())
where the last equality holds due the Hessian-free assumption. With 9 and can prove (5)
Next, substituting the ( to the upper-level gradient
we obtain that
dé(m @ 0*) dm
((m 0*) Vel(z) Vol(m c 0*)
(z) (m Vz((z)) = (0" -.mm Vzl(z)) @ Va((z),
which leads to 6 The proof is complete.
The key insight drawn from Prop. that the bi- bi-linearity of pruning variables (i.e., @ 0*) makes the IG-involved gradient (2) easily sol and the computational complexity is almost the same as that of computing the first-order gradient (z((z) just once, as supported by 6
BIP algorithm and implementation. We next formalize the BIP algorithm based on Prop. and the alternating gradient descent based BLO solver (22 At iteration t, there are two main steps.
* Lower-level SGD for model retraining: Given m (t-1), (t+-1), and (t-1) m (c-1) @ (((-1) update ((t) by randomly selecting a data batch with the learning rate a and applying SGD (stochastic gradient descent) the lower-level problem of (I).
00 (-1) [Ve((m ((-11)
0 "fm" (1-1
Val(K) x= ( + " (0-step)
Upper-level SPGD for pruming: Given m (t-1), (( and z (1+1/2) = m (t-1) o ((1), we update using SPGD (stochastic projected gradient descent) along the IG-enhanced descent direction (
dd(mm g())
m
=Ps (0
m (t-1)
m=
dm
Ps m (1-1) 3 (0)0
(1-1) Vzf(z) (11/2 @ Vv((z) (-200)122)) (m-step)

---

Original
Prior Iterative Magnitude Pruning (IMP) over Rounds
Pruned
Rewind
Prune pilns
Prune
Train
Round 1
Round
Round T
Original
Our proposal: Bi-level Pruning (BiP) directly to pruning ratio p%
Pruned
Upper level
Upper level
Upper level
Prine epoch SPGD
spoch SPGD
epoch SPGD
Pretrained Model
Sparse Model
Train weights Luooch
Train weights spoch
weights
Lower level
Lower level
Lower level
Figure 3:
Visualization of pruning pipeline comparison between IMP and BiP. Edge refers to the mask update and color refers the weight update.
where 3 is the upper-level learning rate, and Ps(-) denotes the Euclidean projection onto the constraint set S given by S {m
{0, 1)", 1'm m s k3] in ( and is achieved by the top-k
hard-thresholding operation as will be detailed later.
In BIP, the (0-step) and (m-step) steps execute iteratively. For clarity, Fig. shows the difference between the pruning pipelines BiP and IMP. contrast to IMP that progressively prunes and retrains model with a growing pruning ratio, BTP directly prunes the model to the targeted sparsity level without involving costly re- re-training process. In practice, we find that both the upper- and lower- level optimization routines of BıP converge very well (see Fig. [A12 and Fig.A13 A13). It also worth noting that both (0-step) and (m-step) only require the first-order information V VzE(2) (Z). demonstrating
that BIP can be conducted as efficiently as first-order optimization. In Fig. Al we highlight the
algorithmic details on the BIP pipeline. We present more implementation details of BIP below and refer readers to Appendix for detailed algorithm description.
Discrete optimization over m: We follow the 'convex relaxation + hard thresholding' mechanism used in [9 [6]. Specifically, we relax the binary masking variables to continuous masking scores m E (0, 1.. We then acquire loss gradients the backward pass based on relaxed m. At forward pass, we project it onto the discrete constraint set S using the hard thresholding operator, where the top elements are set to and the others to Os. See Appendix B for more discussion.
Data batch selection for lower-level and upper-level optimization: We adopt different data batches (with the same batch size) when implementing (0-step) and (m-step). This one of the advantages of the BLO formulation, which enables the flexibility to customize the lower-level and upper-level problems. The use of diverse data batches is beneficial to generalization as shown in (98)
Hyperparameter luming: As described in (m-step)-mm-step) and 3 for lower-level and upper-level optimization, respectively. We choose
(m-step), BIP needs to set two learning rates a
0.01 and 8 = 0.1 in all experiments, where we adopt the mask learning rate 33 from Hydra (9) and set a smaller lower-level learning rate a, as 0 is initialized by a pre- pre-trained dense model. We show ablation study on a in A8 c)). BLO also brings in the low-level convexification parameter y. We set 7 1.0 in experiments and refer readers Fig (b) for a sanity check.
One-step vs. multi-step SGD: In (t-step), the one-step SGD is used and helps reduce the computa- tion overhead. In practice, also find that the one-step SGD is sufficient: The of multi-step SGD in B1P does not yield much significant improvement over the one-step version; see Fig A8 a).
Extension to structured pruming: We formulate and solve the BIP problem in the context of unstructured (element-wise) weight pruning. However, define the pruning mask m w.r./. model's structural units (e.g., g., filters), BIP is easily applied to structured pruning (see Fig and Fig. A10).
7

---

CIFAR-IG, RaNNa-1
CHEAR- 10, ReoNe-20
(1AR-11 RoNNs-16
CHHAR 10, VOG-16
$6.5
8.1.5
45.0
33.5
$1.0
62.1
$3.0
90.5
900
$25g
Prusing Bulo (99)
Praning Rusio (5)
Prazing Ratio (%)
Prezsin Rutio (56
16.0
70.0
Tay- Tmp--mayyNuu,
ImageNas,
640
17.5
17.0
16.
666.0
42.
75.0
75.6
14.0
12.0g
100
23
40
50
100
5%%
20
40
60
90
100
125
50
10
100
Prusing Ruds
Prastng
Prasing
Prezing
Figure 4: Unstructured pruning trajectory given by test accuracy (%) vs. sparsity (%) on various dataset- model
pairs. The proposed BiP is compared with HYDRA (9). IMP 22 OMP (22.. GRASP 23 And the performance of dense model and that of the best winning ticket marked using dashed lines in each plot. The solid line and shaded area of each pruning method represent the mean and variance of test accuracies over independent trials. We observe that B1P consistently outperforms the other baselines. Note in the (ImageNet, ResNet-50) setting, we only compare B1P with our strongest bascline IMP due to computational resource constraints.
Experiments
In this section, we present extensive experimental results to show the effectiveness of BiP across multiple model architectures, various datasets, and different pruning setups. Compared to IMP, one-shot pruning, and optimization- -ased pruning baselines, we find that BıP can find better winning tickets in most cases and is computationally efficient.
4.1 Experiment Setup
Datasets and models. Following the pruning benchmark in (22. we consider 4 datasets including CI [T02) CIFAR- 100 [102], Tiny-ImageNet
[03). ImageNet [104, and 5 architecture types
including Res55t-20/6611 8/55 and VGG-16 105 106 Tab. A1 summarizes these datasets and
model configurations and setups.
Baselines, training, and evaluation. As baselines, we mainly focus on 4 SOTA pruning methods, ① IMP [17] @ OMP [17). 3 GRASP (23) (a one-shot pruning method by analyzing gradient flow at initialization), and ④ HYDRA [9] (an optimization- -based pruning method that optimizes masking scores). worth noting that there exist various implementations of IMP, e.g., specified
by different learning rates and model initialization or 'rewinding' strategies [18] To make fair
comparison, we follow the recent IMP benchmark in 22], which can find the best winning tickets over current heuristics- based pruning baselines. We also remark that HYDRA is originally proposed for improving the adversarial robustness a pruned model, but it can be easily customized for standard pruning when setting the adversary's 's strength as O [9. We choose HYDRA as baseline because can be regarded as a single-level variant BIP with post-optimization weight retraining. When implementing BiP, unless specified otherwise, use the 1-step SGD in (O-step). and set the learning rates (a, 9) and the lover-level regularization parameter y as described in the previous section. When implementing baselines, of all methods mainly from two perspectives: (1) the test accuracy of the sub-network, and (2) the runtime of pruning to reach the desired sparsity. We refer readers Tab.[A3 and Appendix C.2 for more training and evaluation details, such as training epochs and learning rate schedules.
follow their official repository setups. We evaluate the performance
4.2 Experiment Results
BIP identifies high-accuracy subnetworks. In what follows, we look at the quality of winning tickets identified by BiP. Two key observations can drawn from our results: (1) BiP finds winning tickets of higher accuracy and/or higher sparsity than the basclines in most cases (as shown in Fig
8

---

Table 1:
The sparsest winning tickets found by different methods at different data-mode setups. Winning tickets refer to the sparse models with average accuracy no less than the dense model 20). In each cell, p% std%) represents the sparsity as well as the test accuracy. The test accuracy of dense models can be found in the header. X signifies that no winning ticket is found by a pruning method. Given the data-model setup (i.e. per column). the sparsest winning ticket is highlighted in bold.
CIFAR-10
CIFAR-100
Method
18
Re (92.125)
ReaNet-56
VGG-16
ReaNes118 (76
ResNei-20 (68 69%
(94.77%)
(92.95%)
(90,65%)
IMP
(96.7710, 10%)
(51.150)))5)
(92 0: 128))
87% (76.91
OMP
(96,5010. 10%)
(93, 0.0%)
(76.991007))
GRASP
HYDRA
(33)73
20% (.79))
8IP
895 (94.7H0 158)
675 (92. 14 1599
74% (-0035))
936 (93 75:0 1966)
89% (76.0+001889
49% 78-0 10%)
95.5
76.0
70.6
RoeNes20
$5.0
92.0
71.0
C.4.0
54.5
5.000
25.0
65.00
$3.5
24.
33.55
IN7
23.0
42.0
Crey
30.0
91.%
20
40
100
12.0g
25
100
750
20
40
50
190
45.5g
40
50
50
100
Prusiig Radi
Prasing
Prasing (%4
Preszng
Figure 6: Filter pruning given by test accuracy (%) vs. pruning ratio (%). The visual presentation setting is the We observe that BIP identifies winning tickets of structured pruning in certain sparsity regimes.
same as Fig. 4
and Tab. D (2) The superiority of BiP holds for both unstructured pruning and structured pruning (as shown in Fig. O and A10). We refer to more experiment results in Appendix C.3
Fig. 4 shows the unstructured pruming trajectory (given by test accuracy vs. pruning ratio) of BıP and baseline methods in 8 model-dataset setups. For comparison, we also present the performance of the original dense model. As we see, the proposed BTP approach finds the best winning tickets (in terms of the highest accuracy) compared to the baselines across all the pruning setups. Among the baseline methods, IMP is the most competitive method to ours. However, the improvement brought by BIP is significant with respect to the variance of IMP, except for the 60%-80% sparsity regime in (CIFAR-10, ResNet-20). In the case of (CIFAR-100, ResNet-20), where IMP can not find any winning tickets (as confirmed by (22)) ), BIP still manages to find winning tickets with around 0.6% improvement over the dense model. In Tab.[ we summarize the sparsest winning tickets along the pruning trajectory identified by different pruning methods. BIP can identify the winning tickets with higher sparsity levels than the other methods, except in the case of (CIFAR-10, 10, ResNet-20).
Fig. demmonsraass the structured pruming trajectory on the CIFAR-10/100 datasets. Here we focus on filter prun- ing, where the filter is regarded as a masking unit in ( Fig.ATO0 We refer readers Fig. [A10 for channel-wise pruning re- sults. Due to the page limit, we only report the results of the filter-wise pruning in the main paper and please refer to Appendix(C.3 for channel-wist pruning. Com- pared Fig. Fig. shows that it becomes more difficult to find winning tickets of high accuracy and sparsity in the structured pruning, and the gap among different meth- ods decreases. This is not surprising, since filter pruning imposes much stricter pruning structure constraints than irregular pruning. However, BIP still outperforms all the baselines. Most importantly, it identifies clear winning tickets in the low sparse regime even when IMP fails.
10²
Dense Model
Time Consumption (min)
Hydra
IMP
Grasp
BiP
10a
20
40
80
100
Pruning Ratio (%)
Figure 5: Time consumption comparison on (CIFAR- 10, ResNet-18) with different prun- ing ratio p.
BiP is computationally efficient. In our experiments, another key observation is that BIP yields sparsity-agnostic runtime complexity while IMP leads to runtime exponential to the target sparsity. Fig. 5 shows the computation cost of different methods versus pruning ratios on (CIFAR-10, 10, ResNet- 18). For example, BIP takes 86 mins to find the sparsest winning ticket (with 89% sparsity in Tab I This yields 7x less runtime than IMP, which consumes 620 mins to find a comparable winning ticket with 87% sparsity. Compared to the optimization-basel baseline HYDRA, BIP is more efficient it

---

93.0
CIFAR1O, ResNet20s
95.4
CI R B
77.75
CIF ResNet18
77.50
295.
92.0
77.25
95.0
77,00
91.0
94.8
76.75
90.5
94.6
76.25
90.0
Desse Model
-7
942
DEMoE Model
2-677255
76.00
Danse Modd
p-67.3 7.2%
p-20%
p- 96. 58%
p-215%
p-85. 58%
75.75
p-20%%
p-55
89.0 NIA
5%
10%
50%
75%
100%
94.0
N/A
N/A
5%
10%
50%
75%
100%
N/A
5%
10%
50%
75%
100%
Rewinding Epoch Number
Rewirding Epoch Number
Rewinding Epoch Number
Figure 7: The sensitivity of BiP rewinding epoch numbers different datasets and model architectures. "N/A" the x-axis indicates BiP without retraining.
does not rely on the extra post-optimization retraining; see Tab. A2 for detailed summary of rumtime and number of training epochs required by different pruning methods. Further, B1P takes about 1.25 x more computation time than GRASP and OMP. However, the latter methods lead to worse pruned model accuracy, demonstrated by their failure to find winning tickets in Tab. Fig, 4 and Fig. 6
BIP requires no rewinding. Another advantage of BiP is that it insensitive to model rewinding to find matching subnetworks. Recall that rewinding is strategy used in LTH 19] determine what model initialization should be used for retraining a pruned model. As shown in 22 an IMP-identified winning ticket could be sensitive the choice of rewinding point. Fig- Ssows the test accuracy of the BiP-pruned model when it is retrained at different rewinding epochs under various datasets and model architectures, where 'N/A' in the x-axis represents the case of no retraining (and thus no rewinding). As we can see, a carefully-tune improvement over BiP without retraining. This suggests that the subnetworks found by BiP are already of high quality and does not require any rewinding operation.
rewinding scheme does not lead to a significant
C.3 In particular, we show Additional results. We include more experiment results in Appendix more results in both unstructured and structured pruning settings in Fig. A4
A5g A6
Fig. A7 where we compare BIP with more baselines and cover more model architectures. also study the sensitivity of BIP to the lower-level step number, lower-level regularization coefficient, the significance of the implicit gradient term (2). learning rate, and batch size, as shown Fig. and Fig-A9) To demonstrate the convergence of the upper-level and lower-level optimization in BTP, we show the training trajectory of B1P for accuracy (Fig (A1) and mask score (Fi) and show how the lower-level step number affects the convergence speed (Fig. [A1)). Further, we show the performance of BıP vs. the growth of training epochs (Fig. A15). and its performance vs. different data batch schedulers (see A16)
5 Conclusion
We proposed the BIP method to find sparse networks through the lens of BLO. Our work advanced the algorithmic foundation of model pruning by characterizing its pruning-retraining hierarchy using BLO. We theoretically showed that BiP can be solved as easily as first-order optimization by exploiting the bi-linearity of pruning variables. We also empirically showed that BIP can find high-quality winning tickets very efficiently compared to the predominant iterative pruning method. In the future, we will seek the optimal curriculum of training data at different optimization levels of BiP, and will investigate the performance of our proposal for actual hardware acceleration.
Acknowledgement
The work of Y. Zhang, Y. Yao, and S. Liu was supported by National Science Foundation (NSF) Grant 11S-2207052. The work of M. Hong was supported by NSF grants CIF-19 and CMMI-1727757. The work of Y. Wang was supported NSF grant CCF-191911 1919117. The computing resources used in this work were also supported by the MIT-IBM Watson AI Lab, IBM Research and the Institute for Cyber-Enabled Research (ICER) at Michigan State University.
10

---

References
[1] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton, "Imagenet classification with deep convolutional neural networks," in Advances in neural information processing systems, 2012,
pp. 1097-1105.
[2] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al., 'Language models are few-shot learners," Advances neural information processing systems, vol. 33, pp. 1877-1901, 2020.
[3] Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin, "Deep learning: a statistical viewpoint," Acta numerica, vol. 30, pp. 87-201, 2021.
[4] Song Han, Huizi Mao, and William J Dally, "Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding," arXiv preprint arXiv:1510.0014,, 2015.
[5] Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag, "What is the state of neural network pruning?," arXiv preprint arXiv:2003.0300 2020.
[6] Song Han, Jeff Pool, John Tran, and William Dally, "Learning both weights and connections for efficient neural network," Advances in neural information processing systems, vol. 28, 2015.
[7] Yihui He, Ji Lin, Zhijian Liu, Hanrui Wang, Li-Jia Li, and Song Han, "Ame: Automl for model compression and acceleration on mobile devices." in Proceedings of the European conference on computer vision (ECCV), 2018, pp.
[8] Huizi Mao, Song Han, Jeff Pool, Wenshuo Li, Xingyu Liu, Yu Wang, and William J Dally, "Exploring the granularity of sparsity in convolutional neural networks," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, 2017, pp. 13-20.
[9] Vikash Sehwag, Shiqi Wang, Prateek Mittal, and Suman Jana, "Hydra: Pruning adversarially robust neural networks," " Advances in Neural Information Processing Systems, vol. 33, pp. 19655-19666, 2020.
[10] James Diffenderfer, Brian Bartoldson, Shreya Chaganti, Jize Zhang, and Bhavya Kailkhura, "A winning hand: Compressing deep networks can improve out-o--distributiin robustness," Advances in Neural Information Processing Systems, vol. 34, pp. 664 676, 2021.
[11] Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Michael Carbin, and Zhangyang Wang. "The lottery tickets hypothesis for supervised and self-supervised pre-training in computer vision models," in Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2021, pp. 16306-16316.
[12] Xiaolong Ma. Fu-Ming Guo. Wei Niu. Xue Lin, Jian Tang, Kaisheng Ma, Bin Ren, and Yanzhi Wang, "Pconv: The missing but desirable sparsity in dnn weight pruning for real-time execution on mobile devices," " in Proceedings of the AAAI Conference on Artificial Intelligence 2020, vol. 34, pp. 5117-5124.
[13] Tianlong Chen, Xuxi Chen, Xiaolong Ma, Yanzhi Wang, and Zhangyang Wang, "Coarsening the granularity: Towards structurally sparse lottery tickets," " arXiv preprint arX1v:2202.04736. 2022.
[14] Yann LeCun, John Denker, and Sara Solla, "Optimal brain damage," Advances in neural information processing systems, vol. 2, 1989.
[15] Ao Ren, Tianyun Zhang. Shaokai Ye, Jiayu Li. Wenyao Xu, Xuchai Qian, Xue Lin, and Yanzhi Wang, "Admm-nn: An algorithm-hardwant co-design framework of dans using alternating direction method of multipliers." 2018.
[16] Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari, "What's hidden in a randomly weighted neural network?," in Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2020, pp. 11893-11902.
11

---

[17] Jonathan Frankle and Michael Carbin, "The lottery ticket hypothesis: Finding sparse, trainable neural networks," arXiv preprint arXiv:1803.036:3. 2018.
[18] Alex Renda, Jonathan Frankle, and Michael Carbin, "Comparing rewinding and fine-tuning in neural network pruning." " in 8th Internaiional Conference on Learning Representations, 2020.
[19] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy. and Michael Carbin, "Linear mode connectivity and the lottery ticket hypothesis," in International Conference on Machine Learning. PMLR, 2020, pp. 3259-3269.
[20] Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Zhangyang Wang. and Michael Carbin, "The lottery ticket hypothesis for pre-trained bert networks," Advances in neural information processing systems, vol. 33, pp. 15834-15846, 2020.
[21] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr, "Snip: Single-shot network pruning based on connection sensitivity," arXiv preprint 1rXiv:1810002344, 2018.
[22] Xiaolong Ma. Geng Yuan, Xuan Shen, Tianlong Chen, Xuxi Chen, Xiaohan Chen, Ning Liu, Minghai Qin, Sijia Liu, Zhangyang Wang, et al., "Sanity checks for lottery tickets: Does your winning ticket really win the jackpot?," arXiv preprint arXiv:2107.00166 2021.
[23] Chaoqi Wang, Guodong Zhang, and Roger Grosse, "Picking winning tickets before training by preserving gradient flow," arXiv preprint arXiv:2002.07376, 2020.
[24] Hidenori Tanaka, Daniel Kunin, Daniel Yamins, and Surya Ganguli, "Pruning neural networks without any data by iteratively conserving synaptic flow," Advances in Neural Information Processing Systems, vol. 33, pp. 6377-6389, 2020.
[25] Milad Alizadeh, Shyam A. Tailor, Luisa M Zintgraf, Joost van Amersfoort, Sebastian Farquhar, Nicholas Donald Lane, and Yarin Gal, "Prospect pruning: Finding trainable weights at initialization using meta-gradients," in International Conference on Learning Representations, 2022.
[26] Jaeho Lee, Sejun Park, Sangwoo Mo, Sungsoo Ahn, and Jinwoo Shin, "Layer-adaptive sparsity for the magnitude-based pruning," arXiv preprint arXiv:2010.07611 2020.
[27] Róbert Csordás, Sjoerd Steenkiste, and Jürgen Schmidhuber, "Are neural nets modu- lar? inspecting functional modularity through differentiable weight masks," arXiv preprint arXiv:2010.02066 2020.
[28] Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Richard G Baraniuk, Zhangyang Wang, and Yingyan Lin, "Drawing early-bird tickets: Towards more efficient training of deep networks," arXiv preprint arXiv: 1957, 2019.
[29] Zhenyu Zhang, Xuxi Chen, Tianlong Chen, and Zhangyang Wang, "Efficient lottery ticket finding: Less data is more," in International Conference on Machine Learning. PMLR, 2021, pp. 12390-12390.
[30] Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang. and Jason D Lee, "Sanity-checking pruning methods: Random tickets can win the jackpot," Advances Neural Information Processing Systems, vol. 33, pp. 11390-20401,, 2020.
[31] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin, "Prun- ing neural networks at initialization: Why are we missing the mark?"" arXiv preprint 1-XXiv2009.08570 2020.
[32] Sijia Liu, Parikshit Ram, Deepak Vijaykeerthy, Djallel Bouneffouf, Gregory Bramble, Horst Samulowitz, Dakuo Wang, Andrew Conn, and Alexander Gray, "An ADMM based framework for automl pipeline configuration," 2019.
[33] Huan Wang, Can Qin, Yulun Zhang, and Yun Fu, "Neural pruning via growing regularization," arXiv preprint ar 202.22001..99243. 2020.
12

---

[34] Misha Denil, Babak Shakibi, Laurent Dinh, Mare' Aurelio Ranzato, and Nando De Freitas, "Predicting parameters in deep learning," Advances in neural information processing systems, vol. 26, 2013.
[35] Sijia Liu, Pin- Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred Hero III, and Pramod Varshney, "A primer on zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications." IEEE Signal Processing Magazine, vol. 37, no. 5, pp. 43-54, 2020.
[36] Michael Zhu and Suyog, Gupta, "To prune, or not to prune: exploring the efficacy of pruning for model compression." arXiv preprint arXiv:1710.01878, 2017.
[37] Steven Janowsky. "Pruning versus clipping in neural networks," Physical Review A, vol. 39, no. 12, pp. 6600, 1989.
[38] Alexandra Peste, Eugenia Iofinova, Adrian Vladu, and Dan Alistarh, "Ac/de: Alternating compressed/dccomprssedd training of deep neural networks," Advances in Neural Information Processing Systems, vol. 34, pp. 8557-8570, 2021.
[39] Michael C Mozer and Paul Smolensky, "Skeletonization: A technique for trimming the fat from a network via relevance assessment," in Advances in neural information processing systems, 1989, pp. 107-115.
[40] Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen, "Rigging the lottery: Making all tickets winners," in International Conference Machine Learning. PMLR, 2020, pp. 2943-2952.
[41] Pavlo Molchanov, Arun Mallya, Stephen Tyree, luri Frosio, and Jan Kautz, "Importance estimation for neural network pruning," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019, pp. 11264-11272.
[42] Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W Mahoney, "Pyhessian: Neural networks through the lens of the hessian," " in 2020 IEEE International Conference on Big Data (Big Data). IEEE, 2020, pp. 581-590.
[43] Yann LeCun, John Denker, and Sara Solla, "Optimal brain damage." in Advances in neural information processing systems, 1990, pp. 598-605.
[44] Babak Hassibi and David G Stork, Second order derivatives for network pruning: Optimal bruin surgeon, Morgan Kaufmann, 1993.
[45] Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz, "Pruning convo- lutional neural networks for resource efficient inference," arXiv preprint 1:Xvv:661.006400 2016.
[46] Sidak Pal Singh and Dan Alistarh, "Woodfisher: Efficient second-ordes approximation for neural network compression." Advances in Neural Information Processing Systems, vol. 33, pp. 18098-1810% 2020.
[47] Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang, "Learning efficient convolutional networks through network slimming," in Proceedings of the IEEE International Conference on Computer Vision, 2017, pp- 2736-2744.
[48] Yihui He, Xiangyu Zhang, and Jian Sun, "Channel pruning for accelerating very deep neural networks." " in Proceedings of the IEFE international conference on computer vision, 2017, pp. 1389-1397.
[49] Hao Zhou, Jose M Alvarez, and Fatih Porikli, "Leess is more: Towards compact cnns," in European Conference on Computer Vision. Springer, 2016, pp. 662-6777
[50] Christos Louizos, Max Welling, and Diederik Kingma, "Leerrnng sparse neural networks through (_0 regularization," arXiv preprint arXiv:1712.01312,, 2017.
13

---

[51] Yi Guo, Huan Yuan, Jianchao Tan, Zhangyang Wang, Sen Yang, and Ji Liu, "Gdp: Stabilized neural network pruning via gates with differentiable polarization," in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021, pp- 0p39-29-5250
[52] Edgar Liberis and Nicholas D Lane, "Differentiable network pruning for microcontrollerss" arXiv preprint 10.08350, 2021.
[53] Aditya Kusupati, Vivek Ramanujan, Raghav Somani, Mitchell Wortsman, Prateek Jain, Sham Kakade, and Ali Farhadi, "Soft threshold weight reparameterization for learnable sparsity," in International Conference on Machine Learning. PMLR, 2020, pp. 5544-5555.
[54] Chao Xue, Xiaoxing Wang, Junchi Yan, Yonggang Hu, Xiaokang Yang. and Kewei Sun, "Rethinking bi-level optimization in neural architecture search: A gibbs sampling perspective." in Proceedings of the AAAI Conference on Artificial Intelligence, 2021, vol. 35, pp. 10551-
10559.
[55] Xiao Zhou, Weizhong Zhang, Hang Xu, and Tong Zhang, "Effective sparsification of neural networks with global sparsity constraint," " Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 3599-3608.
[56] Trevor Gale, Erich Elsen, and Sara Hooker, "The state of sparsity in deep neural networks," arXiv, vol. abs/1902.09574, 2019.
[57] Zhenyu Zhang. Xuxi Chen, Tianlong Chen, and Zhangyang Wang, "Efficient lottery ticket finding: Less data is more," in Proceedings of the 38th International Conference Machine Learning, Marina Meila and Tong Zhang, Eds. 18-24 Jul 2021, vol. 139 Proceedings of Machine Learning Research, pp. 12380-12333 PMLR.
[58] Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Michael Carbin, and Zhangyang Wang, "The lottery tickets hypothesis for supervised and self-supervised pre-training in computer vision models," arXiv preprint arXiv:2012.06900 2020.
[59] Haonan Yu, Sergey Edunov, Yuandong Tian, and Ari S. Morcos, "Playing the lottery with rewards and multiple languages: lottery tickets in rl and nip." in 8th International Conference on Learning Representations, 2020.
[60] Xuxi Chen, Zhenyu Zhang, Yongduo Sui, and Tianlong Chen, "(GAN)s Is can play lottery tickets too," in International Conference on Learning Representations, 2021.
[61] Haoyu Ma, Tianlong Chen, Ting-Kuei Hu, Chenyu You, Xiaohui Xie, and Zhangyang Wang, "Good students play big lottery better." arXiv preprint arX1v:2101.03255, 2021.
[62] Zhe Gan, Yen-Chun Chen, Linjie Li, Tianlong Chen, Yu Cheng. Shuohang Wang, and Jingjing Liu, "Playing lottery tickets with vision and language," arXiv preprint arXiv:2104.1 18332. 2021.
[63] Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. "A unified lottery ticket hypothesis for graph neural networks," arXiv preprint arXiv:2102.06790, 2021.
[64] Neha Mukund Kalibhat, Yogesh Balaji, and Soheil Feizi, "Winning lottery tickets in deep generative models." 2021.
[65] Tianlong Chen, Yu Cheng, Zhe Gan, Jingjing Liu, and Zhangyang Wang. "Ultra-date efficient gan training: Drawing a lottery ticket first, then training it toughly," arXiv preprint arXiv:2103.00397 2021.
[66] Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang, "Long live the lottery: The existence of winning tickets lifelong learning." " in International Conference on Learning Representations, 2020.
[67] Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf, "Pruning filters for efficient convnets," arXiv preprint 1rXiv:1608.08710,.00 2016.
14

---

[68] Wei Niu, Xiaolong Ma, Sheng Lin, Shihao Wang, Xuehai Qian, Xue Lin, Yanzhi Wang, and Bin Ren, "Patdnn: Achieving real-time dnn execution on mobile devices with pattern- based weight pruning." in Proceedings of the Twenty-Figh International Conference Architectrall Support for Programming Languages and Operating Systems, 2020, pp. 907-922.
[69] Xiaolong Ma, Wei Niu, Tianyun Zhang, Sijia Liu, Sheng Lin, Hongjia Li, Wujie Wen, Xiang Chen, Jian Tang, Kaisheng Ma, et al., "An image enhancing pattern-based sparsity for real-time inference mobile devices," in European Conference on Computer Vision. Springer, 2020,
pp. 629-645.
[70] Jingyu Wang, Songming Yu, Zhuqing Yuan, Jinshan Yue, Zhe Yuan, Ruoyang Liu, Yanzhi Wang. Huazhong Yang. Xueqing Li, and Yongpan Liu, "Paca: A pattern pruning algorithm and channel-fused high pe utilization accelerator for cnns," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022.
[71] Joost van Amersfoort, Milad Alizadeh, Sebastian Farquhar, Nicholas Lane, and Yarin Gal, "Single shot structured pruning before training." arXiv preprint arXiv:2007.00389, 2020.
[72] James E Falk and Jiming Liu, "On bilevel programming, part i: general nonlinear cases," Mathematical Programming, vol. 70, no. 1. pp. 47-72, 1995.
[73] Luis Vicente, Gilles Savard, and Joaquim Júdice, "Descent approaches for quadratic bilevel programming." Journal of Optimization Theory and Applications, vol. 81, no. 2, pp. 379-399, 1994.
[74] Can Chen, Xi Chen, Chen Ma, Zixuan Liu, and Xue Liu, "Gradient-based bi-level optimization for deep learning: A survey," arXiv preprint arXiv:2207.11719, 2022.
[75] Douglas! White and G Anandalingam, "A penalty function approach for solving bi-level linear programs," Journal of Global Optimization, vol. no. pp. 397-419, 1993.
[76] Stephen Gould, Basura Fermando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo, "On differentiating parameterized argmin and argmax problems with application to bi-level optimization," arXiv preprint 1rXiv::607.008
2016.
[77] Shoham Sabach and Shimrit Shtern, "A first order method for solving convex bilevel optimiza- tion problems," " SIAM Journal on Optimization, vol. 27, no. 2, pp. 640-660, 2017.
[78] Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang, "A generic first- order algorithmic framework for bi-level programming beyond lower-level singleton," " in International Conference on Machine Learning. PMLR, 2020, pp. 6305-6315.
[79] Junyi Li, Bin Gu, and Heng Huang, "Improved bilevel model: Fast and optimal algorithm with theoretical guarantee," arXiv preprint arXiv:2009.000 00690, 2020.
[80] Saeed Ghadimi and Mengdi Wang, "Approximation methods for bilevel programming." arXiv preprint arXiv:1802.00 02246, 2018.
[81] Kaiyi Ji, Junjie Yang, and Yingbin Liang, "Bilevel optimization: Nonasymptotic analysis and faster algorithms." " arXiv preprint arXiv:2010.07962, 2020.
[82] Mingyi Hong. Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang, "A two-timescale framework for bilevel optimization: Complexity analysis and application actor-critic," arXiv preprint arXiv:2007.051100 2020.
[83] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil, "Forward and reverse gradient-based hyperparameter optimization," in International Conference on Machine Learning. PMIR, 2017, pp. 1163-1173.
[84] Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo, "On the iteration complexity hypergradient computation." in International Conference on Machine Learning. PMLR, 2020, pp. 3748-3758.
15

---

[85] Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots, "Truncated back- propagation for bilevel optimization." " in The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019, pp. 1723-1732.
[86] Yihua Zhang, Guanhuan Zhang, Prashant Khanduri, Mingyi Hong. Shiyu Chang, and Sijia Liu, "Revisiting and advancing fast adversarial training through the lens of bi-level optimization," arXiv preprint arXiv:21 12. 12376, 2021.
[87] Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine, "Meta-learning with implicit gradients." in Advances in Neural Information Processing Systems, 2019, pp.
113-124.
[88] W Ronny Huang, Jonas Geiping, Liam Fowl, Gavin Taylor, and Tom Goldstein, "Metapoison: Practical ceneral-purpose clean-label data poisoning." arXiv preprint arXiv:2004.00225 2020.
[89] Hanxiao Liu, Karen Simonyan, and Yiming Yang, "Darts: Differentiable architecture search," arXiv preprint arXiv: 09055, 2018.
[90] Zhangyu Chen, Dong Liu, Xiaofei Wu, and Xiaochun Xu, "Research on distributed renewable energy transaction decision-making based on multi-agent bilevel cooperative reinforcement learning." " 2019.
[91] Xuefei Ning, Tianchen Zhao, Wenshuo Li, Peng Lei, Yu Wang, and Huazhong Yang, "Dsa: More efficient budgeted pruning via differentiable sparsity allocation," in European Conference on Computer Vision. Springer, 2020, pp. 592-607.
[92] Wei Wen, Chumpeng Wu, Yandan Wang, Yiran Chen, and Hai Li, "Learning structured sparsity in deep neural networks," Advances in neural information processing systems, vol. 29, 2016.
[93] Tianyun Zhang, Shaokai Ye, Kaiqi Zhang. Jian Tang, Wujie Wen, Makan Fardad, and Yanzhi Wang. "A systematic dnn weight pruning framework using alternating direction method of multipliers." " in Proceedings of the European Conference on Computer Vision (ECCV), 2018,
pp. 184-199.
[94] Torsten Hoeferr Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste, "Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks." Journal of Machine Learning Research, vol. 22, no. 241, pp. 1-124, 2021.
[95] Hao Wang, Xiangyu Yang. Yuanming Shi, and Jun Lin, "A proximal iteratively reweighted approach for efficient network sparsification," IEEE Transactions on Computers, vol. 71, no. 1, pp. 186,196,70 2020.
[96] Francis Bach, Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski, et al., "Optimization with sparsity-inducinn penalties," Foundations and Trends@ in Machine Learning, vol. 4, no.
1. pp. 1-106, 2012.
[97] Uri Shaham, Yutaro Yamada, and Sahand Negahban, "Understanding adversarial train- ing: Increasing local stability of neural nets through robust optimization," " arXiv preprint 0rXiv:1511.054333 2015.
[98] Xiang Deng and Zhongfei Mark Zhang, "Is the meta-learning idea able to improve the generalization of deep neural networks on the standard supervised learning?," in 2020 25th International Conference on Pattern Recognition (ICPR). IEEE, 2021, pp. 150-157.
[99] Imre Csiszár, "Information geonetry and alternating minimization procedures," Statistics and decisions, vol. 1, pp. 205-237, 1984.
[100] Motasem Alfarra, Adel Bibi, Hasan Hammoud, Mohamed Gaafar, and Bernard Ghanem, "On the decision boundaries of neural networks: A tropical geometry perspective." arXiv preprint 2xiv:20002008838 2020.
[101] Chelsea Finn, Pieter Abbeel, and Sergey Levine, "Model-agnostic meta-learning for fast adaptation of deep networks," arXiv preprint 1003000000 2017.
16

---

[102] A. Krizhevsky and G. Hinton, "Learning multiple layers of features from tiny images," Master's thesis, Department of Computer Science, University of Toronto, 2009.
[103] Ya Le and Xuan Yang, "Tiny imagenet visual recognition challenge." CS 231N, vol. no.
pp. 3, 2015.
[104] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei, "Imagenet: A large- scale hierarchical image database," in Computer Vision and Pattern Recognition, 2009. CVPR 2009, IEEE Conference on. IEEE, 2009, pp. 248-255.
[105] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun, "Deep residual learning for image recognition." " in Proceedings the IEEE conference on computer vision and pattern recognition, 2016, pp. 770-778.
[106] Karen Simonyan and Andrew Zisserman, "Very deep convolutional networks for large-scale image recognition," arXiv preprint arXiv:1409, 1556, 2014.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes]. [No], or [N/A] . You are strongly encouraged to include a justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section.
Did you include the license the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
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] See See C.4
(C) Did you discuss any potential negative societal impacts of your work? [Yes] See
Cec
(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] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See Section 3 and Appendix(A
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See supplemen- tal material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? (Yes] See Sec.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Sec.
(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 Table|A2]
4. If you using existing assets (c.g., code, data, models) or curating/releasing assets...
17

---

(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No] The licences of used datasets provided in the cited references
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] Our code is included in the supplementary material
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
18


Reviews:
[{"review_id": "cQiBjp_bI0P", "reviewer": "Reviewer_cu5X", "summary": "This paper aims to solve unstructured pruning as a bi-level optimization problem. To find pruning masks and values of unpruned weights, they define bi-level equations and perform two SGD-processes iteratively. Their goal is proposing a new method that can show comparable accuracy as IMP(iterative magnitude-based pruning) with restricted training time. ", "questions": "- How about bringing the Appendix B (including Figure A1) to the main manuscript? At the first time, it was a little hard to understand the overview of this method.  \n- I don’t understand why LTH is referred as  a pruning method. As far as I understand, the LTH paper just used the magnitude-based pruning method for finding winning-tickets. LTH paper is a novel paper to represent why we train the over-parameterized neural networks, not represent a new pruning method. I think IMP with gradual pruning rates was proposed in Zhu’s paper (described below).\nWhy are the below papers not mentioned in this paper? There have been many other results on unstructured pruning methods.\n  - Zhu, Michael, and Suyog Gupta. \"To prune, or not to prune: exploring the efficacy of pruning for model compression.\" arXiv preprint arXiv:1710.01878 (2017).\n  - Evci, Utku, et al. \"Rigging the lottery: Making all tickets winners.\" International Conference on Machine Learning. PMLR, 2020.\nSidak Pal Singh and Dan Alistarh. Woodfisher: Efficient second-order approximation for neural network compression. Conference on Neural Information Processing Systems (NeurIPS), 33, 2020.\n  - Peste, Alexandra, et al. \"Ac/dc: Alternating compressed/decompressed training of deep neural networks.\" Advances in Neural Information Processing Systems 34 (2021): 8557-8570.\n", "limitations": "- This paper argues for an unstructured pruning method, but there is a critical issue on the unstructured pruning. I think this paper has no/less consideration on that.\n- The experimental designs are so restricted. It should be extended to other challenging datasets and architectures.\n", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- For unstructured pruning of DNNs, this paper defines a bi-level optimization problem and shows theoretical contents for that.\nThis paper shows the comparable results of this method using various dataset and architectures.\n- The compression (including re-training) time is not increased with various pruning rates.\n\n### Weaknesses\n- I have a concern on the real effectiveness of unstructured pruning. As many papers have been mentioned, there is no realistic acceleration method for unstructured pruning due to random locations of unpruned weights. There is no note for this widely-known problem. Even though this method is a novel idea for unstructured pruning, we cannot use this method for our inference. When using CSR formats (ex. cusparse library in CUDA), we must need higher pruning rates to gain faster inference speed. I think that problem is why there have been a few studies on unstructured pruning these days unlike structured pruning.\n- In this aspect, this method can achieve outperformed results on lower pruning rates less than 50%. But, there is less noticeable improvement on effective pruning rates. So, in my opinion, the resulting accuracy seems to be not the main contribution of this paper. \nMoreover, the experimental results seem to be so restricted. We are living in 2022 and the neural networks have evolved since Song Han’s magnitude-based pruning. I don’t think the results on the CIFAR-10 dataset can prove the novelty of a pruning method. It can just show a pruning method works well. Most of the results on this paper are limited to the ResNet arch. and CIFAR-10 dataset. CIFAR-10 consists of just ten classes. I think this paper should extend the experimental results to various architectures (ex. MobileNet, Transformer, …) or bigger dataset with smaller model (ex. ResNet-18 on ImageNet). \n- Then, there remains another main contribution, faster pruning-retraining speed regardless of pruning rate. To strengthen this contribution, I think there should be more ablation studies and experiments. I’m curious why this method works with consistent time regardless of pruning rates. Or if I put much time for higher pruning rates, then can I gather higher accuracy by using this method?", "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": "OX68iAHfmv", "reviewer": "Reviewer_c9rK", "summary": "Search for the winning lottery in the Lottery Ticket Hypothesis (LTH) is of great interest in the Machine Learning (ML) community and this paper aims to find such winning tickets (in most cases). This work formulates the model pruning (primarily unstructured but also extends to structured pruning) as a Bilevel Optimization (BLO) where the lower-level optimization finds the best possible set of weights given the sparse neural network (that is weight masks) and the upper-level optimization is optimizing for the boolean mask (done using continuous relaxation followed by threshold-based rounding). Authors first derive the general expression for the gradient with respect to mask using an implicit gradient, which involves second-order derivatives, matrix inverse, and (n, n) matrices where n in #parameters in the network. However, with the hessian free assumption and given the nature of the problem (bilinear in mask “m” and parameters “theta”), the final expression of gradient turns out to have only first-order derivatives. Having defined the expressions, they finally proceed to describe the algorithm which involves lower-level SGD and upper-level SPGD, done until convergence, which does happen, in practice. Then the paper proceeds to the experiments involving multiple architectures, multiple datasets, and different pruning ratios. Performance metrics involve final accuracy, performance relative to the dense pre-trained model, and overall run time. Strong experiments show that BiP achieves superior performance than the original dense model (i.e. finds winning lottery) and has a comparable (or superior) performance to iterative magnitude pruning (IMP) while having much lesser run-time similar to one-shot pruning methods. ", "questions": "As mentioned in the main review.", "limitations": "As mentioned in the main review.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The Paper is concise and well written. \n2. The theory is easy to follow and the experiment section is strong involving ablations across different hyperparameters. \n3. Charts are well organized. \n\nOverall, I enjoyed reading this work. I’ve some suggestions which primarily are additional references to be discussed and some additional visualization that could help to make this a strong submission which I describe in the following weakness section. \n\nWeaknesses:\n1. While the diagram is mentioned in the appendix, can the authors include an algorithm block for a better understanding of the overall flow? \n2. How are the diverse batches chosen for the training? Does it involve some kind of submodular optimization to get the schedule? What happens if the batch for SGD is qualitatively different from the batch of SPGD? \n3. The convergence result shown in the appendix involves final accuracy. Does this happen that the masks still keep on changing (that is finding the subnetwork) but all of that subnetworks have similar performance when trained (performed SGD)? \n4. It was mentioned that SGD steps are kept fixed to 1. However at the very first step of pruning, why would still having just 1 SGD step suffice? \n5. Table 1. Can authors add a vertical separator line for the datasets?\n\nAdditional references that can be discussed:\n1. Soft Threshold Weight Reparameterization for Learnable Sparsity. ICML’20\n2. EFFECTIVE TRAINING OF SPARSE NEURAL NETWORKS UNDER GLOBAL SPARSITY CONSTRAINT. CVPR’21\n3. Rethinking Bi-Level Optimization in Neural Architecture Search: A Gibbs Sampling Perspective. AAAI’21\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": "K-BISb3ND_a", "reviewer": "Reviewer_iDDi", "summary": "This paper provides a novel reformulation of model pruning as a bi-level optimization (BLO) problem, in which the paradigm of pruning-retraining pruning can be viewed as two optimization levels: (1) finding the pruning mask (the upper-level), and (2) masked model retraining (the lower-level).\n\nThe paper further proposed an algorithm, bi-level pruning (BIP), to be a BLO solver that uses only the first-order gradient, which makes it as efficient as one-shot pruning.\n\nThe experiment results show that BIP equips the high efficiency of one-shot pruning and maintains the high accuracy of iterative magnitude pruning (IMP) in both structured and unstructured pruning schemes.", "questions": "- It would be really helpful to add some discussion about the similarities and differences between the BLO and the L0-based pruning (https://arxiv.org/pdf/1712.01312.pdf). \n- In Figure 6(b1) the best accuracy is achieved when lower-level steps N <= 3, which would be unexpected and need some explanation. As a larger N tends to find more optimal model parameters that are close to $\\theta^*$.\n- Could you talk about the schedule of BIP to prune with multiple sparsity ratios? IMP could initialize from models with low pruning ratios to produce models with high pruning ratios. Thus when pruning for multiple ratios, the time complexity of IMP could be amortized. I wonder if BIP could be efficient in this setting.", "limitations": "The authors have addressed the limitations adequately. It would be better to move some ablation studies like Figure A4 to the main manuscript, though the pages may be limited.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The idea of the BLO reformulation of the model pruning problem is new, which provides a theoretical basis for BLO algorithms to be explored for model pruning. \n- The proposed BIP pruning algorithm is original and practical. \n- The paper is well organized and easy to follow.\n\nWeakness:\n\n- It would be really helpful to add some discussion about the similarities and differences between the BLO and the L0-based pruning (https://arxiv.org/pdf/1712.01312.pdf). L0-based methods view pruning masks as random variables defined by specific parameters, thus making the pruning masks could be learned together with the models. This is a different perspective compared to BLO. And these two views may be combined and unified, which makes it worth having a discussion and comparison.", "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": "D-YYStKy9FM", "reviewer": "Reviewer_mQEK", "summary": "The authors (correctly) identify that iterative magnitude pruning (IMP) is inefficient to extract \"winning tickets\" from neural networks. To this end, they investigate a method utilising bi-level optimisation (BLO) to extract winning tickets -- including structured results which can easily yield real-world speedups. In the paper they formulate pruning as a BLO problem, and subsequently evaluate across CIFAR-10/100, Tiny-ImageNet and ImageNet. The results are consistently better than IMP, and gradient-based saliency methods such as Grasp.\n\n==\n\nSee below for response to authors; score has been updated after rebuttal.", "questions": "Many of the questions are motivated from above:\n\n1. What is the definition of \"winning tickets\" used?\n2. Is the pruning done continuously through training?\n3. What is the motivation for not using Frankle's benchmark?\n4. How fast are the channel pruned networks?", "limitations": "I don't think there is any explicit discussion of limitations in the main paper. The checklist points us to appendix C4 but there's nothing there regarding limitations (and I have discussed some above).", "rating": 2, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I am suspicious of the contributions of this paper, since the use of \"winning ticket\" seems to be overloaded in this work. In the abstract this term is defined as: \"i.e., pruned sparse models with better generalization than the original dense models\". But -- this is not the widely agreed upon definition. Lines 35 to 37 give the more widely accepted definition, but line 325 gives a different definition which I don't agree with. It is crucial that the work is self-consistent, and consistent with other literature.\n\nFollowing on from this observation, it seems that the pruning is done throughout training. This cannot reasonably be compared to IMP or Grasp: the pruning mask is set at iteration 0 (or close to 0) and does not change throughout training. It is also worth noting that Grasp is not SOTA anymore: you should compare to ProsPr by Alizadeh et al. (cited by your work already). The only valid comparison I can see would be to the Early-Bird work by You et al. -- but you don't provide any in this direction. In addition, you have provided few comparisons to methods which prune after training, and perhaps do some small amount of fine tuning. These are also reasonable competitors to this work.\n\nFinally, you are not the first to do bi-level optimisation for pruning. \"Differentiable Network Pruning for Microcontrollers\" by Liberis and Lane would be an example prior art (and I'm sure there are others).\n\nHere are some more minor thoughts:\n\n- Code is included which is very nice since the method is fairly complicated.\n- I really commend this work for paying attention to structured pruning -- it's a really hard problem, and far more relevant than most other pruning directions -- but I am not sure you characterise the related work fairly. \"Single Shot Structured Pruning\" by van Amersfoort et al. and ProsPr by Alizadeh et al. both assessed this direction at initialisation.\n- On L229 you say that we can assume $\\nabla^2 l = 0$. I am not convinced this is actually true in practice: after all, this is how many earlier pruning saliency methods worked. However, I am not saying that this makes the work incorrect; approximations pop up everywhere in DL.\n- Is there a good reason to use reference 18 as the benchmark rather than the benchmark provided by Frankle's missing the mark work? It is very extensive, and other works have built upon it in recent years.\n- Figure 6a is not enough to justify the robustness to rewinding that marks a winning ticket. You've provided results on the smallest model with the easiest dataset. More difficult examples are needed.\n- The final line of the conclusion is a bit concerning: in practice, structured pruning methods could prune the same number of parameters but yield totally different speedups. It is an important thing to measure.", "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