Max-Affine Spline Insights Into Deep Network Pruning
Authors: Haoran You
Randall Balestriero
Zhihan Lu
Yutong Kou
Huihong Shi
Shunyao Zhang
Shang Wu
Yingyan Lin
Richard Baraniuk
Venue: Accepted by TMLR ()

Abstract: State-of-the-art (SOTA) approaches to deep network (DN) training overparametrize the model and then prune a posteriori to obtain a ``winning ticket'' subnetwork that can achieve high accuracy. Using a recently developed spline interpretation of DNs, we obtain novel insights into how DN pruning affects its mapping. In particular, under the realm of spline operators, we are able to pinpoint the impact of pruning onto the DN's underlying input space partition and per-region affine mappings, opening new avenues in understanding why and when are pruned DNs able to maintain high performance. We also discover that a DN's spline mapping exhibits an early-bird (EB) phenomenon whereby the spline's partition converges at early training stages, bridging the recently developed DN spline theory and lottery ticket hypothesis of DNs. We finally leverage this new insight to develop a principled and efficient pruning strategy whose goal is to prune isolated groups of nodes that have a redundant contribution in the forming of the spline partition.
Extensive experiments on four networks and three datasets validate that our new spline-based DN pruning approach reduces training FLOPs by up to 3.5x while achieving similar or even better accuracy than current state-of-the-art methods. Code is available at https://github.com/RICE-EIC/Spline-EB.

Published in Transactions on Machine Learning Research (07/2022)
Max-Affine Spline Insights Into Deep Network Pruning
Haoran You" T* Randall Balestriero Zhihan Lu", Yutong Kou Huihong Shi', Shunyao Zhang's Shang Wu', Yingyan Lin and Richard Baraniuk'
'Rice University 'Meta AI Research
Huazhong University of Science and Technology "Nanjing University "hhooran.you, z155, s274, sw99, yingyan.lin, richb) @rrcc..dr, 'rbalestriero@ff..com,
"shihh@smail.jju.edee
Reviewed on OpenReview: http:://pppaarriiss....e////bbta
Abstract
State-of-the-art (SOTA) approaches to deep network (DN) training overparametrize the model and then prune a posteriori to obtain "winning ticket" subnetwork that can achieve high accuracy. Using a recently developed spline interpretation of DNs, we obtain novel insights into how DN pruning affects its mapping. In particular, under the realm of spline operators, we are able to pinpoint the impact of pruning onto the DN's underlying input space partition and per-region affine mappings, opening new avenues in undorstanding why and when are pruned DNs able to maintain high performance. We also discover that DN's spline mapping exhibits early-bird (EB) phenomenon whereby the spline's partition converges at early training stages, bridging the recently developed DN spline theory and lottery ticket hypothesis of DNs. We finally leverage this new insight to develop a principled and efficient. pruning strategy whose goal is to prune isolated groups of nodes that have a redundant contribution in the forming of the spline partition. Extensive experiments on four networks and three datasets validate that our new spline-bascr DN pruning approach reduces training FLOPs by up to 3.5x while achieving similar or even better accuracy than current state-of-the-art methods. Code is available at https: http:///gttbb..o...../// http./////-/III//Slllaae.
1 Introduction
Deep Networks (DNs) are powerful and versatile function approximators that have reached outstanding performances across various tasks, such as board-game playing (Silver et al., 2017), genomics (Zou et al., 2019), and computer vision (Esteva et al., 2019). For decades, the main driving factor of DN performances has been progresses in their architectures, e.g. with the finding of novel nonlinear operators (Glorot et al., 2011; Maas et al., 2013), or by discovering novel arrangements of the succession of lincar and nonlincar operators (LeCun et al., 1995; He et al., 2016; Zhang et al., 2018). With a tremendously increasing need for DNs practical deployments, one line of research aims to produce a simpler, energy efficient DN by pruning dense and overparametrized one, c.g. removing either weights, nodes, filters, layers, or any combination much reduced computational cost (Frankle & Carbin,
of these options from DN architecture, leading 2019b; Han et al., 2015; Chin al., 2020; Liu et al., 2017). Recent progresses (You al., 2020; Molchanov et al., 2016) in this direction allow to obtain models much more energy friendly while nearly maintaining the models' task accuracy (Li et al., 2020).
While tremendous empirical progress has been made regarding DN pruning, there remains lack of explicit understanding of its impact on a DN's underlying mapping. A few studies (Dong et al., 2017; Qian & Klabjan, 2021) have started to compare different pruning strategies from more theoretical perspective. Yet, such formulations propose very specialized solutions who often fail to extend to any pruning policy.
denotes equal contribution

---

Published in Transactions on Machine Learning Research (07/2022)
Providing more general framework to study the many pruning solutions that keep emerging rapidly is however crucial e.g. to compare all those methods under a unified mathematical model, to better decide which method to use based on a given application, or even to design novel pruning techniques guided by some a priori knowledge about the given task and data. Our goal in this study is to motivate the use of the affine spline formulation of DNs to analyze the recently developed empirical pruning techniques, e.g., lottery ticket hypothesis Frankle & Carbin (2019b); You et al. (2020); Evci et al. (2019); Su al. (2020); Blalock et al. (2020).
In this paper, we shed new light on the inner workings of pruning techniques from a spline perspective, by leveraging recent advances in DN understandings and spline formulation (Montufar et al., 2014; Balestriero & Baraniuk, 2018). Specifically, current DNs are affine splines, that is the input-output mapping is affine in polytopal regions of the input space partition. From this viewpoint pruning acts upon DN by remov- ing/altering the partition boundaries as demonstrated in Fig. 1, and therefore pruming affects the decision boundary which is constrained to be linear within the regions of the DN partition. We will demonstrate how this viewpoint allows us to interpret current pruning techniques (e.g. lottery tickets hypothesis (Frankle & Carbin, 2019a)) by sludying their impact on the DN inpul space partition, demonstrating how and when can pruning be used without sacrificing the final performances. Finally, we demonstrate how to derive a new pruning scheme based our gained understandings that reaches competitive performances. In order to ease our development, we slightly abuse notations and refer to DN as being overparametrized whenever it can be pruned while maintaining its performances and refer to a DN as being minimal whenever it can not be pruned without impacting its performances. We summarize our contributions as follows:
[CI] We discover and bridge the connection between spline theory and network pruning techniques. Specifi- cally, we relate the pruning of DN nodes or weights to (i) the DN input space partition, (ii) the per-region affine parameters, and (Mi) the decision boundary, providing the explicit interpretation of existing empirical pruning strategies various gramularity levels (either structured or unstructured).
[C2 We further exlend these insights by proposing a partition-based metric to quantify the evolution of the partition boundaries during training, which allows us to efficiently detect early-bird (EB) tickets when an overparametrize DN has been trained enough and can be pruned; and as opposed to previous EB methods, ours detects EB tickets regardless of the employed pruning techniques or hyperparameters.
[C3] We leverage the new insights and the finding of [C2] to derive an efficient pruning strategy from first principles, which only focuses on DN nodes whose corresponding spline partition boundaries contribute to the final decision boundary. A series of experiments on various benchmarked models and datasets validate that our pruning method achieves 3.5x training FLOPs reduction and maintains similar or even better accuracies over state-of-the-art pruning techniques, while being principled and interpretable.
2 Background and Related Works
A DN transforms an input æ through a composition of L layers f= L to form the final prediction: f(z) = (f" .o (x). Each layer is (nonlinear) mapping taking as input 1 -dimensional feature map and producing a D -d-mmensiinnl one, where D' the th feature map's dimension'; each layer's parameters are collected in 0g. The input dimension is referred to as D". For a fully-conneeted and activation function layer, O₂ comprises the Dº x D dense matrix Wf and the -i-mmensiional bias vector b'. For convolution operators (LeCun et al., 1995), the dense matrix W is replaced with circulant block circulant matrix cf for channel-wise convolutions and summations.
Max-affine spline DNs. A key result of (Montufar et al., 2014; Balestricro & Baraniuk, 2018) is the reformulation of current DN layers with (leaky-)ReLnnTiiearr Abs. Value activation functions as spline operators and in particular as Max-Affine Spline Operator (MASO), and the entire input-output mapping is Continuous Piecewise Affine (CPA) mapping. The input space partition of such DNs has been characterized in (Balestriero et al., 2019). Jointly, the layers combine their imput space partition to form the DN input space partition Ω. A few work have focused on studying the relation between the number of regions and the DN architecture (Hanin & Rolnick, 2019b), the analytical form of the partition (Balestriero et al., 2019),
consider matrices and tensors as flattened vectors for clarity
2

---

Published in Transactions on Machine Learning Research (07/202) 2022)
(b) Node Pruning
Layer 1
Layer 2
Layer 3 (Classifier)
(a) Input Space Partitioning
(c) Weight Pruning
Figure 1: (a) Input space partitioning presents how deeper layers successively subdivide the space in loy DN with 2 dimensional input space and three layers: Xy E R X1 E R - X22 E R X3 E R where the newly introduced boundaries are in dark and previously built ones are in grey. We see that: (i) the turning point of splines in later layers are exactly located at previous ones, and (ii) splines in the final classification layer are exactly the decision boundary (denoted as blue lines). Additional examples are supplied A Appendix H; (b) Node (structured) pruning removes entire subdivision splines; (c) Weight (unstructured) pruning quantizes the partition splines to be colinear to the space axes. Both (b) and (c) are conceptual diagrams to explain how pruming incurs the less expressiveness of the final decision boundary.
the upper bound in the number of regions (Montufar et al., 2014; Montúfar et al., 2021). The fundamental property that will leverage throughout this paper is that the internal weights of the layers are paired with their input space partition. As praning impacts those weights and/or nodes directly, this will offer new ways to sludy pruming in DNs' inpul space. More background on DNs, their spline formulation, and its connection with DN pruming can be found in Appendix F.3,
Network pruning. Pruning is a widely used DN compression technique reducing the number of activated nodes (Liu et al., 2019c; LeCun el al., 1990) in given model. The common pruning scheme adopts a three-step routine: (i) training a large model with more parameters than the desired final DN, (ti) pruning this overly large trained DN, and (ıūi) fino-tuning the pruned model to adjust the remaining parameters and restore as best possible the performance lost during the pruming step. Those three steps can be iterated to get highly-sparse network (Han et al., 2015). Within this routine, different pruning methods can be employed, each with a specific pruning criteria, granularity, and scheduling (Liu et al., 2019c; Blalock et al., 2020). Those techniques roughly fall into two categorics: unstructured pruning (Han et al., 2015; Frankle & Carbin, 2019b) and structured pruning (He el al., 2018; Liu et al., 2017; Chin al., 2020). Regardless of pruning methods, the trade-offs lie between the amount of pruming performed on a model and the final accuracy. For various energy efficient applications, novel pruming techniques have been able to push this trade-off favorably. The most recent theoretical works DN pruning relies studying the existence of Winning Tickets. (Frankle & Carbin, 2019b) first hypothesized the existence of sub-networks (pruned DNs), called winning tickets, that can produce comparable performances to their non-pruned counterpart. Later, (You et. al., 2020) showed that those winning lickets could be identified in the early training stage of the unpruned model. Such sub-networks are denoted as early-bird (EB) tickets.
Despite the above discoverics, the DN pruning litcrature lacks an explicit understanding and visualization via theoretical analysis that would bring insights into (i) current pruning techniques and (ii) observed phenomenons such EB tickets, while leading to principled pruning techniques. We propose to approach this task by leveraging the spline viewpoint of DNs to provide novel interpretations of existing pruning techniques, study the conditions to their success and when should they be avoided, and finally, how to derive novel pruning strategies from first principles.
3 Deep Networks Partition, Decision Boundary and Pruning Work Hand-In-Hand
In this section, we first introduce our novel spline interpretation of pruming at various gramularity levels. Then we extend such insights by detecting spline EB tickets through pruning invariant partition-based metric. Finally, leverage the new insights to derive an principle and efficient pruning strategy.
3

---

Published in Transactions on Machine Learning Research (07/2022)
3.1 Exact Characterization of Deep Network Pruning Using Spline Theory
The goal of this section is to formalize the impact of pruning onto the deep net underlying mapping beyond the standard understanding that pruming, regardless of the strategy, reduces the DN capacity. As will become clear, one formulation that enables more precise insights is the Continuous Piccewise Affine (CPA) formulation DNs. By adapting the known ties between DNs to CPAs Montufar et al. (2014); Balestriero & Baraniuk (2018) (also recall Sec. 2), we now propose precise understanding of the impact of pruning onto the DN's CPA mapping, first starting by providing the explicit CPA operator, to then demonstrate how that CPA mapping is impacted by various pruning strategies.
From Deep Networks to Continuous Piecewise A Affine Operators. First, we ought to recall (also recall Sec. 2) that a CPA mapping is a mapping that is overall continuous, and that produces an output f(x) given an input a through a simple affine transformation whose parameters depend on the region w of the imput space partition Ω containing a. To first build some insights into how a DN is in fact a CPA operator, we consider a singlo-layer DN the form of
f(x) o oW'' x bb))
(1)
with x E RRD" W' x + b' the output of the alfine I transformation of the first layer which is D D'ddimensional vector, and a an element-wise activation function e.g. producing its output at coordinate ls given an input vector u as follows
[u]k. = [u] 2 0 [a[u], = [u] < 0,
[o(u]]
with a the leakiness parameter (notice that setting a -1 1 also recovers the absolute value. Due to the specific form of the activation function, we can obtain friendlier form than the one of Eq. where the DN mapping is now viewed as CPA mapping i.e.
f(x) Σ (A a: + 1
(2)
WES
where Ω is partition of the DN input space (TR (T) and the collection of regions w E Ω can be found analytically as in
U HEERR" ((W,,,,)) .)) b.)s, s s0 = 1, 1,...,,K) [k]... sE(-1,13
Q= =
(3)
hence the partition Ω is made of convex (possibly open) polytopal regions that are the intersection of half- spaces given by each of the first layer's affine mapping and all the possible combination of positive positive/negative 'ngative activation patterns of a. It should be clear that the above DN = CPA bridge holds not only for leaky-ReT.C but any nonlinearity that is itself a CPA e.g. max-pooling.
To case the next derivations, we introduce the operator S Ω {-1, which maps any region of the partition E Q to its corresponding vector of signs that defined w (recall Eq. 3). With this mapping, we can further simplify the input-output DN mapping to recover Eq. 2 as follows
f(x)
diag(S W' x + WES?
Σ
[(wEw)-
(4)
$A
4b
A key insight is that the layer parameters W! b¹ impact both the per-region affine mapping parameters and the partition regions (compare Eq. and 4). This single layer case is already sufficient. to start pinpointing the impact of different pruning strategies on the the DN's underlying CPA mapping. We propose to do so in the following paragraph, and delegate the multilayer extension for the end of this section.
How Pruning Impacts Deep Networks' Partition and Per-Region Affine Mappings. Given the above derivations, we can now provide clear distinction between weight and unit pruning applied on layer e in how those two different strategies impact the CPA properties e.g. its partition. First, let's formalize
here Z= follow the previous paragraph derivation but the same applies to any layer in general
4

---

Published in Transactions on Machine Learning Research (07/2022)
the pruning strategy as the application of mask onto the layer's parameters
(W , (Qw o w q o').
(5)
where Qúv {0. 13'x0" and q E {0. 1) The entries of the mask matrix/vectoon depend on the employed
stratogy and can impose a specific structure c.g. unit pruning would employ Qiv = qi 1 and q giv so that the masking applies to all the parameters of a wnit at once, while parameter pruning would treat each entry of Qw: g. independently.
A first direct observation can be made by combining Eq. 3, and demonstrating how pruning not only impacts the CPA partition but also its per-region mappings, as both are tied together.
Proposition 1. Regardless of the type of pruning (weight/unij) setting entries of Qw L to O, i.e applying pruming, impacts both the per-region affine mappings A b. and the DN input space partition Q.
The above already finds a very interesting insight. The ability find pruned DNs that perform nearly as good as their unpruned counter-part demonstrate that the affine mapping parameters A bu and the DN partition & can be "compressed" without much detrimental impact. We first propose to leverage the DN input space partition to study the difference between node and weight pruning, representing structured and unstructured pruning, respectively. In the former, nodes of different layers are removed, while in the latter, entries of the w' matrices (or C' for convolutions) are removed. We demonstrate in Fig. 1 (b) and (c) that node pruning removes entire subdivision splines while weight pruning (or quantization) can be thought as finer granular limitations on the slopes of subdivision splines, and will only remove the subdivision lines when all entries of a specific row in W are pruned, in which case node and weight pruning become identical. From this perspective, we can already identify the reason why pruned networks are less expressive than the overparametrized variants (Sharir & Shashua, 2018) as pruned DNs' input space partition and final decision boundary shape are limited compared to their unpruned counterparts. This can be formalized more precisely below. To streamline notations, we will now denote by Card( W.b) the number of region of the layer given by the parameters W and b.
Theorem 1. A light inequality belween the number of regions of pruned DNs and unpraned counterparts is given by
D' 1
Qw o w a ob) s Card(?) b') - Σ
k-1
and for unit pruning policy, the marinum number of regions that Ω contains is given by max Card(SlQw o w', o o b²) = 2 (9
2
To see this result, notice that the number of possible sign patterns ie.. Card(!)) reduces with the number of units that are being pruned. If a layer contains in general K units, then its maximum number of regions or sign patterns is x (see e.g. Balestriero et al. (2019)), hence unit pruning simply alters K given the amount of units that have been removed. This raises interesting venues e.g. to study why the DN partition appears to be much more redundant than necessary, although DN partitions already contained a number of regions much smaller than their upper limit. In fact, even in unpruned DNs for which the number of combination is 2* many of those regions turn out to be empty after training as precisely characterized in (Hanin & Rolnick, 2019a). Combining those results, we thus observe that most DNs do not require to exploit the full potential of their partition, hence making pruning method successful.
Going to Multilayer Deep Networks and Smooth Activations
Going to any desired depth can be done following the recipe of Balestricro et al. (2019). The main idca reads as follows. Given a DN, first consider its first layer, and find its corresponding partition i.e. as done above. Once this is obtained, this first part of the entire DN is known to be a simple affine mapping within each region is of the currently obtained partition. Hence withhnn w- we can consider this first part of the entire DN mapping as single linear layer and the above procedure can be repeated again now obtain the partition of the first two layers (the first one being simple linear mapping on w). This provides
5

---

Published in Transactions on Machine Learning Research (07/202) 2022)
90
Data Grid
80
Unpruned
Prune 20%
Prune 40%
12
FC Layer
x
10
RELU Act.
60
FCNet Accuracy (%)
FC Layer
x0
FCNet Speed (epochis)
20 40 60
80
90 95
Prune 60%
Prune 80% FCNet Splines Visualization
Prune 90%
FCNet
Pruning Ratio (%)
Figure 2: Classification task pruning using FCNets, where the blue lines represent subdivisions in the first layer and the red lines denote the last layer's decision boundary. We see that: (i) pruning indeed removes redundant subdivision lines so that the decision boundary remains an X-shape until 80% nodes are pruned; and (ii) ideally, one blue subdivision line would be sufficient to provide two turning points for the decision boundary, c.g., visualization at 80% sparsity. The middle figure visualizes the accuracy and training speeds (on a NVIDIA 2080Ti GPU) of the adopted FCNet under various pruning ratios. The general trend is that, the more nodes we prune, the faster is the training at the cost of degraded accuracy.
with a refined partition Ω that is only valid within the studied region w of the first layer partition. Doing for each of those regions and noticing that they are mutually exclusive, the entire partition of the first two layers is obtained. Repeating this process recursively one layer at a time ultimately produces the partition of the entire DN mapping.
Lastly, our entire set of exporiments focus on DNs with CPA nonlincarities. But for completeness, we briefly discuss here how the above analysis could be carried out for DNs with smooth activations. This step is quite direct as it relies on the results from Balestriero & Baraniuk (2019) that have demonstrated how entire class of smooth activations correspond to nothing else but CPA nonlincarities in which the region assignment (the indicator function in 1) is made probabilistic. In short, an input x is not assigned to a single region but is assigned to each of the region with a confidence value, which recovers the standard CPA case in the zero-noise limit, Hence, using this result, all the above can be directly extended to such smooth nonlincaritics.
3.2 Visualization of Deep Network Pruning From Spline Perspective
We now propose to visualize the impact of pruning onto the DN partition with a more realistic setting of a trained DN and employing an existing pruning strategy.
Despite the constraints that pruning imposes on the DN input space partition, classification performances do not necessarily reduce when pruning is employed. In fact, the final decision boundary, while being tied with the DN input space partition, does not always depend on all the existing subdivision lines. That is, pruning will not degrade performances as long as the needed decision boundary geometry does not rely on the partition regions that are being offected by pruning. We demonstrate and provide explicit visualization of the above in Fig. 2 and Fig. with fully- fully-connected networks (FCNets) and convolutional networks (ConvNets). respectively. The observation consistently shows that only parts of subdivision splines are useful for decision boundary; and the goal of pruning is to remove those (redundant) subdivision splines and find winning tickets. For example, observe that for two-layer FCNet (20 nodes per layer), applying pruning ratios ranging from 20% 95% (i.e., prune 4 ~ 19 nodes) does not prevent solving the task as long as the remaining subdivision lines are positioned to allow the decision boundary geometry to remain intact. We also extend the above experiment to a high dimensional case with MNIST classification and a DN with two convolutional layers, 20 filters, and kernel sizes 21 and 5, respectively in Fig. 3. By adopting the same channel pruning method as (Liu et al., 2017), we see that most of the pruned nodes remove subdivision lines that were not crucial for the decision boundary and thus only have a small impact the final classification performance. Hence, as long as pruning leaves at least those few subdivision lines,
6

---

Published in Transactions on Machine Learning Research (07/202) 2022)
G
10.5
e
95
Unpruned
Prune 20%
Prune 40%
Data
Grid
90
Conv BN--LL
20 21
9.55
Conw RELU
2
85
ConvNet Speed (epoch/min)
9.0
20 40 60 80
90
95
Prune 60%
Prune 80% ConvNet Splines Visualization
Prune 90%
ConvNet
Pruning Ratio (%)
Figure 3: Classification task pruning using ConvNets, where to produce these visuals, we choose two images from different classes to obtain a 2-dimensional slice of the 764-dimensional input space (grid depicted on the left). We thus obtain low-dimensional depiction of the subdivision splines that we depict in blue for the first. layer, green for the second convolutional layer, and red for the decision boundary of 6 vs. 9 (based on the left grid). We consistently find that only a fraction splines are necessary to provide the turning points of final decision boundary. The middle figure visualizes the accuracy and training speods (on NVIDIA 2080Ti GPU) of the adopted FCNet under various pruning ratios. The general trend is that, the more nodes we prune, the faster is the training the cost of degraded accuracy.
the final performances will remain high. Apart from the empirical study, we also provide some analysis about the connection between pruning (e.g, lottery ticket hypothesis (I.TH) and spline theory in Appendix G.
3.3 Spline early-bird tickets detection
Early-Bird (EB) lickets (You et al., 2020) provides method to draw winning ticket sub-networks from a large model very early during training (10% ~ 20% of the total number of training epochs). The EB drawn is based on an a priori designed pruning strategy and hyperparameters and compares how different (in terms of which nodes/ nodes/channee channels are removed) are the hypothetical pruned models through the training steps; this method outperforms SOTA methods (Frankle & Carbin, 2019b; Tiu al., 2017). The main limitation of EB lies in the need define a priori pruming technique (itself depending on various hyperparameters). Based the spline formulation, we formulate novel EB method that does not rely on an external technique and only considers the evolution of the DN input space partition during training.
Early-bird in the spline trajectory. First, we demonstrate that there exists an EB phenomenon when viewing the DN input space partition, which should follow naturally as the DN weights and the DN input space partition are tied. We visualize DN partition's evolution at different training stages Fig. 4 (a) and (b), under the same settings as Sec. 3.2. From this, we clearly see that the partition quickly adapts to the task and data at hand, and then is only slightly refined through the remaining training epochs. This fast convergence comes carly as the 2000-th iteration (w.r.t. 10000 itcrations for FCNets) and the 30-th epoch (w.r.t. 160 epochs for ConNNets). Additionally, we observe that the contribution of the first layers in the input space partition becomes stable more rapidly than for deeper layers. We can thus leverage this early convergence to detect EB tickets with a novel metric based on those subdivision lines to draw more unified EB tickets than (You et al., 2020). Moreover, EB tickets have been found to be universal under different optimization and initialization methods, of which the experiments are provided Appendix and E.
Quantitative distance between input space partitions. To draw EB tickets based the evolution of DN input space partitions, we first need to provide metric that conveys such information. First, recall that cach region from the DN input space has an associated binary code based on which side of the subdivision trajectories the regions lie (Montufar et al., 2014; Balestriero & Baraniuk, 2018). Given large collection of data points, we can assign each datum the code the region lies in (found simply based on the sign of the per-layer feature maps). As training occurs and the partition adapts, the code associated with an input will vary. However, once training stabilizes and regions do not change anymore, this code will remain the same. In fact, one can easily show that in the infinite data sample regime covering the entire input space, DNs with

---

Published in Transactions on Machine Learning Research (07/202) 2022)
Figure 4: Visual- ization of spline trajectorics, which mainly adapt during early phase of train- ing demonstrating the lottery ticket hypothesis for DN partitions.
03
0.06
Loss
0.4
Loss
0.04
02-
AWW
0.0
0.00
4000
20
62
50
100
120
142
100
Iterations
Epochs
(a) Spline Trajectory for FCNets
(b) Spline Trajectory for ConvNets
25
15
25
13
25
14
50
50
50
0.6
75
75
75
0.4
100
100
100
125
125
125
0.2
150
150
150
(a) AlexNet on CIFAR10
(b) VGG-16 on CIFAR100
(c) PreResNet-101 on CIFAR100
Figure 5: Visualization of the early-bird (EB) phenomenon, which can be leveraged to largely reduce the training costs due the less training of costly overparametrized DNs. Each sub-figure visualizes the quan- titative distance over the whole training process. Both and axis represent the epoch where we draw the binary code to represent the DN input space partition. Each point means the distance between the binary code drawn from æ-th epoch and y-th epoch. The quantitative distances between consecutive epochs change rapidly in the first few training epochs (denoted by dashed red box) and remain similar after that, we then draw Spline EB tickets such epoch, which the very beginning of the training process (i.c., epochs), indicating both the existence of EB tickets and the effectiveness of our detector.
the same codes also have the same input space partition, in turn the same decision boundary geometry. The proposed metric is thus the hamming distance between the codes of each datum observed at two consecutive training steps.
We visualize the above hamming distance of the DN partition between 160 consecutive epochs, when training AlexNet on CIFAR-10 (shown as the spline distance matrix (160 x 160) in Fig. 5, where the (i.j)-th element represents the spline distance between networks from the i-th and j-th epochs. The distances are normalized between 0 and 1, where a lower value (w.r.t. warmer temperature) indicates a smaller spline distance (and thus DNs with similar partitions). We consistently observe that such distance bocomes small (i.e., < 0.15) in the first few epochs under different models and datasets settings. indicating the EB phenomenon, but now captured terms of the DN input space partition. To obtain an active EB drawing strategy from that, we measure and record the spline distance between three consecutive epochs, and stop the training when the two associated distances
smaller than predefined threshold of 0.15, denoted by the red block in Fig, 5. The detailed algorithm is provided in Appendix A. We conclude by emphasizing that opposed to the usual EB tickets drawn in (You et al., 2020), our formulation provide more interpretable scheme that is invariant to the pruning strategy as well as its hyperparameters (e.g., the pruning ratio). Hence, our formulation allows for a unified solution that does not require to be adapted based on the pruning technique that users experiment with.
3.4 Spline pruning policy
We now propose to derive from first principles novel pruning strategies of DNs based on the spline viewpoint insights. Recall from Sec. 2 that the layer input space partition is formed by successive subdivision process
8

---

Published in Transactions on Machine Learning Research (07/2022)
involving each per-layer imput space partition. As also studied in the previous section, for classification performances, not all the input space partition regions and boundaries are relevant since not all affect the final decision boundary. Knowing a priori which regions of the input space partition are helping in solving the task is extremely challenging, since it requires knowledge of the desired decision boundary and of the input space partition, both being highly difficult to obtain for high dimensional spaces and large networks (Montufar et al., 2014; Balestriero et al., 2019; Hanin Rolnick, 2019a). What simpler to obtain, however, is how redundant are some of the layer weights/ weights/units units in terms of the forming of the DN partition relative to other mmits/weights From that, it will become easy to prune the redundant /weishs as their impact on the forming of the decision boundary is already carried by another
When considering the layer input space partition, we can identify "redundant" units based on how each unit impacts the partition with respect to other units. For example, if two units have biases and slope vectors proportional to each other, then one can effectively remove one of the two units without altering the layer imput space partition. While this is a pathological case, we will demonstrate that the angles between per-unil slope matrices and inter-bias distances measure such redundancy. We first introduce our pairwise redundancy measure as the following equation:
(1 K[W')... Jac.)) II[W") Je,"Jl,,lalllln Iall Iv. lla
No R-)
pl[b']x -[b']wl.p> 0,
(6)
where W& refers to the corresponding slope matrices of the k-th unit, P is an hyper-parameter measuring the sensitivily of the difference in angle versus the biases. In the case of a convolutional layer, Wi is the flattened filter of shape (channels in, height, width). Finding the two units with the most similar contribution to the DN input space partitioning can be done via arg min (k, k') where the obtained couple (k, k') encodes the two units which are the most redundant. In turn, one of those two units can be pruned such that the impact of pruming onto the DN input space partition is minimized.
Proposition 2. Given a layer and its input space partition, removing sequentially one of the two units, k and i,' for which (K,, k²) 0, leaves the layer input space partition unchanged.
The above result exploits (Balestriero et al., 2019). In short, if (k, K') for any positive p. then the layer-partition boundaries (of layer é) of units k k' per- fectly overlap. The DN partition bound- arics correspond to the layer-partitie boundaries backpropagated through the earlier layers to reach the data space. But this process is continuous operator i... the layer-partition boundaries that overlap will produce DN partition bound- aries that overlap. In practice, units with small enough but nonzero (k, R²) are also highly redundant and can be re- moved. We provide an example of this procedure in Fig. 6, where a small DN input space partition (layer trajectories in black and layer 2 in blue) is depicted. In the middle we visualize the measurements from Eq. (6) that trying to find similar "partition trajectories" from layer 2 seen in the DN input space (comparing the green trajectory to the others with coloring based on the induce similarity from dark to light). Based on this measure, pruning can be done to remove the "grouped partition trajectoris" and obtain the pruned partition on the right.
DN Partition ?
N² (kc
Pruned
3
3
3
2
2
1
1
1
0
0
-1
-1
-2
-2
-2
33
-3
-3
-3 -3-2-10 0 1
2
3
-3 -
0 2 3 -3-2-1 0 1 2
Figure 6: Left: small 2, 5 DN input space partition. Middle: the pruning criteria as in Eq. (6). Right: the pruned input space partition based on the criteria.
Efficiency of the spline pruning. Note that instead of using parameter-wise pruning, we perform channel- wise pruming of which the pruning overhead is negligible when evaluating across four models and three datasets. For example, ResNet-50 has about 20k channels and needs 100G FLOPs to prune, which is only /30,,000,00 of the training costs (3000P FL.OPs).
9

---

Published in Transactions on Machine Learning Research (07/2022)
Table 1: Evaluating the proposed layerwise spline pruning over SOTA pruming methods on CIFAR-100, where all accuracies are averaged over five runs and "Improv." denotes the improvements of our layerwise spline pruning over the network slimming (NS) method.
PreResNet-101
VGG-16
Pruning ratio
Dataset
NS
Spline
EB Spline
Improv.
NS
Spline
EB Spline
Improv.
Unpruned
93.06+0.00
93.66+0.04
93.66+0.04
92.71+0.07
92.71=0.07
92.71=0.07
30%
93.48+0.08
93.56+0.05
93.07+0.10
+0.08
93.29+0.110
93.21+ 06
92.83=0.09
-0.08
CIFAR-10
60%
92.52=0.02
92.55+0.03
92.37+0.04
+0.03
91.85+0. 12
92.13+0.
92.23+0.14
+0.38
70%
91.27=0.23
91.3320.22
91.33=0.15
+0.06
88.52#0.22
89.6810.24
88.6520.20
+1.16
Uupruned
73.1040.15
13.1020.15
03.1040.15
71.4340.25
714330..2 25
71.43+0.25
10%
0.15
01.58+0.16
73.14+0.12
+1.56
71.6+0.25
71.78+0.17
72.28+0.27
+0.68
CIFAR-100
30%
00.70=0.21
70.13+0.19
72.11=0.24
+1.41
70.32+0.20
71.15+0.23
71.59+0.18
+1.27
50%
68. 0.62
69 0.99
70.88=0.83
+2.18
66. 06.10=0.11
69.92-0.32
69.96+00.41
+3.86
70%
1.151+1.12
67 07.06+1.08 1.08
68.41+0.92
+1.90
61.16+1.36
1.413+1.42
64.01+1.40
+2.85
4
Experiment results
In this section, we first describe our experiment scttings, and then benchmark the proposed spline pruning method over ten SOTA pruming baselines in the context of layerwise pruning and gloabl pruning, respectively. Finally, we present ablation studies in terms of the only hyper-pant ppprr-paraettr p.
4.1 Experiment settings
Models, datasets, baslines, and metrics: Models & Datasets: We consider four DNN models NPreRes VGG-16, and RessNet-18/00) on both the CIFAR-10/100 and ImageNet datasets follow- ing the basic setting of (You et al., 2020). Baselines: We evaluate the proposed spline pruning methods over ten SOTA training and pruning baselines, including network slimming (NS) (Liu al., 2017), lottery tickets (LT) (Frankle& & Carbin, 2019a), SNIP (Lee et al., 2019), ThiNet (Luo et al., 2017), SFP (He et al., 2018), LeGR (Chin et al., 2020), GAL-0.5 (Lin et al., 2019), GDP (Lin et al.), C-SGC-50 (Ding et al., 2019), and meta pruning (Liu et al., 2019b). Among them, LT and SNIP are unstructured parameter-wist wise pruning while others (as well as ours) are structured heter/chaneelwise pruning, therefore it is desired to see that LT and SNIP perform better under high pruning ratios, e.g., 70%, but lead to much higher energy cost or training FLOOPs. All other comparisons are apple-to-apple comparisons in the structured pruning scenarios. Metrics: We evaluate in terms of the retraining accuracy, total training FLOPs, and real-device energy cost, the latter of which are measured by training the models on an edge GPU (NVIDIA JETSON TX2) (NVIDIA Inc.), which considers both the computational and data movement costs.
Training scttings: For the CIFAR-10/ 10/00 datascts, the training takes total of 160 epochs; and the initial learning rate is set to 0.1 and is divided by 10 at the 80-th and 120-th epochs, respectively. For the ImageNet dataset, the training takes a total of 90 epochs while the learning rate drops at the 30-th and 60-th epochs, respectively. In all the experiments, the batch size set to 256, and an SGD solver adopted with a momentum of 0.9 and weight decay of 0.0001, following the setting of (Liu et al., 2019c). Additionally, p in Equ. 2 is set to 0.05 for all experiments except for the ablation studies. All experiments are run in server with ten NVIDIA 2080 Ti GPUs.
4.2 Layerwise spline pruning
Recall that the spline pruning policy is done by solving arg ming, (k, k'). By regard k as the index of channels for convolutional layers, we are able to conduct channel pruning in a layerwise manner. Table 1 shows the comparison between the spline pruning (w/ and w/o EB detection) and SOTA network slimming (NS) method (Tiu et al., 2017) on CIFAR-10/100 datasets. We can see that the spline pruning consistently outperforms NS, achieving -0.08% 3.86% accuracy improvements. This set of results verifies our hypothesis that removing redundant splines incurs little changes in decision boundary and thus provides a good priori initialization for retraining.
4.3 Global spline pruning
We next extend the analysis global pruning, where the mismatch of the filter dimension in different layers impedes the cosine similarity calculation. To solve this issue, in practice, we adopt PCA (Scholz et. al.,
10

---

Published in Transactions on Machine Learning Research (07/2022)
Table 2: Evaluating our global spline pruning method over SOTA methods on 10FA0-10/100 datasets. Note that the "Spline Improv." denotes the improvement of our spline pruning (w/ or w/o EB) as compared to the strongest baselines. All accuracies are averaged over five runs.
Retrain acc.
Energy cost (KJ)/FLOPs (P)
Sctting
Methods
p=30%
p=50%
p=70%
p=30%
p=50%
p=70%
ET (one-shot)
93.70+0.09
93.21=0.05
92.78+0.13
6322/144 (14.
(4.2
6322/14.9
SNIP NS
93. 38.76#0.00 0.00
93.31
92.76 16
3161 /7.40
3161/7.40
3161/7.40
93.83+0.03
93.4220.14
92.49=0.27
5270/13.9
4641/12.7
4211/11.0
PreResNet-101 CIFAR-10
ThiNet
93.39+0.00
93.07=0.15
91.42+0.25
3579/13.2
2656/10.6
1901 /8.65
Spline
94.13+0.04 .04
93.92:0.18
92.06+0.25
4897/13
4382/12.1
3995/10.1
EB Spline
93.67#0.08
93. 18
92.32+0.28
2322/66 /.02/6600
1808/4.22
1421/2.74
Spline Improv.
+0.3
+0.5
-0.46
1.4x/1.2x
1.5x/2.5x
1.4x/3.2x
LT (one-shot)
93.1810.05
93.25=0.19
93.28+0.17
746.2/30.3
746.2/30.3
746.2/30.3
SNIP
93.20+0.09
92.71
92.3+0.22
373.1/15.1
373.1/15.1
373.1/15.1
NS
93.05+0.07
92.96=0.20
92.7+0.24
617.1/27.4
590.7/25.7
553.8/23.8
VGG16 CIFAR-10
ThiNet
92. 02.82#0.12
91.92+0.21
90.4+0.20
631 631.5/22.6
383.9/19.0
380.1/16.
Spline
93.6220.08
93.46=0.10
92.85+0.21
643.5/26.4
603.4/25.0
538. 119.6
EB Spline
93.28+0.04
93.0520.17
91.96+0.18
476.1/19.4
436.1/15.5
370.7 370.7/11.1
Spline Improv.
+0.42
+0.21
-0.43
0.8x/0.8x
0.9x/100x
1.0x/1.4x
LT (one-shot)
71.90+0.20
71.60+0.23
09.95+0.39
(19.9
6095/14.9
6095/14.9
SNIP
0..34+0.22
71.63+0.26
70.01
3047/7.40
3047/7740
3047/7.40
NS ThiNet Spline
72.8+0.14
71.52+0.19
68. 0.446.4499
4851 4851/13.7
4310/12.5
3993/10.3
PreResNet-101 CIFAR-100
73.10:00.13
70.92+0.29
67. 0.39
2603/13.2
2642/10.6
1893/8.65
73.79+0.22
7..04+0.24
0.37
4980/12.0
4413/10.9
4008/9.36
EB Spline
40.67
0..99
69.7440.33
2388 10988/5.44 55.44
1821 1821/3.84
1416/2.46
Spline Improv.
+0.69
+0.44
-0.27
1.3x/1.45 /.4x
1.5x/2.8x
1.3x/3.5x
p=10%
p=30%
p=50%
p=10%
p=30%
p=50%
LT (one-shot)
72.62+0.21
71.31+0.25
70.96+0.46
741.2/30.3
741.2/30.3
741.2/30.3
SNIP
71.55+00.28
70.83+0.24
70.35+0.38
370.6/15 /1..
370.6/15.1
370.6/15.1
NS ThiNet
71.24+0.27
71.28=0.29
69.74=0.51
636.5/29.3
592.3/27.1
567.8/21.0
VGG16
70.83+0.22
69.57+0.21
07.22+0.43
632.2/27.4
568.5/22.6
381.4/19.0
CIFAR-100
Spline
72.18+0.26
71.54+0.29
70.0740.41
688.3/28.0
605.2/22.9
555.0/19.4
EB Spline
72.07+0.24
71.4620.23
70.29+0.36
512.2/19.9
429.1/15.3
378.9/18 1
Spline Improv.
-0.44
+0.23
-0.67
0.7x/0.8x
0.9x/1.0x
1.0x/1.3x
2008) for reducing the feature dimensions to the same before applying the spline pruning. However, we also consider factor analysis (FA) dimension reduction to demonstrate that spline pruning is not sensitive to the adopted dimension reduction methods as long as it can be used to measure the correlation between two units, and these FA experiments are provided Appendix C.
Spline pruning over SOTA CIFAR. Table compares the retraining accuracy, the total training FLOPs, and the total training energy of our spline pruning methods with four SOTA pruning baselines, including two unstructured pruning baselines (i.e., the original lottery ticket (LTT) training (Frankle & Carbin, 2019b) and SNIP (Lee et al., 2019)) and two structured pruning baselines (i.e., NS (Liu et al., 2017) and ThiNet (Luo et al., 2017)). The results demonstrate that our spline pruning again consistently outperforms all the corpetitors terms of the achieved accuracy and training efficiency trade-offs. Specifically, compared with the strongest competitor among the four SOTA basclines, spline pruning achieves 0.8 3.5 x training FLOPs reductions and 0.7
1.5 X energy cost reductions while offering comparable or even better (-0.67% 0.69%) accuracies. In particular, spline pruning consistently achieves 1.16 3.16 x
training FLOPs reductions than all the structured pruning baselines, while leading to comparable or better accuracies (-0.17% ~ 1.28%). More comparisons with baselines of pruning at initialization can be found in Appendix B.
Spline pruning over SOTA on ImageNet. We further investigate whether the spline pruning have consistent performance harder dataset, using ResNet-18/50 on ImageNet and benchmarking with eight SOTA pruning methods including ThiNet, NS, SFP, LeGR, GAT-0.5, GDP, C-SGD-50, and Meta Pruning.
11

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Table 3: Evaluating the proposed global spline pruning over SOTA pruning methods on ImageNet.
Pruning ratio
Top-1 Acc. (%)
Top-1
Top-5 Acc. (%)
Top-5 Acc.
Total Training
Total Training
Models
Methods
Improv. (%)
Improv. (%)
FLOPs (P)
Energy (MJ)
Unprumed
69.37
89.24
1259.13
98.14
10%
69.65
40.08
89.20
-0.04
2424.86
193.51
Res-Net-18
NS
30%
67.85
-1.72
88.07
-1.17
2168.89
180.92
SFP
30%
67.10
-2.47
87.78
-1.40
1991.94
158.14
10%
09.41+0.08
-0.16
89.04
-0.20
1101.24
95.63
EB Spline
30%
00.12
-1.76
87.99
-1.25
8:1 .00
82.85
Unpruned
75.99
92.98
2839.96
280.72
30%
72.04
-3.95
90.67
-2.31
4358.53
436.13
ThiNet
50%
71.01
-4.98
90.02
-2.96
3850.00
431.73
SFP
30%
74.61
-1.38
92.06
-0.92
4330.86
470.72
RosNes-50
LeGR
50%
75.3
92.4
-0.58
4174.74
GAL-0.5
40%
72.0
-3.99
91.8
-1.18
4458.74
440.73
GDP
40%
72.6
-3.39
91.1
-1.88
4487.14
443.54
C-SGD-50
50%
74.5
-1.49
92.1
-0.88
4117.91
407.04
Meta Pruting
50%
73.4
-2.59
3532266
349.12
30%
75.0820.11
-0.91
92.58
-0.40
2434.09
264.24
EB Spline
50%
73.37=0.18
-2.02
91.53
-1.45
1636.02
197.09
Specifically, spline pruning with EB detection (EB Spline) achieves reduced training FLOPs of 43.8%
57.5% and reduced training energy of 42.1% 54.3% for ResNet-50, while leading to top-1 accuracy improvement of -0.12% 3.04% (a top-5 accuracy improvement. of 0.18% ~ 1.91%). Consistently, EB Spline achieves a reduced training FLOPs of 44.7% 61.7% and reduced training energy of 39.5% ~ 54.2% for RcsNet-18, while leading to comparable top-1 accuracies (-0.24% ~ 0.71%) and top-5 accuracics (-0.16% 0.21%).
4.4 Ablation studies of the spline pruning method
Recalling that the only ayper-parametert p our spline pruning method (sce Equ.
PreResNet-101
VGG-16
Testing Accuracy (%)
Testing Accuracy (%)
of the main content), which balances the difference between the angles sus the biases. Here we conduct ab- lation studics to measure the retrain-
75
70
70
65
p-
65
ing accuracies under different values of for investigating its sensitivity, as shown
piu 50%
p- 30%
60
in Fig. 7. Without loss of generality, we evaluate two commonly used models, VGG-16 and PreResNet-101, on the rep- resentative CIFAR-100 dataset. Results
0.01
0.05
0.1
0.3
0.4
0.01
0.05
0.1
0.3
0.4
P
Figure Abalation studies of the hyperparameter p in our spline pruning on two models, VGG-16 and PreResNet-110 1011 show that spline pruning consistently performs well for wide range of values ranging from 0.01 to 0.4, which also generalizes to different pruning ratios (denoted by p). This set of experiments demonstrate the robustness of our spline pruning mothods.
5 Conclusions
We discover and bridge the connection between spline theory and network pruning techniques, providing explicit visualization and new insights into how pruning DN nodes affects the decision boundary, which well explains the presence of winning tickets and the importance of obtaining good initialization staring from overparametrization. Moreover, we extend these insights by proposing a pruning invariant metric to quantily the evolution of splines during training and detect the unified spline EB tickets. Finally, we leveraged the spline formulation of DNs to sharpen our understanding of different pruning policies, study the conditions in which pruning does not deteriorate performances, and develop a novel and more principled pruning strategy extending spline EB tickets; and extensive experiments demonstrated the superior performances
12

---

Published in Transactions on Machine Learning Research (07/2022)
(accuracy and energy efficiency) of the proposed method. The proposed spline viewpoint opens avenues to theoretically study novel and existing pruning techniques as well guide practitioners via the proposed visualization tools.
References
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In Advances in neural information processing systems, pp. 6158-6169, 2019.
Devansh Arpit and Yoshua Bengio. The benefits of vverpparameterization at initialization in deep relu networks. arXiv preprint arXiv:1901.0361, 2019.
David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding. Technical report, Stanford, 2006.
R. Balestriero and R. G. Baraniuk. A spline theory of deep networks. In Proc. Int. Conf. Mach. Learn volume 80, pp. 374 383, Jul. 2018.
Randall Balestriero and Richard Baraniuk. From hard to soft: Understanding deep network nonlinearities via vector quantization and statistical inference. In International Conference on Learning Representations, 2019.
Randall Balestriero, Romain Cosentino, Behnaam Aazhang, and Richard Baraniuk. The geometry of deep networks: Power diagram subdivision. arXiv preprint 1XXiv:1905008433, 2019.
Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Greedy layerwise learning scale to ima- genet. In International conference machine learning, pp. 583 583-593. PMLR, 2019.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? Tn Third Conference on Machine Learning and Systems, 2020.
M Emre Celebi, Hassan A Kingravi, and Patricio A Vela. A comparative study of efficient initialization methods for the k-means clustering algorithm. Expert systems with applications, 40(1):200-2100 2013.
Ting-Wu Chin, Ruizhou Ding, Cha Zhang, and Diana Marculescu. Towards efficient model compression via learned global ranking. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2020.
Xiaohan Ding, Guiguang Ding, Yuchen Guo, and Jungong Han. Centripetal sgd for pruning very deep convolutional networks with complicated structure. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.
2019.
Xin Dong, Shangyu Chen, and Sinno Pan. Learning to prune deep neural networks via. layer-wise optimal brain surgeon. Advances in Neural Information Processing Systems, 30, 2017.
Andre Esteva, Alexandre Robicquet, Bharath Ramsundar, Volodymyr Kuleshov, Mark DePristo, Katherine Chou, Claire Cui, Greg Corrado, Sebastian Thrun, and Jeff Dean. A guide to deep learning in healthcare. Nature medicine, 25(1):24 29, 2019.
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. arXiv preprint arXiv:1911.11133 2019.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019a. URL https://openrevier: net//forum?ddsrJJ--B3BBee
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. Tn International Conference Learning Representations, 2019b.
13

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249- 256, 2010.
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 315 323, 2011.
Greg Hamerly and Charles Elkan. Alternatives the k-means algorithm that find better clusterings. In Proceedings of the eleventh international conference on Information and knowledge management, pp. 600-607, 2002.
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.00149 2015.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. arXiv preprint arXiv:190.09001, 2019a.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceodings of Machine Learning Research, pp. 2696.2604. PMLR, 09-15 Jun 2019b. URL mlr. vatss///9//aann11... html.
https://proceede/
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human- level performance on imagenet classification. In Proceedings of the TEEE international conference on computer vision, pp. 1026 1034, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770 778, 2016.
Yang He, Guoliang Kang, Xuanyi Dong, Yanwei Fu, and Yi Yang. Soft filter pruning for accelerating deep convolutional neural networks. arXiv preprint 1686066808006666, 2018
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolu- tional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Tapas Kanungo, David Mount, Nathan Nelanyahu, Christine Piatko, Ruth Silverman, and Angela Y Wu. An efficient k-means clustering algorithm: Analysis and implementation. IEEE transactions on pattern analysis and machine intelligence, 24(7):881 892, 2002.
Kenji Kawaguchi, Jiaoyang Huang, and Leslie Pack Kaelbling. Effect of depth and width on local minima in deep learning. Neural computation, 31(7):1462 1498, 2019.
Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in neural information processing systems, pp. 598 605, 1990.
Yann LeCun, Yoshua Bengio, et al. Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks, 3361(10):1995, 1995.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. SNIP: SINGLE-SHOT NETWORK PRUNING BASED ON CONNECTION SENSITIVITY. In International Conference on Learning Representations, 2019. URL https://openreviiet http://eeee..ooomm//daa//a//....
Chaojian Li, Tianlong Chen, Haoran You, Zhangyang Wang, and Yingyan Lin. Halo: Hardware-aware learning optimize. In Proceedings of the European Conference on Computer Vision (ECCV), September 2020.
Shaohui Lin, Rongrong Ji, Yuchao Li, Yongjian Wu, Feiyue Huang, and Baochang Zhang. Accelcrating convo- lutional networks via global & dynamic filter pruning. In Proceedings of the SeeenthSe International Joint. Conference Artificial Intelligence, IJCAL-18.
14

---

Published in Transactions on Machine Learning Research (07/2022)
Shaohui Lin, Rongrong Ji, Chenqian Yan, Baochang Zhang, Liujuan Cao, Qixiang Ye, Feiyue Huang, and David Doermann. Towards optimal structured cnn pruning via generative adversarial learning. In Proceedings of the LEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2790 2799, 2019.
Shengchao Liu, Dimitris Papailiopoulls, and Dimitris Achlioptas. Bad global minima exist and sgd can reach them. arXiv preprint #rXiv:1906.02613 2019a.
Zechun Liu, Haoyuan Mu, Xiangyu Zhang, Zichao Guo, Xin Yang, Kwang- Tinng-Ting Cheng, and Jian Sun. Metapruning: Meta learning for automatic neural network channel pruning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1996-3305, 2019b.
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, pp. 2736-2744, 2017.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. In International Conference on Learning Representations, 2019c. URL her/forrumidd<221n333333
Jian-Hao Luo, Jianxin Wu, and Weiyao Lin. Thinet: A filter level pruming method for deep neural network compression. In Proceodings of the IEEE international conference on computer vision, pp. 5058-5066, 2017.
Andrew L Maas, Awni Y Hannun, and Andrew Y Ng. Rectifier nonlinearities improve neural network acoustic models. In Proc. icml, volume 30, pp. 3, 2013.
Dmytro Mishkin and Jiri Matas. All you need is a good init. arXiv preprint arXiv:1511.06422, 2015.
Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz. Pruning convolutional neural networks for resource efficient inference. arXiv preprint arXiv:1611.06440, 2016.
Guido Montúfar, Yue Ren, and Leon Zhang. Sharp bounds for the number of regions of maxout networks and vertices of minkowski sums. arxiv preprint arXiv:2104.0813: 2021.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Advances in neural information processing systems, pp. 2924-2932. 2014.
NVIDIA Inc. NVIDIA Jetson TX2. http:://www.viiiaa..omm http://wwwwa.....a...aaaaaaaaaaa embedded-systee wwstems/jetssn-ttaeteeee tx2// accessed 2019-09-01.
Xin Qian and Diego Klabjan. probabilistic approach to neural network pruning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8640 8649. PMLR, 18 18-24 Jul 2021.
Douglas A Reynolds. Gaussian mixture models. Encyclopedia of biometrics, 741:659 663, 2009.
Sebastian Ruder, An overview of gradient descent optimization algorithms. arXiv preprint arXiv:1609.04747, 2016.
Matthias Scholz, Martin Fraunholz, and Joachim Selbig. Nonlinear principal component analysis: neural network models and applications. Tn Principal manifolds for data visualization and dimension reduction, pp. 44 67. Springer, 2008.
Or Sharir and Amnon Shashua. On the expressive power of overlapping architectures of deep learning, International Conference on Learning Representations, 2018. URL http::::////peeeeeeeeeeee//////e HkNGssee-.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354 359,,59, 2017.
15

---

Published in Transactions on Machine Learning Research (07 (07/2022)
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. arXiv preprint arXiv:2009.1100 11094, 2020.
Iyya Sutskever, James Martens, George Dahl, and Geoffre Hinton. On the importance of initialization and momentum in deep learning. Tn International conference machine learning, pp- 1139-1147, 2013.
Hidenori Tanaka, Daniel Kumin, Daniel LK Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. arXiv preprint arXiv:2006.0544 2020.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. arXiv preprint arXiv:200..07376, 2020.
Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Yingran Lin, Zhangyang Wang, and Richard G. Baraniuk. Drawing carly-bird tickets: Toward more efficient training of deep networks. In International Conference on Learning Representations, 2020. URL https://openrev/// http//orrmmmddBBxssrssss
Yulun Zhang, Yapeng Tian, Yu Kong, Bineng Zhong, and Yun Fu. Residual dense network for image super-resolution. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 2472 2481, 2018.
Difan Zou and Quanquan Gu. An improved analysis training over-parameterized deep neural networks. Advances in Neural Information Processing Systems, pp. 2055-2064. 2019.
James Zou, Mikael Huss, Abubakar Abid, Pejman Mohammadi, Ali Torkamani, and Amalio Telenti. A primer on deep learning in genomics. Nature genetics, 51(1):12-18 18, 2019.
16

---

Published in Transactions on Machine Learning Research (07 /022)
A Algorithm for searching Spline EB tickets
Algorithm 1:
The Algorithm for Scarching Spline EB Tickets
1: Initialize the weights W and the FIFO queue Q with length l; while (epoch) < Ema do
Update W and r using SGD training; Calculate the distance between the input space partitions of the current and the previous networks, and then add it to Q
5: +=t+1
6: if Max(Q) < then
7: Return f(x; W) (Spline EB ticket);
end
end while
B Comparison with pruning at initialization baselines
We further supply another three pruning-ar at initializaaioon (unstructured parameter- wise pruning) methods, RigL. (Evci et al., 2019), GraSP (Wang et al., 2020), and SynFlow (Tanaka et al., 2020), as our baselines and present the comparison results shown in Tab. 4. We can that our method consistently outperforms the pruning-at-iniiaalzatiin baselines in terms of accuracy-efficiency trade-offs, achieving up to 2.68% accuracy improvement at comparable even (up to 3.2x) lower total training FLOPs.
Table 4: Evaluating global spline pruning method SOTA pruning at initialization methods CIFAR-10/100 datasets. All accuracies are averaged over three runs.
Retrain Accuracy (%)
FLOPs (P)
Setting
Methods
p=30%
p=50%
p=70%
p-30%
p-50%
p=70%
RigL
93.56+0.06
93.26=0.14
92.72=0.21
7,81
7.51
7.81
GraSP
93.21+0.05
92.83=0.13
92.57=0.25
7.5
7.5
7.5
SynFlow
03.25440.08
92.8620.16
91.7622019
7.5
7.5
PreResNet-101
Spline
94.1340.01
93.9220.12
92.0610.25
10.1
CIFAR-10
ED Spline
93.67:20.08
93.1820.15
92.32:20.28
4.26
2.74
Spline Improv.
+0.57%
+.092%
0.66%
+1.09%
-0.4%
+-0.6%%
0.6x
2.9x
RigL
92.65+0.05
92.72=0.13
92.40=0.18
15.6
15.6
15.6
CraSP
92.4940.01
91.47#0.11
90.79=0.17
15.3
15.3
SynFlow
92.74+0.06
01.8920.12
92.17:0.20
15.3
15.3
15.3
VGG-16
Spline
93.6220.08
93.4620.10
92.8520.21
26.4
25
19.6
CIFAR-10
EB Spline
93.2810..4
93.0520.17
91.9620.19
19.4
15.5
11.1
Spline Improv.
+0.88%
+1.13%
+0.74%
1.99%
+0.55%
2.06%
0.6x
Rigl.
72.5320.119
71.8720.28
69.9220.36
7.81
7.81
7.81
GraSP
72.09910.27
71.6620.15
69.6020.45
7.5
7.5
7.5
SynFlow
72.33+0.20
71.88=0.25
69.86=0.35
7.5
7.5
7.5
PreResNet-101 CIFAR-100
Spline
73.79+0.22
72.0 22.0440.24
08.24+0.37
12.6
10.9
9.36
Spline
72.67+0.21
71.99=0.25
60.74+0.33
3.84
2.46
Spline Improv.
+1.24% ~ 1.7%
10.16%
0.38%
-0.18%
0.14%
0.6x
3.2x
p=10%
p=30%
p=50%
p=10%
p=30%
p=50%
RigL
71.40+0.26
70.98=0.16
70.76+0.37
15.6
15.6
15.6
GraSP
69.50+0.29
69.25+0.29
68.43+0.45
15.3
15.3
15.3
VGG-16
SynFlow
72.08++0.25
71.48=0.25
71.20
15.3
15.3
15.3
CIFAR-100
Spline
18.22..0.
71.5420.29
70.07=0.41
28
22.9
19.4
EB Spline
72.07+0.21
71.4620.23
70.29
19.9
15.3
11.8
Spline Improv.
+0.1% +2..8%
+0.06%
42.29%
-0.91%
+1.8%
0.6x
1.3x
C Global Spline pruning with FA dimension reduction
We further adopt factor analysis (FA) dimension reduction methods on PreResNet-101 and VGG-16. The results shown in the Tab. 5. We that our spline based pruning method is not sensitive to
17

---

Published in Transactions on Machine Learning Research (07/2022)
Table 5: Global spline pruning with PCA and FA dimension reduction methods.
Accuracy (%)
Setting
Methods
p=30%
p=50%
p= 70%
Spline (FA)
91.2710.06
91.2610.15
91.97+0.21
Spline (PCA)
94.13+0.04
93.92+0.12
92.0610.25
Spline (FA)
93.10+00.09
93.25+0.12
92.49+0.22
VGG-160CIFAR-10
Spline (PCA)
93.62+0.08
93.4640.10
92.85+0.21
Spline (FA)
74.37
72.9440.21
68.0240.29
PreRkssVe-1011@01AAR-1000
Spline (PCA)
73.79+0.22
72.0440.24
68.2440.37
p=10%
p=30%
p=50%
Spline (FA)
72.20+0.19
71.99+0.32
70.6240.39
VCG-160CIFAR-100
Spline (PCA)
72.18+0.26
71.54+0.29
70.07+0.41
the adopted dimension reduction methods as long as it can be used measure the correlation between two units. We think that studying the theoretical guarantees what methods and in which regime those methods are in fact preserving that information would be an interesting future research direction to provide further theoretical guarantees.
D How universal is the EB for different optimization methods?
We detect EB tickets using different optimization methods, including SGD, Adam, Adagrad, and RMSprop (Ruder, 2016), and report both the emerging epochs and the retraining accuracies of detected EB tickets NeeResNet-101 and VGG-16 in the Tab. 6. The results show that our spline EB tickets consistently emerge at early training stages and perform on par with their unpruned counterparts, and thus are empirically observed to be universal to different optimization methods.
Table 6: EB tickets detection using different optimization methods.
Retrain Accuracy (%)
Setting
Methods
BB Emerge Epoch
Unpruned
p=30%
p=50%
EB (SGD)
61
93.66
93.67+0.08
13.18+0.13
(Adam)
89.63+0.15
80.63+0.18
89.2610.18
PreResNet-101 101IIFAR--10
EB (Adagrad)
33
90.6420.09
90.76+0.11
90.7920.09
EB (RMSprop)
80
87.41 16
86.8340.1 17
86.37+0.20
FB (SGD)
24
92.71+0.07
93.2840.04
93.05+0.17
EB (Adam)
41
90.1110.08
91.25+0.09
90.73+0.19
VGG-16@CIFAR-10
(Adagrad)
27
90.17+0.10
91.0440.12
89.55+0.22
EB (RMSprop)
88
87.35+0.09
87.86+0.16
88.10+0.24
E How universal is the EB for adversarial initialization?
also detect EB tickets with the adversarial initialization (Liu et al., 2019a). The results shown in the Tab. 7 demonstrate that our EB tickets can consistently be found under the adversarial initialization and perform on par with their corresponding unprumed dense networks after being retrained.
Table 7: EB tickets detection using adversarial initialization.
Retrain Accuracy (%)
Setting
Methods
EB Emerge Epoch
Unpruned
p=30%
p=50%
[Random Init.)
93.66+0.04
93.6740.08
93.1840.13
PreResNett MalkesNNe-100@CCFAR---0
EB (Adv, Init)
81
93.33+0.06
93.3840.10
93.36+0.11
EB (Random Init.)
24
92.71
93.2840.04
93.05+0.17
VGG-I68CIFAR-10
FB (Adv. Init)
40
92.20=0.05
92.63+0.04
91.6620.14
18

---

Published in Transactions on Machine Learning Research (07/2022)
F Background of MASO and its ties with our method
The entire CPA/max-affine spline formulation of deep networks (DNs) has been extensively studiod before (Balestriero & Baraniuk, 2018). However the prior published works merely focus on studying the various spline properties that one can obtain on a DN from the MASO formulation. Those works did not study the contributions that we propose in this paper, Lee, (1) bridging the connection between spline theory and network pruning techniques, (2) discovering that a DN's spline mappings exhibit an early-bird (EB) phenomenon whereby the spline's partition converges at early training stages, and (3) leveraging the afore- mentioned EB finding to develop a principled pruning strategy that focuses on a tiny fraction of DN nodes whose corresponding spline partition regions actually contribute to the final decision boundary.
Needless to say that, we do not claim that the MASO formulation is one of our contribution. In fact, we refer the readers to those prior works in Sec. 2. Instead, we propose to build-upon the MASO formulation to in-turn study pruning in deep networks, and this (as far as we are aware) has not been done (even succinctly) previously.
G Analysis about the connection between LTH and Spline theory
At the lowest level, LTH and spline theory are connected as follows. A DN partitions its input space according to power diagram subdivision that is formed by a recursive subdivision process through the layers. Fach subdivision is analytically known and involves the layer weights of each unit and the biases. When pruning unit at layer I, the subdivisions of layers 1, 1,, are unchanged, the power diagram of layer I is altered only by removal of a single hyperplane from its boundary, and all the subdivisions of layers 1+ +1, 1, I are altered.
Additionally, in classification lasks, the decision boundary is constrained to be linear within each region of this input space partition. Hence, for the decision to be nonlinear in part of the space, the input space partition at that location must contain it is possible to obtain an input space partition obtained by power diagram subdivision each containing significantly less regions, that can still be positioned such that the decision boundary solves the task at hand. This is the exact phenomenon we tried to highlight in Fig. 2 and Fig. 3 where we depicted that the same (or similar) decision boundary (in red) could be obtained from a much reduced input space partition.
least two regions. The LTH, in terms of splines, states that
While we have limited ourselves to mostly empirical evaluations and validations as an important first step, we agree that an in-depth theoretical study would be immensely beneficial for the community. This is something we are hoping to achieve in next study as this theoretical question is incredibly challenging, for which this work can provide critical insights and inspirations.
H Additional Visualization
We supply the additional visualization of spline trajectories to Fig. 8.
DN initialization: an alternative to pruning
The initialization dilemma and the importance of overparameterization. In the case of DNs. most initialization techniques focus on maintaining feature maps statistics bounded through depth to avoid vanishing of exploding gradient (Glorot & Bengio, 2010; Sutskever et al., 2013; Mishkin & Matas, 2015). However, incorporating data information into the DN weights initialization is done in Kmeans with say kmeans++ remains to be developed for DNs. Hence, overparametrization allows successful training, and a posteriori, one can remove the redundant parameters and obtain a final model with much better performances versus the non-overparametrized and non-pruned counterpart. This is the key motivation of Early Bird tickets. Furthermore, the parallel between DNs and K-mcans most relevant as has been shown in (Balestriero et al., 2019) that the DN decision process relies on an input space partition based on centroids that is very similar to the one of K-means and which thus benefit in the same way to overparametrization.
19

---

Published in Transactions on Machine Learning Research (07 (0722222)
Node
Node
Node 3
Node 4
Node 5
Layer
Node
Node 2
Node
Node
Node
Layer 2
Decision Boundary
Layer 3 (Classifier)
Figure 8: Additional visualization of the partitioning and subdivision layer after layer, where each node introduces spline in the input space which is depicted under the current partitioning with highlighted path linked via a dotted line.
Beyond this geometric aspect, overparametrization has been proven to facilitate optimization (Arpit & Bengio, 2019) and to position the initial parameters close to good local minima (Allen-Zhu al., 2019; Zou & Gu, 2019; Kawaguchi et al., 2019) reducing the number of updates needed during training.
Remark 1.
Winning lickets are the resull of employing overly poramelrized DNs which are simpler to optimize and produce better performances, current optimization techniques can not escape from poor local minima and advanced DN initialization (near good local minima) is unknown.
We further support the above remark in the following paragraphs where we demonstrate how the absence of good initialization coupled with non-optimal optimization problems impacts performances unless over- parametrization is used, in which case winning tickets naturally emerge.
DN initialization alternative: layerwise pretraining. We saw in the previous section that the concept of winning tickets emerges from the need overparametrize DNs which in turn emerges naturally from overparamctrizing grcatly facilitates training and improves final
architecture scarch and cross-validation results. We now show that if better initialization of DNs existed, would have the ability to train minimal DN directly and thus would not resort to the entire pruning pipeline.
We convey the above point with a carefully designed experiment. We consider three cases. First, the case employ a minimal DN with random weights initialized from random Kaiming initialization (He et al., 2015). Second, we consider the same minimal DN architecture but with weights initialized based on unsupervised layerwise pretraining which consider used) (Belilovsky et al., 2019). In both cases, training is done the classification task in the same manner. Third, consider overparametrize DN trained with the lottery ticket (LT) method (training, pruning, and re-training). The final models of the three cases have the same architecture (but different weights based on their own training method). We report their classification results in Table 8, from which we can see that especially for very small final DNs (high pruning ratios) LT models outperform a randomly initialized DN, but in turn a well initialized DN is able to outperform LT training. From this, we see that the ability of pruning methods and, in particular, LT produce better-pent setter-performing minimal DNs than directly training the minimal DN lies in the lack of good inilialization for Deep Networks.
data-aware initialization (no label information is
20

---

Published in Transactions on Machine Learning Research (07 (07/2022)
Table 8: Accuracies layerwise (LW) pretraining, structured pruning with random and lottery ticket ini- tialization.
Setting
Pruning Ratio
Random Init.
Lottery Init.
LW Pretrain
30%
93.33+0.01
93.57+0.01
93.08
50%
93.07+0.03
93.55+0.03
93.08
VGG-16 on CIFAR-10
70%
92.68+0.02
93.44+0.01
92.81
90%
90.48+0.06
90.4110.23
90.88+0.02
10%
71.49+0.03
71.70+0.09
71.14+0.02
30%
71.34+0.10
71.24+1.18
71.35+0.01
VGG-16 on CIFAR-100
50%
67.74+1.05
69.73+1.15
70.19+0.01
70%
60.44+4.98
66.95
67.40+0.83
VGG-16 CIFAR-10
VGG-16 on CIFAR-100
Testing Accuracy (%)
94
Testing Accuracy (%)
71
66
92
61
56
90
Layerwise Pretrain
51
Layerwise Pretrain
Lottery Initialization
Lottery Initialization
46
88
0.873
2.034
3.196 4.357 5.519
0.234
1.687
3.140 4.594
6.047
FLOPs
1e16
FLOPs
1e16
Figure 9: Accuracy vs. efficiency trade-offs of lottery initialization and layerwise pretraining.
In fact, for high pruning ratios, layerwise pretraining even offers a more energy efficient method overall (including the pretraining phase) than LT training, shown in Fig. 9, we further compare the required FLOPs when networks are initialized using lottery initialization and layerwise pretraining, respectively. We observer that (1) when the pruming ratio is low (i.e., 50%), networks with lottery initialization require smaller number of computational FLOPs to provide good initialization for the pruned network, while leading to comparable or even higher retraining accuracy: and (2) when the pruning ratio is higher, layerwise pretraining requires a much smaller number of computational FLOPs as compared to training highly overparametrized dense networks. Such a phenomenon opens a door for investigating the following two questions, which we leave as our further works.
Is there clear boundary/condition /cnndition to show whether should start from overparameltization consider pretraining good initialization for samll DNs instead?
How much verparametrizaliig do need to maintain better trade-offs between accuracy and efficiency, compared to other initialization ways (e.g., layerwise pretraining)?
As the amount of different architectures grows rapidly and the specificity of those architectures can vary drastically, simple layerwise pretraining falls short of providing an advanced initialization solution. For example, is not clear how layerwise pretraining can be used with a DenseNet Huang al. (2017) where some parameters connect layers that are far apart in the architecture. Hence, while we believe searching for improved initialization strategies, we now focus on studying LT training and DN pruning as they provide universal solution.
J Analysis about why there are redundant partition boundaries
21

---

Published in Transactions on Machine Learning Research (07 (07/202) /022)
1.0
0.08
0.8
0.06
0.6
0.04
0.02
0.2
-1.0
-0.5
0.0
1.0
100 200
300
X
Layer width
Figure 11: Left: Depiction of simple (toy) univariate regression task with target function being sawtooth with two peaks. Right: The l training crror (y-axis) as a function of the width of the DN layer (2 layers in total). In theory, only 4 units are requires to perfectly solve the lask hand with a ReLU layer, however we see that optimization in narrow DNs is difficult and gradient based learning fails find the correct layer parameters. As the width increased as the difficulty of the optimization problem reduces and SGD manages to find good set of parameters solving the regression task.
Network pruming literature follows the chaining of (i) over- parametrization, (ti) training, and (ii)) pruming to obtain a small but critical subnetwork, i.e., "winning ticket" that
achieve high accuracies. This offers a powerful alternative to training small network from scratch good initialization for such sparse network is not known (Frankle & Carbin, 2019a; Blalock et al., 2020) making the optimization challenging. This strategy finds benefits not only with DN but also with tradi- tional methods such as K-means,
Test Accuracy (%)
94
tickets
92
kmeans+
90
which case pruning re- moves centroids (Kanungo al., 2002; Hamerly & Elkan, 2002; Celebi et al., 2013). We propose to briefly employ K-means to demonstrate the superiority of such pruning strategies. As shown in Fig. 10, consider K-means+ (Arthur & Vas- silvitskii, 2006) as a ground-truth method to represent. good initialization (denoted as kmeans+++), where we know a priori the number of clusters (64) for artificial data generated from a Gaussian Mixture Model (GMM) (Reynolds, 2009) with spherical and identical covariances. Against that baseline, we perform the three-step pruning strategy over multiple runs and with varying numbers of initial clusters to generate winning initialization (denoted as tickets). In all case the clusters will be pruned to 64 (true number of Gaussians) from the initial number that varies from 64 to 128 (æ-axis of Fig. 10). We observe that the winning initialization perform near-optimal results (i.e., closer to kmeans++) when starting from overparancttriiztion (i.e., initial clusters z 100), otherwise suffer from large accuracy drops. We highlight that employing overparameter- ization facilitate finding winning lickets. From the above experiments is clear that in the absence of "optimal" initialization small DNs, pruning is the current preferred solution to obtain performing minimal architectures.
88
80
100
120
Number of Initial Clusters
Figure 10: K-means experiments on toy mixture of 64 Gaussian.
Additional results on initialization and pruning
Next we extend the creeparanetizztioon-ruiii vs. initialization insights to univariate DNs on a carefully designed dataset. Considering simple unidinensional sawtooth as displayed in Fig. 11 with P peaks (here
22

---

Published in Transactions on Machine Learning Research (07 (07/2022)
P 2). In the special case of single hidden layer with a ReLU activation function, must have least 2P units to perfectly fit this function with the weight configuration being [Wi]i, 1,[bi -k with k = 1,...., Dj and [W2]1,1 = 1, [, (11))))11122221) 2,..., DI. Note that these weights are not unique (other ones can ideutically fit the function) and are given as an example. At initialization, if the DN has only 2P units, the probability that a random weight initialization arranges the initial splines in way to allow effective gradient based training is low. Increasing the width of the initial network will increase the probability that some of the units are advantageously initialized throughout the domain and aligned with the natural input space partitioning of the target function (different regions for different increasing decreasing sides of the sawtooth). This is what empirically illustrated in Fig. 11 (right) where one can see that even repeating multiple initializations of a DN without overparametrization does not allow to solve the task, while overparametrizing, training, and then pruning that together preserve only the correct number of units allow for better approximation.
L Relation between activation patterns and spline partition of input space
Subdivision Lines. Every layer in deep networks (DNs) with piecewise non- linearities (e.g. ReLU activation) can be viewed as subdivision lines for parti- tioning the given input space (Balestriero et al., 2019). For example, suppose the DNs' imput space is shaped as square grid with N x N data points, we extract the activations from one intermediate layer of & hidden nodes, then each node corresponds one subdivision line to distinguish non-zero activations in the input grid, thus we have & subdivision lines in this layer, same as the number of hidden nodes. From such geometry perspective, there are two good charactoristics to leverage: (1) Subdivision lines the first layer are lincar affine functions (aking layer parameters as slopes and biases, following subdi- vision lines are piecewise linear, whose turning points are exactly located at the subdivision lines in previous layers; (2) The derived subdivision lines the final classification layer are exactly the network decision boundary. Such
<0
Z
>
N
Visualize one subdivision line on grid. connection provides us a new perspective to analyze how the decision boundary are gradually formulated and what network compression methods (e.g., pruning, quantization) really mean from such geometry perspective.
Figure 12:
M Early-bird visualization on test and random samples
To investigate what happens to the partitioned regions that do not contain any training data, we redraw Fig. 5 (early-bird visualization) on test samples, and show the visualization of early-bird phenomenon at Fig. 13.
N Spline trajectory and EB tickets with Leaky ReLU activation
We redraw Fig. 4 (spline trajectory) and Fig. (carly-bird visualization) when using Leaky ReLU as activation functions, and show the corresponding spline trajectory at Fig. 14 and the visualization of early-bird phenomenon at Fig. 15. From these figures, we can consistently observe that. the splines will adapt during the early phase while converging at later training stages, demonstrating that the early-bird phenomenon still holds under the Leaky RcLU activation functions. In addition, we supply the pruning experiment comparisons using networks with Leaky-ReLU activation functions to Table 9, from which we see that the spline pruning consistently outperforms all baselines in terms of both accuracy and efficiency, leading to -0.44% +1.38% accuracy improvement and up to 4x training flops savings.
23

---

Published in Transactions on Machine Learning Research (07 (07/202) 2022)
25
14
50
15
75
75
75
75
100
125
125
325
125
150
150
250
150
VGG-16 CIFAR100
PreResNet-101 CIFAR100
VGG-16 CIFAR100
ProResNet-101 CIFAR100
(a) Visualization Training Samples
(b) Visualization on Testing Samples
25
25
08
06
100
200
04
61
150
350
VGG-16 on CIFAR100
ProResNet-101 on CIFAR100
(c) Visualization on Random Samples
Figure 13: visualization of the early-bird (EB) phenomenon when using training samples, testing samples, and random samples, respectively.
Replace ReLU with Leaky ReLU
Loss
0.3
www
2000
4000
6000
8000
10000
Iterations
Spline Trajectory for FCNet
Figure 14: Visualization of spline trajectories using FCNet with Leaky ReLU activation functions.
Table 9: Evaluating our spline pruning method over baselines when using Leaky ReLU activation functions.
Retrain Accuracy (%)
FLOPs (P)
Setting
Methods
p=30%
p=50%
p=70%
p=30%
p=50%
p= 70%
NS
03.5440.08%
93.1840.12 12%
20.89+0..3%
13.9P
12.7P
11.0P
ThiNet
92.1820..099
91.57+0.155
90.25+0..25%
13.2P
10.6P
8.65P
Spline
0.05%%
92.74+0.169
91.11+0.21%
13.6P
12.1P
10.1P
PreResNet-101 on CIFAR-10
EB Spline
92.76+0.07%%
92.1340.13%
90.66++..25%
6.00P
4.26P
2.74P
Spline Improv.
-0.44%
+1.38%
1.1x 4.0x
24

---

Published in Transactions on Machine Learning Research (07/2022)
Replace ReLU with Leaky ReLU
25
0.8
50
75
75
100
0.4
0.2
150
150
(a) PreResNet-101 on CIFAR10 (b) PreResNet-101 on CIFAR100
Figure 15: Visualization of the early-bird (FB) phenomenon when training PreResNet-101 with Leaky ReLU
activation functions.
Comparison under 90% pruning ratios
As shown in the Table 10, the proposed spline pruning outperforms the baselines across two models (PreResNet-101 and VGG-16) and two datasets (CIFAR-10 and CIFAR-100), leading to -0.35% +63.87% accuracy improvements. Note that the nelwork slimming (NS) method suffers from bottleneck layers due to the "over-pruning" channels on specific layers.
Table 10: Evaluating our spline pruning method over baselines under 90% pruning ratios.
Datasets
Model
Methods
Accuracy (p=90%)
NS
77.63+ 1.21%
ThiNet
97.80+1.100)
Spline
87.96+0.95%
ProResNet-101
EB Spline
18.1570.87%
Spline Improv.
+0.35% +1055%
NS
89. 19..7..766%
CIFAR-10
ThiNet
86.90+0.89%
Spline
89.1140.67%
VGG-16
EB Spline
89.24:0.71%
Spline Improv.
+0.11% +2.34%
NS
28.90+2.56%
ThiNet
60.66+1998%
Spline
58.97+1.75%
PreResNet-101
EB Spline
60.31 1.92%
Spline Improv.
-0.35%
+31.41%
NS
1%
CIFAR-100
ThiNet
42.35%
Spline
69.37+1.6799
VGG-16
EB Spline
64.87+1.93%
Spline Improv.
+8.56%
63.87%
P Comparison with iterative pruning methods
We further supply the comparison with network slimming with the mentioned iterative pruning method (NS-IP). As shown in the Table 11, our spline pruning again outperforms those methods in terms of both
25

---

Published in Transactions on Machine Learning Research (07/2022)
accuracy and efficiency, leading to -0.47% +1.11% accuracy improvement and up to 7.1x training flops savings. We will add this set of experiments and discussion in our revision.
Table 11: Evaluating our spline pruning method over iterative pruning baseline.
Retrain Accuracy (%)
FLOPs (P)
Setting
Methods
p=30%
p=50%
p=70%
p=30%
p=50%
p=
NS-IP
03.7410.06%
92.7210. 13%
92.5310.24%
23.6P
21.6P
18.7P
Spline
94.13=0.04%
93.92+ 121%
92.06=0.25%%
13.6P
12.1P
10.1P
PrefeeNNtt-101 on CIEAR-10
EB Spline
03.67:0.0897 08%
93.1840.133 13%
02.32%0.28%
6.00P
4.26P
2.74P
Spline Improv.
+0.39%
+1.20%
-0.47%
1.7x
6.8x
NS-IP
72.68+0.18%
71.82+0 26%
69.86+0331%
23.31'
21.3P
17.5P
Spline
73.79=0.22%%
72.04+0.24%
68.2420.37%
12.6P
10.9P
9.36P
PreResNet- 101 on CIFAR-100
Spline
72.67:0.21%
71.9910.25%
.9.7420.33%
5.44P
3.84P
2.46P
Spline Improv.
+1.11%
+0.22%
-0.12%
1.8x
7.1x
Quantitative distances of different layers along training trajectory
As shown in the Table 12, the quantitative distance of early layers converges faster than later layers, indicating that the base partition regions divided by first few layers will not change too much since the very carly epochs.
Table 12: Record of the quantitative distance between input space partitions of different layers, i.e., early, middle, or later layers, along the training trajectory.
Quantitative Distances
Datascts
Models
Layers
10th epoch
40th epoch
80th epoch
120th epoch
160th epoch
Early (1st)
0.247
0.197
0.061
0.021
0.003
VGG-16
Medium (8th)
0.538
0.424
0.183
0.024
0.003
Late (16th)
0.579
0.512
0.236
0.027
0.004
CIFAR-100
Early (Ist)
0.621
0.562
0.296
0.023
0.002
PreResNet--10 101
Medium (16th)
0.704
0.612
0.273
0.025
0.003
Late (32th)
0.781
0.728
0.376
0.038
0.005
26


Reviews:
[{"review_id": "NxRug5GAUy", "reviewer": "Reviewer_8fbB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. This paper offers a new perspective on looking at neural network pruning.\n2. Some observations this paper makes align with the prior work.\n\n\n**Weaknesses**\n\n1. It's unclear whether the paper solves the research problem proposed in the abstract.\n2. In many cases, the paper makes an overclaim.\n3. The evaluation is weak.\n4. The paper has more room for improving writing quality.\n\n**Detailed Comments**\n\n*Problem scope and solutions*\n\nThis paper claims to tackle the problem, \"the literature has remained largely empirical and hence provides little insights into how pruning affects a DN's decision boundary and no guidance regarding how to design a principled pruning technique.\"\n\n(1) I am less convinced that this paper addresses this problem. The paper proposes a new perspective, but most of the paper's experiments and explanations remain empirical (not shown in a principled way). Thus, it's \"another\" empirical study that this paper bashes and offers many explanations without principles.\n\n(2) It's a bit unclear why we should look at neural network pruning from spline theory. Prior work [1, 2] also proposed a way to look at neural network pruning using probabilistic perspective or Hessians (second-order characteristics). I'd like to know what's the limit of those works and what spline theory offers more.\n\n[1] Qian et al., A Probabilistic Approach to Neural Network Pruning (ICML)\n[2] Xin et al., Learning to Prune Deep Neural Networks via Layer-wise Optimal Brain Surgeon (NeurIPS)\n\n(3) In fact, this paper's observations have also been observed in the prior work, too. For instance, an early-bird phenomenon may be the one we can expect from the lottery ticket hypothesis. It could be a weak contribution.\n\n**Claims that are not clear or saying more than it be**\n\nI wrote down some examples below. I think those are not just the writing issues; as if the paper removes (or towns down) those claims, the contributions become weaker.\n\n(1) (Abstract) The paper claims \"we develop new theory and visualization tools.\" However, spline theory is *employed* in this paper. It's also unclear what are visualization tools this paper offers.\n\n(2) (Intro) The paper claims \"such understandings are crucial for one to study the possible failure modes.\" It's unclear what the failure modes are, and the experiments do not show whether a new technique is useful for understanding those.\n\n(3) (Sec 3.1) The paper says that \"EB tickets have been found to be universal.\" But, I am not convinced by the universality as the claim is just based on empirical observations, which is the same as the prior work. As the paper identifies \"empiricalism\" in studying neural network pruning, it's unclear whether this paper's perspective offers something more to the existing knowledge.\n\n**Weak evaluations**\n\n(1) First and foremost, the evaluation takes an empirical approach---running pruning on multiple datasets and networks. In addition to that, the improvements are marginal (+0.08 ~ +2.18). In this case, I would like to see the standard deviations in all the Tables.\n\n(2) Comparison with the other perspectives on neural network pruning is required.\n\n(3) Efficiency: It's not clear what the baseline is. If the baseline is parameter-wise pruning, it's unfair to compare with them as the paper uses channel-wise pruning. It must be compared with the SoTA channel-wise pruning. If it's actually compared with the SoTA channel-wise pruning, I'd like to elaborate that in the experimental setup more clearly.\n\n(4) PCA: PCA already reduces some redundant information from the input, and I am not sure why it can \"maintain\" the information from the prior layer.\n\n(5) Figure 1: it's not clear about the experimental setup. Are those figures conceptual diagrams help understand the paper or the actual results from some experiments?\n\n\n**Writing**\n\n(1) As this paper aims to make contributions to neural network pruning, it would be nice to explain a bit more about \"Max-affine spline DNs\". In Sec 2, it just explains \"what MASO\" is and then continues with \"The form is clear that there exists an underlying layer input space partition based on the realization ...\" But, the connection is less clear to me.\n\n(2) Figures and Tables do not contain some necessary information. For example, Figure 1 does not share any experimental settings, so we won't know how and where the results come from. Also, there are some notations, e.g., \"speed\" in Figure 2 and 3, which is not defined clearly in the caption (or in the main contents). Figure 5 also does not offer any clues what those plots are and how we should interpret them. Many more..", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Summary**\n\nThis paper proposes a new perspective on understanding neural network pruning. The paper employs spline theory to analyze how the decision boundaries of neural networks evolve over training and how they are removed when we apply pruning. The paper exposes an early-bird phenomenon in which the spline's partition converges at early-training stages, aligned with the observation from the lottery-ticket hypothesis paper. Building on this observation, the paper proposes a new pruning technique that identifies a set of redundant groups of nodes that can be pruned with less accuracy degradation. In evaluation, the paper shows that the proposed pruning techniques often perform better than the state-of-the-art pruning methods.\n\n**Contributions**\n\n1. This paper makes an empirical connection between spline theory and neural network pruning.\n2. The paper proposes a technique for finding an early-bird ticket that is less sensitive to the pruning settings.\n3. The paper proposes a new pruning technique based on the spline theory and shows some effectiveness over the prior pruning methods.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. Clarify the problem this paper tackles.\n2. Motive more clearly why we use \"spline theory\" to look at neural network pruning\n3. Comparison to the prior work (on new perspectives of looking at neural network pruning)\n4. Town down the strong claims (than it be) and provide convincing results backing some claims\n5. Provide the standard deviations for all the experiments in the tables.\n6. Clarify the experiments on \"efficiency.\"\n7. Clarify why PCA can maintain the information.\n8. Clarify MASO and its connection to NN pruning in Sec 2.\n9. Clarify the captions (and the relevant texts) of Figures.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oPBq7kFqmz", "reviewer": "Reviewer_hftF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n1. The connection between spline theory and network pruning is interesting and novelty. It could provide a good perspective to develop new pruning method in the community.\n2. The experiments demonstrate it has a good ability to get a better pruning results over recent baselines in both spline case and early bird case. The improvement is pretty consistent but a little of marginal.\n3. The paper is well-written in general and easy to follow.\n\n\nCons:\n1. While the connection could be clearly visualization in the two given examples, there is limited theory foundation to know why the connection is legit and solid. The main theoretical part is in proposition 1. However, it is mainly based on another reference.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper connects the spline theory to understand the deep neural network pruning problem and utilizes the theory to propose a new pruning method. Specifically, it first shows that the only parts of subdivision splines are useful for decision boundary and it is ok to remove other splines, which is a good match with the pruning objective. At the same time, the important splines don't change too much in the training procedure so that it could be act as a good way to be used as early bird tickets. The paper then proposes an importance metric based on the cosine similarity between slope and biases. Several experiments hav been down to show the proposed pruning method is more effective than some recent baselines on a series architecture and datasets.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. It would be better if it could do more analysis both on empirically or theoretically to justify the proposed connection.", "broader_impact_concerns": "None as far as I am concerned.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "VzIe3m7Qv7", "reviewer": "Reviewer_DjUH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper proposes a new perspective for analyzing and explaining network pruning methods.\n \n2. This paper also develops new pruning methods that do not require pre-defined pruning strategies. \n\n3.  The evaluation was conducted on different network structures and datasets with different scales. \n\nWeakness:\n1. This paper might overclaim regarding its theoretical contribution.\n\n2. The baseline choices can be further justified, and more results can be presented. ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new way to explain how network pruning methods influence the network decision boundary and develop new pruning methods based on spline and spline partition. The paper compares its methods with a SOTA pruning method on different network structures and demonstrates their advantage. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "My main concerns about this work are the theoretical contribution and result completeness. To address these two concerns and other relatively minor ones, I suggest the authors make the following revision of the paper. \n\n1. The paper kind of claiming that it proposes a new theoretical foundation for new pruning methods. Indeed, the paper introduces spline to explain how pruning works. The related analysis is mostly qualitative in text, and the theoretical analysis is not enough. I would suggest the authors provide some related theorems with rigorous proof, such as why pruning is equal to removing subdivision splines; (2) whether the proposed pruning methods could guarantee to find true EBs, if yes, under what conditions, if no, whether errors are bounded, etc. The paper would be much stronger if the authors could provide related theoretical analysis. If those are kind of hard to add, I would suggest the authors lower the tune of the new theory.\n\n 2. The paper claims it compares the proposed method with 10 baselines on three datasets. First, I only find the results of CIFAR 10/100 in both the main text and appendix. It would be great if the authors could also include the results on ImageNet better in the main text. This is because including ImageNet could better demonstrate the scalability of the proposed methods on large-scale datasets with high-dimensional inputs. In addition, I would also suggest the authors comment on 1. why selecting those 10 baselines, 2. the cases where the proposed method works worse than the selected baselines. \n\n3. Finally, this is relatively minor but good to have. It would be great if the authors could give a brief and formal introduction to spline theory and related claims in the background section. In the current version, I can get the point about what's spline and how it is related to DNNs. It would be easier for readers to understand if this information is provided before 3.1. And the claim \" the DN decision boundary must be linear within the regions of the DN input space partition.\" is relatively new for readers that are not familiar with spline and space partition. A quick explanation in the background section is appreciated. ", "broader_impact_concerns": "I do not find this paper has any ethical concerns and thus may not need to include a broader impact statement. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to employ the spline theory to understand and improve current techniques in deep network pruning. In evaluation, the paper shows that the proposed pruning techniques often perform better than the state-of-the-art pruning methods.

It received three reviews. After author response, all the reviewers provided "Leaning Accept" recommendations, and appreciated the authors' efforts in providing a new perspective for analyzing and explaining network pruning methods. This connection between spline theory and network pruning is interesting and novel, and empirical results are comprehensive, with experiments conducted on different network structures and datasets with different scales.

On the other hand, reviewers have pointed out places where this paper can be further improved, such as toning down the strong claims, adding a brief and formal introduction to spline theory and related claims in the background section, and further improving paper clarify. 

In summary, the authors have done a good job at responding to these review comments, and the Action Editor would like to recommend "Accept with minor revision". The authors are encouraged to incorporate the promised changes that have not been incorporated yet in the final version of the paper.
Decision: Accept (poster)