Max-Affine Spline Insights Into Deep Network Pruning
Authors: Randall Balestriero
Haoran You
Zhihan Lu
Yutong Kou
Huihong Shi
Yingyan Lin
Richard Baraniuk
Venue: ICLR 2022 Submitted (2022)
Keywords: DNN Interpretability
Network pruning
Max-affine spline theory
Visualization

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 be trained from scratch to achieve high accuracy. To date, 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. Using a recently developed spline interpretation of DNs, we develop new theory and visualization tools that provide new insights into how pruning DN nodes affects the decision boundary. We discover that a DN's spline mappings exhibit an early-bird (EB) phenomenon whereby the spline's partition converges at early training stages, bridging the recently developed max-affine spline theory and lottery ticket hypothesis of DNs. We leverage this new insight to develop a principled and efficient pruning strategy that focuses on a tiny fraction of DN nodes whose corresponding spline partition regions actually contribute to the final decision boundary. 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 state-of-the-art methods. All the codes will be released publicly upon acceptance.

Under review as a conference paper at ICLR 2022
MAX-AFFIN SPLINE INSIGHTS INTO DEEP NETWORK PRUNING
Anonymous authors Paper under double-blind review
ABSTRACT
State-of-the-art (SOTA) approaches to deep network (DN) training over- parametrize the model and then prune a posteriori to obtain a "winning ticket" subnetwork that can be trained from scratch achieve high accuracy. To date, the literature has remained largely empirical and hence provides little insights into how pruning affects DN's decision boundary and no guidance regarding how design a principled pruning technique. Using a recently developed spline inter- pretation of DNs, we develop new theory and visualization tools that provide new insights into how pruning DN nodes affects the decision boundary. We discover that DN's spline mappings exhibit early-bird (EB) phenomenon whereby the spline's 's partition converges at early training stages, bridging the recently devel- oped DN spline theory and lottery ticket hypothesis of DNs. We leverage this new insight to develop a principled and efficient pruning strategy that focuses on a tiny fraction of DN nodes whose corresponding spline partition regions actually contribute to the final decision boundary. Extensive experiments four networks and three datasets validate that our new spline-based DN pruning approach re- duces training FLOPs by up to 3.5x while achieving similar or even better accu- racy than current state-of theth--rr methods. All the codes will be released publicly upon acceptance.
INTRODUCTION
Deep Networks (DNs) are powerful and versatile function approximators that have reached outstand- ing performances across various tasks, such 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 suc- cession of linear and nonlinear operators (LeCun al., 1995; He al., 2016; Zhang et al., 2018). With tremendously increasing need for DNs' practical deployments, one line of research aims to produce simpler, energy efficient DN by pruning dense and overparametrized one, e.g. removing either weights, nodes, filters, layers, or any combination of these options from a DN architecture, leading to a much reduced computational cost (Frankle & Carbin, 2019b; Han et al., 2015; Chin et al., 2020; Liu et al., 2017). Recent progresses (You et 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 a lack of explicit understanding of its impact on DN's decision boundary plus a lack of theoretical tools for deriving pruning techniques in a principled way. Such understandings are crucial for one to study the possible failure modes of pruning techniques, to better decide which to use based on a given application, to design pruning techniques possibly guided by some a priori knowledge about the given task and data. Our core motivation is to bridge the affine spline formulation of DNs and the recently developed empirical pruning techniques, e.g., lottery ticket hypothesis Frankle & Carbin (2019b); You et al. (2020); Evei et al. (2019); Su et al. (2020); Blalock et al. (2020).
In this paper, we shed new light on the inner workings of pruming techniques from a spline per- spective, 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

---

Under review as a conference paper at ICLR 2022
(b) Node Pruning
Layer 1
Layer 2
Layer (Classifler)
(a) Input Space Partitioning
(c) Weight Pruning
Figure I: (a) Input space partitioning presents how deeper layers successively subdivide the space, where the newly introduced boundaries are in dark and previously built ones in grey. We see that: (i) the turning point of splines in later layers are exactly located at previous ones, and (äi) splines in the final classification layer exactly the decision boundary (denoted blue lines). Additional examples are supplied in Appendix H; (b) Node (structured) pruning removes entire subdivision splines; (c) Weight (unstructured) pruning quantizes the partition splines to be colin- ear to the space axes. Both (b) and (c) lead to the less expressiveness of the final decision boundary.
pruning acts upon DN by removing/altering the partition boundaries as demonstrated Fig. I, and therefore pruning 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, 201 2019a)) by studying their impact the DN input space partition, demonstrating how and when can pruning be used without sacrificing the final performances. Finally, we demonstrate how to derive new pruning scheme based our gained understandings that reaches competitive performances. In order to ease our development, slightly abuse notations and refer DN as being overparametrized whenever 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:
be pruned
[CI] We discover and bridge the connection between spline theory and network pruning techniques. Specifically, we relate the pruning of DN nodes or weights to (i) the DN input space partition, (ii) the per-region affine parameters, and (iii) the decision boundary, providing the explicit interpretation of existing empirical pruning strategies at various granularity levels (either structured or unstructured).
[C2] We further extend these insights by proposing a partition-based metric 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] derive an efficient pruning strategy from first principles, which only focuses on DN nodes whose corresponding spline partition boundaries contribute the final decision boundary. A series of experiments on various benchmarked models and datasets validate that our pruning method achieves 3.5x training FL.OPs reduction and maintains similar even better accuracies over tate-of-the-ar pruning techniques, while being principled and interpretable.
BACKGROUND AND RELATED WORKS
DN transforms input æ through composition of L layers f L, form the final prediction: ((x) (s"
(=)) Each layer (nonlinear) mapping taking as input Dd ddieensional feature map and producing D³ -imennsional one, where D is the eth feature map's dimension'; ; each layer's parameters are collected in 0g. For fully-connected and activation function layer, 0g comprises the Dº D dense matrix W' and the D d'-dieensianal bias vector b² For convolution operators (LeeCun al., 1995), the dense matrix f is replaced with circulant block circulant matrix Cf for channel-wise convolutions and summations.
consider matrices and tensors as flattened vectors for clarity
2

---

Under review as a conference paper at ICLR 2022
Max-affine spline DNs. A key result of (Montufar et al., 2014; Balestriero & Baraniuk, 2018) is the reformulation of current DN layers with (Beaky>ReLLuLLinnaAAAll Value activation functions as spline operators and in particular as Max-Affine Spline Operator (MASO). With this formulation each layer's input-output mapping can be written as
(x) max (A + v.). r=1....,ft
with the maximum taken coordinate-wee wise.. By the form of Eq. (1) it is clear that there exists an underlying layer input space partition based on the realization of the maximum operator; for a study of this partitioning, see (Balestriero et al., 2019). Jointly, the layers combine their input space partition to form the DN imput space partition Q. 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), the upper bound in the number of regions (Montufar et al., 2014; Montúfar et al., (221).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 pruming impacts those weights and/or nodes directly, this will offer us new ways to study pruning in DNs' imput space. More background on DNs, their spline formulation, and its difference with our work can be found in Appendix F.
Network pruning, Pruming is widely used DN compression technique reducing the number of activated nodes (Liu et al., 2019c; LeCun et al., 1990) a given model. The common pruning scheme adopts a three-step routine: (i) training a large model with more parameters than the desired final DN, (ii) pruning this overly large trained DN, and (iii) fine-tuning the pruned model adjust the remaining parameters and restore as best as possible the performance lost during the pruning step. Those three steps can be iterated to get a highly-sparse network (Han et al., 2015). Within this routine, different pruning methods can be employed, each with a specific pruning criteria, granular- ity, and scheduling (Liu et al., 2019c; Blalock et al., 2020). Those techniques roughly fall into two unstructured pruning (Han et al., 2015; Frankle & Carbin, 2019b) and structured pruning (He et al., 2018; Liu et al., 2017; Chin et al., 2020). Regardless of pruning methods, the trade-offs lie between the amount of pruning performed on model and the final accuracy. For various energy efficient applications, novel pruning techniques have been able to push this tradc-off favorably. The most recent theoretical works on DN pruning relies on 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- con-pruned counterpart. Later, (You et al., 2020) showed that those winning tickets could be identified in the early training stage of the unpruned model. Such sub-networks are denoted as early-bird (EB) tickets.
categories:
Despite the above discoveries, the DN pruning literature lacks an explicit understanding and visu- alization via theoretical analysis that would bring insights into (i) current pruning techniques and (ii) observed phenomenons such EB tickets, while leading principled pruning techniques. We propose to approach this task by leveraging the spline viewpoint of DNs to provide novel interpreta- tions 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 pruning at various granularity levels. Then extend such insights by detecting spline EB tickets through a pruning invariant partition- based metric. Finally, we leverage the new insights to derive an principle and efficient pruning strategy.
3.1 INTERPRETING PRUNING FROM A SPLINE PERSPECTIVE
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 pruming 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 spe-
cific in Tf are pruned, in which case node and weight pruning become identical. From this
3

---

Under review as a conference paper at ICLR 2022
100
Data Grid
80
14
Unpruned
Prune 20%
Prune 40%
12
Layyer
2x
10
RELU Act.
FCleet Accuracy (%) FCNet (epochis)
Layer
20x2
50
40
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 that the decision boundary remains X X-shape until 80% nodes are pruned; and (ii) idcally, one blue subdivision line would be sufficient to provide two turning points for the decision boundary, e.g., visualization 80% sparsity.
100
lo
P
In
Or
8:
95
10.0
Unpruned
Prune 20%
Prune 40%
Data Grid
90
Gem-BW-RELV
20
1065.3
Canolet Accurscy (4) ConnMet Speed (epechimini
300+10
20 60 Pruning Ratio (%)
Prune 60%
Prune 80% ConvNet Splines Visuallzation
Prune 90%
ConvNet
Figure 3: Classification task pruning using ConvNets, where to produce these visuals, we choose two images from different classes to obtain 2-dimensional slice of the 764-dimensional input space (grid depicted on the left). We thus obtain a low-dimensional depiction the subdivision splines that 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 of splines are necessary provide the turning points of final decision boundary.
perspective, we can already identify the reason why pruned networks are less expressive than the overparametrizeed variants (Sharir & Shashua, 2018) as pruned DNs' input space partition and final decision boundary shape are limited compared to their unpruned counterparts. Thus this limitation occurs first on the DN partition which in turn constrains the regions in the space where the decision boundary can be nonlinear as we recall that the DN decision boundary must be linear within regions of the DN input space partition.
Despite the constraints that pruning imposes on the DN input space partition, classification perfor- mances 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 boundary geometry does not rely on the partition regions that are being affected by pruning. We demonstrate and provide explicit visualization of the above in Fig. and Fig. 3 with fully-connected networks (FCNets) and convolutional networks (ConyNets). respectively. The observation consis- tently shows that only parts 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, we 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 long as the remaining subdivision lines are positioned to allow the decision boundary geometry to remain intact. We also extend the above experiment to high dimensional case with MNIST classification and DN with two convolutional layers, 20 filters, and kernel sizes of and 5, respectively in Fig. that most of the
long as the needed decision
3. By adopting the same channel pruming method as in (Liu al., 2017), pruned nodes remove subdivision lines that were not crucial for the decision boundary and thus only have small impact on the final classification performance. Hence, as long as pruning leaves least

---

Under review as a conference paper at ICLR 2022
Figure 4: Visual- ization of spline trajectories, which mainly during early phase of training demon- strating the lottery ticket hypothesis for DN partitions.
0.30
05-
3.4
Loss
adapt
0.24
0.00
2093
Iterations
0900
5000
5000
39000
Epochs
(a) Spline Trajectory for FCNets
(b) Spline Trajectory for ConvNets
those few subdivision lines, the final performances will remain high. Apart from the empirical study, also provide some analysis about the connection between pruning (e.g, lottery ticket hypothesis (LTH)) and spline theory in Appendix G.
3.2 SPLINE EARLY-BIRE TICKETS DETECTION
Early-Bird (EB) tickets (You et al., 2020) provides a method to draw winning ticket sub-networks from large model very early during training (10% 20% of the total number of training epochs). The EB drawn is based on an priori designed pruning strategy and hyperparameters and compares how different (in terms of which nodes/channels are removed) are the hypothetical pruned models through the training steps; this method outperforms SOTA methods (Frankle & Carbin, 2019b; Liu al., 2017). The main limitation of EB lies in the need to define a priori pruning technique (itself depending on various hyperparameters) Based on 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 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 's evolution at different training stages in Fig. 4 (a) and (b), under the same settings Sec. 3.1. From this, 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 early the 2000-th iteration (w.rt. 10000 iterations for FCNets) and the 30-th epoch (w.r.t. 160 epochs for ConvNets). Additionally, 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 in Appendix D and E.
Quantitative distance between input space partitions. To draw EB tickets based on the evolution of DN input space partitions, we first need to provide metric that conveys such information. First, recall that each region from the DN input space has associated binary code based on which side of the subdivision trajectories the regions lie (Montufar et al., 2014; Balestriero & Baraniuk, 2018). assign each datum the code of the region it lies in
Given large collection of data points, (found simply based on the sign of the per-layer feature maps). As training occurs and the partition adapts, the code associated with 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 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 lower value (w.r.t. warmer tem- perature) indicates a smaller spline distance (and thus DNs with similar partitions). We consistently observe that such distance becomes small (i.e., < 0.15) in the first few epochs under different models and datasets settings. indicating the EB phenomenon, but now captured in 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 are smaller than a predefined threshold of 0. 0.,5, denoted by the red block in Fig. 5. The detailed algorithm is provided in Appendix A. We conclude by emphasizing that as opposed to the usual EB
5

---

Under review as a conference paper at ICLR 2022
25
25
25
0.6
75
75
75
100
100
100
125
02
150
150
150
(a) AlexNet CIFAR10
(b) VGG-16 CIFAR100
(c) PreResNet-101 CIFAR100
Figure 5: Visualization of the early-bird (EB) phenomenon, which can be leveraged to largely reduce
the training costs due to the less training of costly overparametrized DNs.
tickets drawn in (You et al., 2020), our formulation provide a more interpretable scheme that is invariant to the pruning strategy well its hyperparameters (e.g., the pruning ratio). Hence, our formulation allows for a unified solution that does not require to adapted based on the pruning technique that users experiment with.
3.3 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 formed by successive subdivision process involving each per-layer input 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 priori which regions of the imput space partition are helping in solving the task is extremely challenging, since 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 is simpler to obtain, however, is how redundant some of the layer weights/units in terms of the forming of the DN partition relative to other units/weights. From that, will become easy to prune the redundant units/weights their impact the forming of the decision boundary is already carried by another unit/weight.
When considering the layer input space partition, we can identify "re- dundant" units based on how each unit impacts the partition with re- spect to other units. For example, two units have biases and slope vec- tors proportional to each other, then one can effectively remove one of the two units without altering the layer input space partition. While this is a pathological case, we will demon- strate that the angles between per- unit slope matrices and inter-bias dis- tances measure such redundancy. We first introduce our pairwise re- dundancy measure as the following equation:
DN Partition !
Pruned ?
2
0
-1
-2
-2
-3
2
2 1
2
-3-2-1
-3-2
3
Figure 6: Left: a small (L 2, = D2 8) DN input space partition. Middle: the pruning criteria as in Eq. (2). Right: the pruned input space partition based on the criteria.
Jk.. [W" Iw..) [[[W"].. I2lll["]] Jw., ll2
(k, k')
where We refers to the corresponding slope matrices of the k-th unit, is hyper-parametts mea- suring the sensitivity of the difference in angle versus the biases. In the case of convolutional layer, We 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 ming w N (k, k') where the obtained couple (As, 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 pruning onto the DN input space partition minimized.
Proposition 1. Given a layer and its input space partition, removing sequentially one of the two units, & and k', for which N¹ (k,K k3) 0, leaves the layer imput space partition unchanged.

---

Under review as a conference paper at ICLR 2022
Table 1: Evaluating the proposed layerwise spline pruning over SOTA pruning 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.66
93.66
93.66
92.71
92.71
92.71
30%
93.48
93.56
93.07
+0.08
93.29
93.21
92.83
-0.08
CIFAR-10
50%
92.52
92.55
92.37
+0.03
91.85
92.13
92.23
+0.38
70%
91.27
91.33
91.33
+0.06
88.52
89.68
88.65
+1.16
Unpruned
73.10
73.10
73.10
71.43
71.43
71.43
10%
71.58
71.58
73.14
+1.56
71.6
71.78
72.28
+0.68
CIFAR-100
30%
70.70
70.13
72.11
+1.41
70.32
71.15
71.59
+1.27
50%
68.70
69.05
70.88
+2.18
66.1
69.92
69.96
+3.86
70%
66.51
67.06
68.41
+1,90
61.16
63.13
64.01
+2.85
The above result exploits (Balestriero et al., 2019). In short, if NV kt, K') for any positive p. then the layer-partitinn boundaries (of layer E) of units k. k' perfectly overlap. The DN partition boundaries correspond to the layer-partition boundaries backpropagated through the earlier layers to reach the data space. But this process is continuous operator i.c., the layer-partitin will produce DN partition boundaries that overlap.In In practice, units with small enough but nonzero (K, k') are also highly redundant and can be removed. We provide an example of this procedure in Fig. 6, where a small DN imput space partition (layer trajectories in black and layer in blue) is depicted. In the middle we visualize the measurements from Eq. (2) that trying to find similar "partition trajectories" from layer 2 seen 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.
boundaries that overlap
Efficiency of the spline pruning. Note that instead of using parameter-wise pruning, we perform channel-wise pruning of which the pruning overhead is negligible when evaluating across four mod- els and three datasets. For example, ResNet-50 has about 20k channels and needs 100G FLOPs to prune, which is only 1/30,000,000 of the training costs (3000P FLOPs).
4 EXPERIMENT RESULTS
In this section, first describe our experiment settings, and then benchmark the proposed spline pruning method over ten SOTA pruning baselines in the context of layerwise pruning and gloabl p.
pruning, respectively. Finally, we present ablation studies in terms of the only
4.1 EXPERIMENT SETTINGS
Models, datasets, baslines, and metrics: Models & Datasets: We consider four DNN models (Pre VGG-16, and ResNet-
both the CIFAR-10/100 and ImageNet datasets following 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 al., 2018), LeGR (Chin et al., 2020), GAL-0.5 (Lin al., 2019), GDP (Lin al.), C-SGC-50 (Ding et al., 2019), and meta pruning (Liu et al., 2019b). Metrics: We evaluate in terms of the retraining accuracy, total training FLOPPs, 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 settings: For the CIFAR-10/100 datasets, 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 total of 90 epochs while the learning rate drops the 30-th and 60-th epochs, respectively. In all the experiments, the batch size is set to 256, and an SGD solver is adopted with a momentum of 0.9 and weight decay of 0.0001, following the setting of (Liu et al., 2019c). Additionally, / in Equ. 2 is set to 0.05 for all experiments except for the ablation studies. All experiments
in server with ten NVIDIA 2080 Ti GPUs.
4.2 LAYERWISE SPLINE PRUNING
Recall that the spline pruning policy is done by solving arg min (k, k¹). By regard k as the index of channels for convolutional layers, we are able conduct channel pruning in layerwise
7

---

Under review as a conference paper at ICLR 2022
Table 2:
Evaluating our global spline pruning method over SOTA methods on CIFAR-10/100
datasets. Note that the "Spline Improv." denotes the improvement of our spline pruning (w/ or
w/o EB) as compared the strongest baselines. All accuracies are averaged over five runs.
Retrain acc.
Energy cost (KJ)/LOPs (P)
Setting
Methods
30%
5=50%
p=70%
p=30%
p=50%
p=70%
LT (one-shol)
93.7
93.21
92.78
6322/14.9
6322/14.9
6322/14,9
SNIP
93.76
93.31
92.76
3161/7.40
3161/7.40
3161/7.40
93.83
93.42
92.49
5270/13.9
4641/12.7
4211/11.0
PreResNet-101 CIFAR-10
ThiNet Spline
93.39
93.07
91.42
3579/13.2
2656/10.6
1901/8.65
94.13
93.92
92.06
4897/13.6
4382/12.1
3995/10.1
EB Spline
93.67
93.18
92.32
2322/6.00
1808/4.26
1421/2.74
Spline Improv.
+0.3
+0.5
-0.46
1.4x/1.2x
1.5x/2.5x
1.xx/3.2x
LT (onc- sho-shoot
93.18
93.25
93.28
746,2/30.3
746.2/30.3
746.2/30.3
SNIP
93.2
92.71
92.3
373.1/15,1
373.1/15.1
373.1/15.1
NS
93.05
92.96
92.7
617.1/27.4
590.7/25.7
553.8/23.8
VGG16
ThiNet Spline
92.82
91.92
90.4
631 5/2226
383 9/190
380. 1/16.6
CIFAR-10
93.62
93.46
92.85
643.5/26.4
603.4/25.0
538. 538.1/194 1/19.6
Spline
93.28
93.05
91.96
171.4
436. 1/15.5
370.7/11.1
Spline Improv.
+0.42
+0.21
-0.43
0.8x/0.8x
0.9x/1 Oxx
1.0x/1.4x
LT (one-shop shoe-shot)
71.9
71.6
69.95
6095/14.9
6095/14.9
6095/14.9
SNIP
72.34
71.63
70.01
3047/7.40
3047/7.40
3047/7
72.8
71.52
68.46
4851/13.7
4310/12.5
3993/10.3
PreResNet-101 CIFAR-100
ThiNet
73.1
70.92
3603/13.2
2642/10.6
1893/866
Spline
73.79
72.04
68.24
4980/12.6
4413/10.9
4008/9.36
EB Spline
72.67
71.99
69.74
2388/5,44
1821/3.84
1416/2.46
Spline Improv.
+0.69
+0.44
-0.27
1.3x/1.4x
1.5w/28xx
1.3x/355x
p=10%
p=30%
p=50%
p=10%
p=30%
p=50%
LT (one-shol)
72.62
71.31
70.96
741.2/30.3
741.2/30.3
741.2/30.3
SNIP
71.55
70.83
70.35
370.6/15.1
370.6/15.1
370.6/15.1
NS
71.24
71.28
69.74
636.5/29.3
592.3/27.1
862.8/24.0
VGG16
ThiNet
70.83
69.57
67.22
632.2/27.4
568.5/22.6
381.4/19.0
CIFAR-100
Spline
72.18
71.54
70.07
688.3/28.0
605, 2/222/
555.0/19.4
Spline
72.07
71.46
70.29
512.2/19.9
429.1/15.
378.9/118
Spline Improv.
-0.44
+0.23
-0.67
0.7x/0.8x
0.9x/L.0x
L0x//133x
manner. Table shows the comparison between the spline pruning (w/ and w/o EB detection) and SOTA network slimming (NS) method (Liu et al., 2017) on CIFAR-10/11 datasets. We can see that the spline pruming consistently outperforms NS, achieving -0.08% 3.86% accuracy improvements. This set of results verifies 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 to 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., 2008) for reducing the feature dimensions to the same before applying the spline pruming. PCA is well motivated as we aim to maintain as much information about the filters while reducing their dimensionality. 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 can be used to measure the correlation between units, and these FA experiments are provided in Appendix C.
Spline pruning over SOTA on CIFAR. Table compares the retraining accuracy, the total train- ing 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 (LT) train- ing (Frankle & Carbin, 2019b) and SNIP (Lee et al.. 2019)) and two structured pruning basclines (i.e., NS (Liu et al., 2017) and ThiNet (Luo al., 2017)). The results demonstrate that our spline pruning again consistently outperforms all the competitors in terms of the achieved accuracy and training efficiency trade-offs. Specifically, compared with the strongest competitor among the four SOTA baselines, spline pruning achieves 0.8 x 3.5 x training FLOPs reductions and 0.7 x 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 x 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.
8

---

Under review as a conference paper at ICLR 2022
Table 3: Evaluating the proposed global spline pruning over SOTA pruning methods on ImageNet.
Prusing ratio
Top-1 Acc. (%)
Top-1 Acc.
Top-5 Acc. (%)
Top-5 Acc.
Total Training FL.OPs
Total Training Energy (MJ)
Models
Methods
Improv. (%)
Improv. (%)
Unpruned
69.57
89.24
1259.13
98.14
10%
69.65
-0.08
89.20
-0.04
2424.86
193.51
NS
30%
67.85
-1.72
88.07
2168.89
180.92
ResNet-
SFP
30%
67.10
-2.47
87.78
-1.46
1991.94
158.14
10%
69.41
0.16
89.04
0.20
1101.24
95.63
EB Spline
30%
67,81
-1.76
87.99
-1.25
831.00
82.85
Unpruned
75.99
92.98
2839.96
280.72
30%
72.04
-3.95
90.67
-2311
4358.53
456.13
ThiNet
50%
71.01
-4.98
90.02
-2.96
3850.03
431.73
SFP
30%
74.61
-1.38
92.06
-0.92
4330.86
470.72
LeGR
50%
75.3
-0.69
92.4
-0.58
4174.74
412.66
ResNet-50
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.94
407.04
Pruning
50%
73.4
-2.59
3532.63
349.12
30%
75.08
-0.91
92,58
00.40
2434.09
264.24
EB Spline
50%
73.37
-2.62
91.53
-1.45
1636.00
197.09
Spline pruning over SOTA on ImageNet. We further investigate whether the spline pruning have ImageNet and benchmarking with eight SOTA pruning methods including ThiNet, NS, SFP, LeGR, GAL-0.5, GDP, C-SGD-50, and Meta Pruning. Specifically, spline pruning with EB detection (EB Spline) achieves reduced training FLOPs of 43.8% % ~ 57.5% % and a 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 1.1 ~ 1.9 1.91 %). Consistently, EB Spline achieves a reduced training FLOPPs of 44.7% 61.7% % and reduced training energy of 39.5% 54.2% for ResNet-18, while leading comparable top-1 accuracies (-0.24% ~ 0.71%) and top-5 accuracies (-0.16% ~ 0.21%).
consistent performance in harder dataset, using ResNet-18/50
4.4 ABLATION STUDIES OF THE SPLINE PRUNING METHOD
Recalling that the only hyper- parameters p in our spline pruning method (see Equ. 2 of the main tent), which balances the difference between the angles versus the biases.
PreResNet-101
VGG-16
Testing Accuracy (5)
Tecting Accuracy (96)
75
75
70
70
Here we conduct ablation studies to measure the retraining accuracies under different values of p for inves- tigating its sensitivity, as shown in Fig. 7. Without loss of generality, we evaluate two commonly used models, VGG-16 and 100, pruning consistently performs well for a wide range of p 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 methods.
65
p
65
P=10%
p.
p --30%
60
P. 7074
Figure 7: Abalation studies of the hyperparameter p in our spline pruning on two models, VGG-16 and PreResNet- 101. the representative CIFAR-100 dataset. Results show that spline
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 quantify the evolution of splines during training and detect the unified spline EB tickets. Finally, we leveraged the spline formulation DNs to sharpen our understanding of different pruning policies, study the conditions in which pruning does not deteriorate perfor- mances, and develop a novel and more principled pruning strategy extending spline EB tickets; and extensive experiments demonstrated the superior performances (accuracy and energy efficiency) of the proposed method. The proposed spline viewpoint opens new avenues to theoretically study novel and existing pruning techniques well guide practitioners via the proposed visualization tools.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameter- ized 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 over-parametteriztion at initialization in deep relu networks. arXiv preprint arXiv:1901003111, 2019.
David Arthur and Sergei Vassilvitskii. k-means+4: 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 nonlin- carities via vector quantization and statistical inference. In International Conference on Learning Representations, 2019. URL https: opwpreeeee......eeoo/ee net heatt/oorumiiidSyyyerr
Randall Balestriero, Romain Cosentino, Behnaam Aazhang, and Richard Baraniuk. The geometry of deep networks: Power diagram subdivision. arXiv preprint arXiv: 1rXiv:1905.08443 2019.
Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Greedy layerwise learning can scale to imagenet. In International conference on machine learning, pp. 583-55333 5933. PMLR, 2019.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? In Third Conference on Machine Learning and Systems, 2020.
M Emre Celebi, Hassan A Kingravi, and Patricio A Vela. A comparative study of efficient initial- ization methods for the k-means clustering algorithm. Expert systems with applications, 40(1): 200-210, 2013.
Ting- Wu Chin, Ruizhou Ding, Cha Zhang, and Diana Marculescu. Towards efficient model com- pression 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,
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 Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Frich Elsen. Rigging the lottery: Making all tickets winners. arXiv preprint 11111:191..11134, 2019.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019a. URL https:// // openreview net/ worrmmiidzzii 21-
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference Learning Representations, 2019b.
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 249-256, 2010.
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In Proceedings the fourteenth international conference on artificial intelligence and statistics, pp. 315-323, 2011.
Greg Hamerly and Charles Elkan. Alterntives to the k-means algorithm that find better cluster- ings. In Proceedings of the eleventh international conference on Information and knowledge management, pp. 600-607, 2002.
10

---

Under review as a conference paper at ICLR 2022
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:1901. 1901.1911, 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 Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2596-2604. PMLR, 09-15 Jun 2019b. URL https: ftttps://proceedingg mll. wrw.s//v7/111 h 9a. html.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference computer vision, pp. 1026-1034, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. 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 180.:1800800666 2018.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 4700-4708, 2017.
Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu. An efficient k-means clustering algorithm: Analysis and implementation. IEEE transactions on pattern analysis and machine intelligence, ((17):81--99) 2002.
Kenji Kawaguchi, Jiaoyang Huang, and Leslie Pack Kaelbling. Effect of depth and width local minima deep learning. Neural computation, 31 (177):44221499, 2019.
Yann LeCun, John $ 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, (36)(10): 1995.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. SNIP: SINGLE-SHOT NETWORK PRUNING BASED ON CONNECTION SENSITIVITY. In International Conference Learning Representations, 2019. URL https: opwpreveew..e.ee/// http://oooumn.ddliiiiiieeeee.e
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. Ac- celerating convolutional networks via global dynamic filter pruning- In Proceedings of the TTentt--Seventh International Joint Conference on Artificial Intelligence, IJCAI-18.
Shaohui Lin, Rongrong Ji, Chenqian Yan, Baochang Zhang, Liujuan Cao, Qixiang Ye, Feiyue Huang, and David Doermann. Towards optimal structured cnn pruning via generative adver- sarial learning. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2790-2799, 2019.
Shengehao Liu, Dimitris Papailiopoulos. and Dimitris Achlioptas. Bad global minima exist and sgd can reach them. arXiv preprint 1rX6v:1996.00 02613, 2019a.
Zechun Liu, Haoyuan Mu, Xiangyu Zhang, Zichao Guo, Xin Yang. Kwang-Tine Cheng, and Jian Sun. Metapruning: Meta learning for automatic neural network channel pruning. In Proceedings of the IEEF/CVF International Conference Computer Vision, pp. 3296-3305. 2019b.
11

---

Under review as a conference paper at ICLR 2022
Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang. Shoumeng Yan, and Changshui Zhang. Learn- ing efficient convolutional networks through network slimming. Proceedings of the IEEE International Conference Computer Vision, pp. 2736-2744, 2017.
Zhigiaan
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
https: hwppeeeeeeeeeeeeeeeeeeeeeeeeeeee net www..eeeeoouumeeeeeeeeeeeeee fow.mmid=r..lnnrrr..
Jia Luo, Jianxin Wu, and Weiyao Lin. Thinet: A filter level pruning method for deep neural network compression. In Proceedings of the IEEE international conference computer vision, pp. 5058-5066, 2017.
Andrew Maas, Awni Y Hannun, and Andrew Y Ng. Rectifier nonlinearities improve neural net- work acoustic models. In Proc. ieml, volume 30, pp. 3, 2013.
Dmytro Mishkin and Jiri Matas. All you need a good init. arXiv preprint arviv: 1511001211.. 2015.
Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz. Pruming convolutional neural networks for resource efficient inference. arXiv preprint arXiv:161 Sefi::6111.06444 106440, 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.08133 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. https::/www.nvv hwtp://wwwwwii.aaaa//./ wttiddi...comeeoo ccom/en-wee autonomous-machhinee 01.
/tt.nnneeeeeeeeee/eeee/ee eeweededdbdddeeeeeeeeeeeeedeeded sts-ssttstts//ttstttt////// accessed 2019-09-
Douglas A Reynolds. Gaussian mixture models. Encyclopedia biometrics, 741:659-663, 2009.
Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv:1609.04747, 2016.
arXiv preprint
Matthias Scholz, Martin Fraunholz, and Joachim Selbig. Nonlinear principal component analy- sis: neural network models and applications. In 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. In International Conference on Learning Representations, 2018. URL https: / //openzeview. wttp://wwwwe.ttommteeeeeeee hett/oorum2id--Hiaseee.
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-3555 2017.
Jingtong Su. Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang, and Jason D Lee. Sanity- pruning methods: Random tickets can win the jackpot. arXiv preprint arXiv:2009,1 1094, 2020.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance initial- ization and momentum in deep learning. In International conference machine learning, pp-
1139-1147, 2013.
Hidenori Tanaka, Daniel Kunin, Daniel LK Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. arXiv preprint arXiv:2006.05467, 2020.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. arXiv preprint arXiv:2002.07376, 2020.
12

---

Under review as a conference paper at ICLR 2022
Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang. Xiaohan Chen, Yingyan Lin, Zhangyang Wang, and Richard G. Baraniuk. Drawing early-bird tickets: Toward more efficient training of deep networks. In International Conference Learning Representations, 2020. URL .wweenreviewweeeee https: www.reeeeiieeeeeee ew net /tt.://mmmdmnxrrrrsss.
Yulun Zhang, Yapeng Tian, Yu Kong, Bineng Zhong, and Yun Fu. Residual dense network for image super-resolution. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2472-2481, 2018.
Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks, Advances Neural Information Processing Systems, pp. 2053-2064, 2019.
James Zou, Mikael Huss, Abubakar Abid, Pejman Mohammadi, Ali Torkamani, and Amalio Telenti. A primer deep learning in genomics. Nature genetics, 51(1): 18, 2019.
13

---

Under review as a conference paper at ICLR 2022
A ALGORITHM FOR SEARCHING SPLINE EB TICKETS
Algorithm 1:
The Algorithm for Searching Spline EB Tickets
Initialize the weights W and the FIFO queue Q with length
2: while / (epoch) < maz do
3: Update W and using SGD training:
4: Calculate the distance between the input space partitions of the current and the previous networks, and then add to Q.
5: t ++1
6: if Max Q) e then
7: Return f(;; W) (Spline EB ticket);
8: end if
9: end while
B COMPARISON WITH PRUNING AT INITIALIZATION BASELINES
We further supply another three pruning-at-initee inttiaailiiiioiionnn methods, RigL. (Evci et al., 2019), GraSP (Wang et al., 2020), and SynFlow (Tanaka al., 2020), results as shown in Tab. 4. We can see that our method consistently outperforms the pruning-at- initialization baselines in terms of accuracy-elle efficieney trade-offs, achieving up 2.68% accuracy improvement at comparable or even (up to 3.2x) lower total training FLOPs.
baselines and present the comparison
Table 4: Evaluating our global spline pruning method over SOTA pruning at initialization methods on 1IFAR-10/100 datasets. All accuracies are averaged over three runs.
Accuracy (%)
FLOP' (P)
Setting
Methods
p=30
p=50%
p=70% %
p=30%
p=50%
p=70%
RigL
93.56
93.26
92.72
7.81
7.81
7.81
GraSP
93.21
92.83
92.57
7.5
7.5
7.5
SynFlow
93.25
92.86
91.76
7.5
7.5
7.5
PreResNet- 101 CIFAR-10
Spline
94.13
93.92
92.06
13.6
12.1
10.1
Spline
93.67
93.18
Spline Improv.
+0.57
+0.92%
+4.66
+11.9%
+0.56%
2.9%
Righ.
92.65
92.72
92.4
1..66
15.6
15.6
GraSP
92.49
91 91.47
90.79
15.3
15.3
15.3
SynFlow
92.74
91. 898
92.17
15.3
15.3
15.3
VGG-16
Spline
93.62
93.46
92.85
26.4
25
19.6
CIFAR-10
ER Spline
93.28
Spline Improv.
+4.88
+1.13%
+0.74%
1,99%
+0.45%
2.06 %
0.6x
1.4x
RigL.
72.55
71.87
69.92
7.81
7.81
7.81
GraSP
72.09
71.66
69.6
7.5
7.5
7.5
SynFlow
72.33
71.88
69.86
7.5
7.5
7.5
PreResNet-101
Spline
73.79
72.04
12.6
10.9
9.36
CIFAR-100
EB Spline
72.67
71.99
Spline Improv.
+1.24% +1.7%
+0.38%
-0.18%
0.14%
3,2x
p=10%
p=30%
p=50%
p=10%
p=.0%
p=50%
Rigl.
71.4
70.98
70.75
15.66
15.6
15.6
GmsP
69.5
69.25
68.43
15.33
15.3
15.3
VGG-16
SynFlow Spline
72.08
71.48
71.2
15.3
15.3
15.3
C0FAR-100
72.18
71.54
70.07
28
22.9
19.4
ER Spline
72.07
71.46
Spline Improv.
+0.1% +2.68%
+4..06
+2.29%
+0.91% +1.86%
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 are shown in the Tab. 5. We can see that our spline based pruning method is not sensitive to the adopted dimension reduction methods as long as can used to 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.
14

---

Under review as a conference paper at ICLR 2022
Table 5: Global spline pruning with PCA and FA dimension reduction methods.
Accuracy (%)
Setting
Methods
p=30%
p=50%
p=70 %
Spline (FA)
94.27
94.26
91.97
PreReNNe-101@CIFAR..
Spline (PCA)
94.13
93.92
92.06
Spline (FA)
93.10
93.25
92,49
VGG-16@CIFAR-I0
Spline (PCA)
93.62
93.46
92.85
Spline (FA)
74.37
72.94
68.02
Spline (PCA)
73.79
72.04
68.24
p=10%
p=30% %
p=50% %
Spline (FA)
72.20
71.99
70.62
VGG-16@CIFAR-100
Spline (PCA)
72.18
71.54
70.07
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 de- tected EB tickets PreResNct-101 and VGG-16 in the Tab. The results show that our spline EB tickets consistently emerge at early training stages and perform on par with their unpruned counter- parts, and thus are empirically observed be universal different optimization methods.
Table EB tickets detection using different optimization methods.
Retrain Accuracy (%)
Setting
Methods
EB Emerge Epoch
Unpraned
p=30% %
p=50% %
EB (SGD)
61
93.66
93.67
93.18
(Adam)
89.63
89.63
89.26
PreResNet- 101
EB (Adagrad)
33
90.64
90.76
90.79
EB (RMSprop)
80
87.41
86.83
86.37
EB (SGD)
24
92.71
93.28
93.05
(Adam)
90.11
91.25
90.73
VGG-16@CIFAR.
(Adagrad)
90.17
91.04
89.55
EB (RMSprop)
88
87.35
87.86
88.1
E How UNIVERSAL IS THE EB FOR ADVERSARIAN 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 initializa- tion and perform par with their corresponding unpruned dense networks after being retrained.
Table EB tickets detection using adversarial initialization.
Retrain Accuracy (%)
Setting
Methods
Emerge Epoch
Unpruned
p=30%
p=50%
EB (Random Init.)
61
93.66
93.67
93.18
PreResNec-101 101 @CIFAR-10
EB (Adv. Init)
81
93.33
93.38
93.36
EB (Random Init.)
24
92.71
93.28
93.05
VGG-16@CIFAR-I
EB (Adv. Init)
40
92.20
92.63
91.66
F BACKGROUND OF MASO AND ITS TIES WITH OUR METHOD
The entire CPA/max-affine spline formulation of deep networks (DNs) has been extensively studied before (Balestriero & Baraniuk, 2018). However the prior published works merely focus on studying the various spline properties that one can obtain on DN from the MASO formulation. Those works did not study the contributions that we propose in this paper, i..., (1) bridging the connection between spline theory and network pruning techniques, (2) discovering that a DN's s spline mappings exhibit early-bird (EB) phenomenon whereby the spline's partition converges early training stages, and
15

---

Under review as a conference paper at ICLR 2022
(3) leveraging the aforementioned EB finding to develop 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. fact, refer the readers 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 succinetly) 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 input space according to a power diagram subdivision that is formed by recursive subdivision process through the layers. Each subdivision is analytically known and involves the layer weights of each unit and the biases. When pruning unit layer I, the subdivisions of layers I,,,, are unchanged, the power diagram of layer is altered only by removal of a single hyperplane from its boundary, and all the subdivisions of layers + 1, ..,, are altered.
Additionally, classification tasks, 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 at least two regions. The LTH, in terms of splines, states that it is possible 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 Fig. and Fig. where we depicted that the same (or similar) decision boundary (in red) could be obtained from much reduced input space partition.
While we have limited ourselves to mostly empirical evaluations and validations an important first step, we agree that an in-depth theoretical study would be immensely beneficial for the community. This is something are hoping to achieve in next study this theoretical question is incredibly challenging, for which this work can provide critical insights and inspirations.
H ADDITIONAL VISUALIZATION
Node
Node
Node
Node
Node 5
Layer
Node 1
Node 2
Node 3
Node 4
Node
Layer 2
Decision Boundary
Layer (Classifier)
Figure 8: Additional visualization of the partitioning and subdivision layer after layer, where each node introduces a spline the input space which is depicted under the current partitioning with highlighted path linked via dotted line.
16

---

Under review as a conference paper at ICLR 2022
Table 8: Accuracies of layerwise (LW) pretraining, structured pruning with random and lottery ticket initialization.
Setting
Pruning Ratio
Random Init.
Lottery Init.
LW Pretrain
30%
03.33+0.01
93.57:0.01
93.08+0.00
50%
93.07
9.03
93.08+0.01
VGG-16 CIFAR-10
70%
92.68=0.02
93,44=0001
9..01
90%
90.48=0.06
90,41=0.23
9..88=0.02
10%
71.49=0.03
7..70=0.09
7..14
30%
71.34=0.10
7..24
0.01
VGG-16 on CIFAR-100
50%
6..74
69.73+1.15
70.19=0.01
70%
60.4414.98
66.61
67.40
I 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 as is done in Kmeans with say kmeans++ remains to be developed for DNs. Hence, overparametrization allows successful training, and posteriori, one can remove the redundant parameters and obtain final model with much better performances versus the non-overparametrized and non-pruned coun- terpart. This is the key motivation of Early Bird tickets. Furthermore, the parallel between DNs and K-means is most relevant as it has been shown in (Balestriero et al., 2019) that the DN deci- sion 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 overparamettizattio. Beyond this geometric aspect. overparametrizztion has been proven facilitate optimization (Arpit & Bengio. 2019) and to position the initial parameters close to good local minima (Allen-Zhu et al., 2019; Zou & Gu, 2019; Kawaguchi et al., 2019) reducing the number of updates needed during training.
Remark 1. Winning tickets are the result of employing overly parametrized DNs which are simpler to optimize and produce better performances, as 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 ab- sence of good initialization coupled with non-optimal optimization problems impacts performances unless overparametrization 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 to overparametrize DNs which in turn emerges naturally from architecture search and validttali as overparametrrzingg greatly facilitates train- ing and improves final results. We now show that if better initialization of DNs existed, one would have the ability to train a 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 of employ minimal DN with random weights initialized from random Kaiming initial- ization (He et al., 2015). Second, we consider the same minimal DN architecture but with weights initialized based on unsupervised layerwise pretraining which we consider as a data-aware initial- ization (no label information is used) (Belilovsky et al., 2019). In both cases, training is done on the classification task the same manner. Third, we consider an 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, see that the ability of pruning methods and. in particular, LT to produce better performig minimal DNs than directly training the same minimal DN lies in the lack of good initialization for Deep Networks.
17

---

Under review as a conference paper at ICLR 2022
VGG-16 on CIFAR-10
VGG-16 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.677
3.140
4.594
6.047
FLOPs
1e16
FLOPs
1e16
Figure 9: Accuracy vs. efficiency trade-off' 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, As shown in Fig. 9, we further compare the required FLOPs when networks are initialized using lottery initialization and layerwise pretrain- ing, respectively. We observer that (1) when the pruning ratio is low (i.e., < 50%), networks with lottery initialization require a smaller number of computational FLOPSs to provide good initial- ization for the pruned network, while leading to comparable even higher retraining accuracy; and (2) when the pruning ratio is higher, layerwise pretraining requires a much smaller number of computational FLOPs compared training highly overparametrized dense networks. Such phe- nomenon opens door for investigating the following two questions, which we leave as our further works.
Is there a clear boundary/condition to show whether we should start from overparametrization or consider pretraining as good initialization for samll DNs instead?
How much overparametrization do we need to maintain better trade-off's between accuracy and efficiency, as 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, it 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 in searching for improved initialization strategies, we now focus on studying LTT training and DN pruning as they provide a universal solution.
J ANALYSIS ABOUT WHY THERE ARE REDUNDANT PARTITION BOUNDARIES
Network pruning literature follows the chaining of (i) overparametrization, (ii) training, and (ii)) praning to ob- tain a small but critical subnetwork, i.e., "winning ticket" that achieve high accuracies. This offers a powerful alter- native training small network from scratch as good initialization for such sparse network is not known (Fran-
98
96
Test Accuracy (%))
94
kmaans
kle & Carbin, 2019a; Blalock et al., 2020) making the optimization challenging. This strategy finds benefits not only with DN but also with traditional methods such K-means, in which case pruning removes centroids (Ka- nungo al., 2002; Hamerly Elkan, 2002: Celebi et al., 2013). We propose to briefly employ K K-means to demon- strate the superiority of such pruning strategies. As shown in Fig. 10, we consider K-means++ (Arthur & Vassilvit- skii, 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 Gaussian Mixture Model (GMM) (Reynolds, 2009) with spherical and identical covariances. Against that baseline, we perform the three-step pruning strategy
120
Number Initial Clusters
K-means experiments toy mixture of 64 Gaussian.
Figure 10:
multiple runs and with varying numbers of initial clus- ters 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).
18

---

Under review as a conference paper at ICLR 2022
1,0
0.8
0.06
0.02
0.0
-1.0
-0.5
0.3
0.5
1.0
100 200
300
X
Layer width
Depiction of simple (toy) univariate regression task with target function being a sawtooth with two peaks. Right: The & training error (y-axis) as function of the width of the DN layer (2 layers in total). In theory, only 4 units are requires perfectly solve the task at hand with a ReLU layer, however we see that optimization in narrow DNs is difficult and gradient based learning fails to find the correct layer parameters. As the width is increased the difficulty of the optimization problem reduces and SGD manages to find a good set of parameters solving the regression task.
Figure 11: Left:
We observe that the winning initialization perform near-optimal results (i.e., closer to kmeans++) when starting from overparameterization (i.e., initial clusters 2 100), otherwise suffer from large ac- curacy drops. We highlight that employing overparameterization facilitate finding winning tickets. From the above experiments it is clear that in the absence of "optimal" initialization of small DNs, pruning is the current preferred solution to obtain performing minimal architectures.
K ADDITIONAL RESULTS ON INITIALIZATION AND PRUNING
Next we extend the overparametrization-Pee pranrtiiiiiaiiio--nniignn vs. initialization insights to univariate DNs on carefully designed dataset. Considering a simple unidimensional sawtooth as displayed in Fig. 11 with P peaks (here P 2). In the special case of single hidden layer with ReLU activation function, one must have at least 2P units to perfectly fit this function with the weight configuration
being [i]1, = L,[i = k with A 1, ..... D2 and [2]1,1 1, (-) Note that these weights are not unique (other ones can identically fit the function) and are given as example. At initialization, if the DN has only 2P units, the probability that random weight initialization arranges the initial splines in a 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 ad- vantageously initialized throughout the domain and aligned with the natural input space partitioning of the target function (different regions for different increasing or decreasing sides of the sawtooth).
(k-1)% (A-11-
k= 2. D1.
This is what empirically illustrated in Fig. 11 (right) where one can see that even repeating multiple initializations of DN without overparametrization does allow to solve the task, while over- parametrizing, training, and then pruning that together preserve only the correct number of units allow for better approximation.
19

---

Under review as a conference paper at ICLR 2022
L RELATION BETWEEN ACTIVATION PATTERNS AND SPLINE PARTITION OF INPUT SPACE
Subdivision Lines. Every layer deep networks (DNs) with piecewise nonlinearities (e.g. ReLU activation) can be viewed as subdivision lines for partitioning the given input space (Balestriero et al., 2019). For ex- ample, 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 line to distinguish non-zero activations in the input grid, thus we have k subdivision lines in this layer,
<0
0
subdivision
>0
the number of hidden nodes. From such geometry perspective, there are two good characteristics to leverage: (1) Subdivision lines the first layer are linear afline func- tions taking layer parameters as slopes and biases, following subdivision lines are piecewise linear, whose turning points are exactly located the subdivision lines in previous layers; (2) The derived subdivision lines at final classification layer are exactly the network decision boundary. Such connection provides us 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.
N
Figure 12: Visualize one subdivision line on grid.
M EARLY-BIRD VISUALIZATION ON TEST AND RANDOM SAMPLES
To investigate what happens to the partitioned regions that do not contain any training data, redraw Fig. 5 (early-bird visualization) on test samples, and show the visualization of early-bird phenomenon at Fig. 13.
25
23
14
25
35
50
55
75
100
VGG-16 CIFAR100
PreResNet-101 CIFAR100
CIFAR100
PreResNet-101 CIFAR100
(a) Visualization Training Samples
(b) Visualization Testing Samples
25
44
0
30
100
135
175
VGG-16 on CIFAR100
PreResNet-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.
N SPLINE TRAJECTORY AND EB TICKETS WITH LEAKY RELU ACTIVATION
We redraw Fig. 4 (spline trajectory) and Fig. 5 (early- 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 Fig. 15. From these figures, consistently observe that the splines
20

---

Under review as a conference paper at ICLR 2022
will adapt during the early phase while converging later training stages, demonstrating that the early-bird phenomenon still holds under the Leaky ReLU 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 -0.44% +1.38% accuracy improvement and up 4x training flops savings.
Replace ReLU with Leaky ReLU
0.7
0.6
0.5
Loss
0.4
0.5
0.2
0.1
2000
6000
6000
8000
10000
Iterations
Spline Trajectory for FCNet
Figure 14: Visualization of spline trajectories using FCNet with Leaky ReLU activation functions.
Replace ReLU with Leaky ReLU
100
100
0.4
125
125
(a) PreResNet-101 on CIFAR10 (b) PreResNet-101 CIFAR100
Figure 15: Visualization of the early-bird (EB) phenomenon when training PreResNet-101 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
93.54%
93.18%
90.89%
13.9P
12.7P
11.0P
ThiNet
92.18%
91.57%
90.25%
13.2P
10.6P
8.65P
Spline
93.56%
92.74%
91.11%
13.6P
12.1P
10.1P
PreResNet-101 on CIFAR-10
EB Spline
92.76%
92.13%
90.66%
6.00P
4.26P
2.74P
Spline Improv.
-0.44%
+1.38%
1.1X 4.0%
21

---

Under review as a conference paper at ICLR 2022
O 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), -100), leading -0.35% +66.87% accuracy improvements. Note that the network slimming (NS) method suffers from bottleneck layers due to the "over-pruning" channels on specific layers.
Table 10: Evaluating spline pruning method over baselines under 90% pruning ratios.
Datasets
Model
Methods
Accuracy (p=90%)
NS
77.63%
ThiNet
87.80%
Spline
87.96%
PreResNct-
EB Spline
88. 15%
Spline Improv.
+0.35
+10.52%
NS
89.13%
CIFAR-10
ThiNet
86.90%
Spline
89.11 %
VGG-16
EB Spline
89.24%
Spline Improv. +0.11 % +2.34% %
NS
28. 90%
ThiNet
60.66%
Spline
58.97%
PreResNet-101
EB Spline
60.31
Spline Improv.
-0.35 %
+31.4%%
NS
1%
CIFAR-I08 100
ThiNet
56.31%
Spline
59.37%
VGG-16
EB Spline
64.87%
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 the Table 11, our spline pruning again outperforms those methods in terms of both accuracy and efficiency, leading -0.47% +1.11% accuracy improvement and up to 7.1x training flops savings. We will add this set 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=70%
NS-IP
93.74%
72%
92.53%
23.6P
21.6P
18.7P
Spline
94.13%%
93.92%
92.06%
13.6P
12.1P
10.1P
PreResNet-101 CIFAR- 10
EB Spline
93.67%
93.18%
92.32%
6.00P
4.26P
2.74P
Spline Improv.
+0.39%
+1.20%
-0.47%
1.7x
6.8x
NS-
72.68%
71.82%
69.86%
23.3P
21.3P
17.5P
Spline
73.79%
72.04%
68.24%
12.6P
10.9P
9.36P
PreResNet- 101 CIFAR-100
EB Spline
72.67%
71.99%
69.74%
5.44P
3.84P
2.46P
Spline Improv.
+1.1%%
+0.22%
-0.12%
1.8x 7.1x
Q 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 early epochs.
22

---

Under review as a conference paper at ICLR 2022
Table 12: Record of the quantitative distance between input space partitions of different layers, i.c.,
early, middle, or later layers, along the training trajectory.
Quantitative Distances
Datasets
Models
Lavers
10th epoch
40th epoch
80th epoch
120th epoch
160th epoch
Early (Ist)
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 (1st)
0.621
0.562
0.296
0.023
0.002
PreResNer- 101
Medium (16th)
0.273
0.025
0.003
Late (32th)
0.781
0.728
0.376
0.038
0.005
R SPLINE PRUNING FOR VISION TRANSFORMER (VIT)?
For self-atiention layers in ViT, the spline theory is not directly applicable due the softmax func- tion which is not continuous piecewise affine. However, one possible direction would be to model such layers as "smooth splines". The discussion in (Balestriero & Baraniuk, 2019) that would allow such extension, this is recognized as an interesting future direction.
23


Reviews:
[{"review_id": "tdNIcCkPPrz", "reviewer": "Reviewer_pmay", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: \n1.the paper provides a new perspective on deep neural network pruning, \n2.the analysis through spline space partition is interesting. \n3.The paper has good written and visualization.\nWeakness: \n1.The author claim that ‘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.’, however, in theoretical part, the author didn’t provide how the proposed algorithm in detail to remove the subdivision splines. Will the algorithm need extra computation cost for such space partition building? \n2. When the author introduces the proposed algorithm, the author didn’t analysis if such method has the same convergence guarantee as Lottery Ticket Hypothesis. If so, what is the bound of the error probability?\n3.In the experiment, the author didn’t consider Vision Transformer, which is an important SOTA model in image classification. And it is unsure if such technique is still working for larger image dataset such as ImageNet. Will the pruning strategy will be different in self attention layers?\n", "summary_of_the_paper": "This paper mainly proposes a new angle to understand the deep neural network pruning based on Spline theory and propose a new pruning algorithm approach. First, the author introduces the back ground of the Spline theory and current pruning methods. Second, the author analysis the different pruning methods from space partition perspective and introduce the proposed algorithm. Third, the author run experiments to evaluate the proposed algorithm in different aspects. ", "summary_of_the_review": "The idea and the observation is interesting, and most of the experiment results are promising. However, it is unclear how the author finds the subdivision spline to remove in experiment implementation. And in the theoretical part, I suggest the author to provide the convergence proof of proposed algorithm’s under Lottery Ticket hypothesis. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UF0JyvqqYHp", "reviewer": "Reviewer_2J1h", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Please read the summary first. Here are detailed comments:\n\n(1) Section 3.1 shows a trend in case studies that the pruning tends to preserve subdivision splines useful to the decision boundary and remove the redundant ones. As long as the decision boundary is preserved, the performance will not degrade. This is interesting. However, the two toy datasets here are too synthetic and no quantitative analysis is presented, especially for more complicated datasets or neural nets. Moreover, given the previous success of pruning on DNNs with piecewise linear activation functions like ReLU, the phenomenon observed here is somewhat obvious. I expected to find some in-depth analysis of why the trained decision boundary only depends on a small subset of splines and why the applied pruning method here can preserve them, which could be an important novelty of this paper, but only the phenomenon is described. The splines also lack a formal math definition in terms of the network parameters/filters/units, which could be very helpful to understand their relationship in pruning.  \n\n(2) Section 3.2 claims that a novel metric based on those subdivision lines is developed to study the early-bird ticket phenomenon but the metric is simply the change of ReLU activation patterns between two consecutive epochs. It is obvious that if the activation patterns do not change too much, the decision boundary of the DNNs would not change too much, but this does not necessarily depend on the previous analysis of the spline partition of input space. The change of partition is only reflected via a toy example in Fig.4 without quantitative analysis and in-depth discussion, e.g., do all the splines or just the important ones (forming the boundary) not change since very early epochs, what happens to the partitioned regions that do not contain any training data, etc.\n\n(3) I also have a similar concern about Section 3.3. It proposes an intuitive pruning strategy, i.e., removing the redundant units that are too similar to each other in terms of cosine similarity of parameters and difference between bias terms. However, this heuristic does not necessarily depend on any previous observations of spline subdivisions and input-space partitions. To achieve a pruning ratio > 50%, this strategy needs to be applied sequentially and thus cannot leverage parallel computation as most existing pruning methods. In each round, its complexity is quadratic in the number of units since it needs to compute all pairwise similarities, which is also costly. Hence, I am worried about its efficiency in practice. \n\n(4) The experiments try to show the proposed strategy's advantage over existing pruning methods on efficiency (when achieving comparable accuracies). However, they did not try high enough pruning ratios. As reported, almost all the evaluated pruning ratios achieve similar accuracies, indicating that the pruned DNNs are still very redundant and the pruning does not enter a trade-off regime between accuracy and pruning ratio. In the current regime, \"better pruning strategies\" can not be well distinguished from \"worse pruning strategies\" and thus cannot provide strong evidence to show the advantage of the proposed method. \n\nAdditional questions:\n\n(1) Did you compare to any iterative pruning methods, which keep removing unimportant units/weights over epochs since the very beginning? They might be as efficient as or even more efficient than the early-bird metric used in this paper.\n\n(2) Did you consider the difference of layers on their contributions to the final decision boundary and their difference in the convergence of activation patterns? Will these differences be helpful to improve the pruning performance?\n\n(3) Instead of sequentially finding the redundant pairs of units, as proposed in Section 3.3, why not apply clustering based on the metric in Eq. (2)? It is not clear how to get the \"grouped partition trajectories\" without using any clustering-type method. \n\n(4) Though starting with max-affine spline DNs in Eq. (1), the paper only considers ReLU activations. Can you add empirical analysis and experiments for other activations belonging to this family?\n\n(5) The current related works lack discussion about the research area for linear regions of neural nets, which covers a great number of papers and is strongly related to the spline subdivisions in this paper and thus cannot be ignored.", "summary_of_the_paper": "This paper conducts a series of empirical studies, which aim at relating node/filter/channel pruning with the partition of input space by neural nets using spline operators as activation functions. In particular, the final decision boundary is only determined by a few splines defined by a few filters of the network. This is verified in the paper through case studies of both fully-connected networks and convolutional networks, which implies that pruning does not severely degrade the accuracy as long as the important splines are not removed by pruning. Another observation is the early-bird tickets: the paper argues that the important splines do not change too much after a few early epochs since the binary activation patterns of data converge rapidly, so prunning can be applied after only a few epochs. The paper then proposes a pruning strategy that sequentially finds the most similar filter pairs and removes them. In experiments, they show that the proposed prunning method is more efficient than some recent pruning methods to achieve similar accuracy with pruning ratio <=70% for CIFAR10/100 and <=50% for ImageNet. ", "summary_of_the_review": "Although both the input space partition of neural nets with piecewise linear activations (sometimes called linear regions, convex polytopes, etc.) and node/structured pruning have been widely studied and well known in recent years, this paper provides an interesting and novel perspective to relate them, i.e., explaining why a high pruning ratio can still work, early-stopping for pruning, and pruning by removing redundant units. The case studies clearly explain the empirical observations and well motivate some conclusions. However, the main results are a little bit disappointing to me due to the lack of in-depth discussion of the phenomenons. Necessary math formulation of some important concepts (e.g., splines, grouped partition trajectories, etc) is missing. Both the early-bird metric and the pruning strategy lack a strong or insightful connection to the spline partition and decision boundary discussed in the first part of the paper. The experiments have not explored higher pruning ratio regimes, which are necessary since the reported accuracy does not change too much over the evaluated pruning ratios. \n\n-------------Update---------------\n\nThe authors address most of my major concerns in their new reported experiments and updated draft. Therefore, I raise my score to 6.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QG4vmcW5JrX", "reviewer": "Reviewer_yjUc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- The idea of pruning the deep network by removing the redundant subdivision splines is a very novel idea. What's more, the authors interpret this idea with many vivid figures which is very readable.\n\n- The authors first bridge the connection between deep network spline theory and deep network pruning. The authors provide new insights into how pruning deep network nodes affect the decision boundary. Furthermore, they leverage this new insight to develop a principled and efficient pruning strategy.\n\n- Training deep network is a remaining huge obstacle. The authors propose a new robust and efficient algorithm for deep network training by effective network pruning techniques, which outperforms state-of-the-art competitors.\n\n- There remains a lack of explicit understanding of network pruning impact on a deep network’s decision boundary. The authors illustrate the effectiveness of their method from many aspects.\n\n- I don't understand why the authors choose the pairwise redundancy measure in (2). They need to give readers some more motivation. Is there any other measure that may be better? Some simple analysis may help us recognize it intuitively. \n\n- In section 4.3, Global spline pruning, the big problem is the mismatch of the filter dimension in different layers impedes the cosine similarity calculation. The authors solve this problem by adopting PCA for reducing the feature dimensions to the same. Is there any reason to measure the similarity between different layers by PCA or FA?\nThey need to clarify it.\n\n- In practice, units with small enough but nonzero $N_\\rho^l(k,k')$ are also highly redundant and can be removed. How to decide the threshold? The authors need to give more details.\n", "summary_of_the_paper": "This paper presents a novel methodology for deep network pruning from the perspective of the max-affine spline.\nThe key idea of the paper is to remove the redundant subdivision splines and find winning tickets.\nThis is an interesting and very nicely written paper that bridges the max-affine spline formulation and empirical pruning techniques.\nThe authors provide a sufficient and straightforward introduction of the behind motivation.\nBeyond these, the authors discuss robustness considerations and perform thorough experiments on various benchmarked models and datasets, showing the favorable performance of their method.", "summary_of_the_review": "The paper is well-written and the ideas are well-presented. However, some points listed above need to be clarified.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KH7mhJIiBQH", "reviewer": "Reviewer_haRu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1. The proposed idea to explain network pruning is quite interesting and could have a significant impact.\n2. The experiment results do show the proposed method could achieve similar or better accuracy with good energy efficiency. \n\nCons:\n1. While the paper claims it bridges the understanding between pruning and decision boundary, however, I find it not convincing. It is only through two simple examples to illustrate the relation. There lacks a systematic way how to derive which spline function could be affect the final decision boundary. \n2. Some of their main claims are not well-supported. Proposition 1 is supporting evidence to conduct their pruning however it does not clearly show why Proposition 1 is working and only gives a reference to the paper proposing the deep learning spline function. Also, the early bird detection is also through two simple trajectories which are not convincing to me either. \n3. To use the global spline pruning, it has to first use PCA to shrink the space. However, the dimension reduction method is crucial to calculating the cosine similarity score. It could be seen in the appendix the performance is fluctuating with a not very small margin, which makes the method not reliable.", "summary_of_the_paper": "The paper proposes to use the max-affine spline function to understand network pruning in the deep learning architecture. Specifically, it uses two examples (one in fully-connected NN and one in CNN) to show the splines visualization with different pruning rates. Inspired by the theory, it then proposes a policy that is based on calculating the cosine similarity between slope and biases to determine the importance. The experiment results show the proposed metric could achieve a similar or better accuracy with good energy efficiency in multiple datasets with both structured pruning and unstructured pruning.", "summary_of_the_review": "Although the paper has proposed a very interesting perspective on network pruning, it lacks supporting evidence on some of their main claims. Therefore, I vote for a borderline paper with a tendency towards reject. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: ### Summary

The paper investigates the relation between pruning and splines. The results show that the prunable nodes of networks correspond to splines that do not affect the ultimate decision boundary of the network. The results also show that splines stabilize early in training, in correspondence with the claims of early bird tickets. Finally, the results show the connection between similarity-based pruning and splines, with an evaluation of the quality of similarity-based pruning.

### Discussion

The paper demonstrates a very interesting connection with splines and promising results with the multiple analyses. However, there could be more precision in the stated connections between splines and pruning. Also, reviewers requested more elaboration of the base technical definitions (e.g., splines).

### Recommendation

I recommend Reject. While the first part of this paper is quite strong in that the spline view of networks provides an interesting analysis framework that draws out interesting connections to pruning. The latter part that develops the concrete pruning algorithm needs reenvisioning. Specifically, to the best of my reading, using the similarity of filters for pruning is not new [1,2,3]. That means the proposed spline pruning policy approach cannot be claimed as new. Though it is reasonable to claim the connection to splines as new.

Second, while the evaluation is extensive in its comparison to other techniques, it is quite murky. The results claim victory by including both spline and EB spline, neither of which strictly dominates the other. My suggestion is to remove the EB spline and, in the worst case,
claim that similarity-based pruning is (1) competitive with other approaches and (2) rests on a foundational theory that is a new alternative to typical importance-based techniques. That latter observation is an important one for the community that can lead everyone into new productive directions. 

Additionally, in line with some requests from the reviews for more analysis, simplifying the evaluation (with fewer and less ambitious claims) and, even perhaps, eliminating the EB analysis altogether, would make room available for additional analysis and elaboration.

[1] BCAP: An Artificial Neural Network Pruning Technique to Reduce Overfitting
Kiante Brantley. UMD Masters Thesis, 2016

[2] A dynamic CNN pruning method based on matrix similarity
Mingwen Shao, Junhui Dai, Jiandong Kuang, Deyu Meng. Signal, Image and Video Processing volume 15, pages 381–389 (2021). Published August, 2020

[3] Similarity-Based Filter Pruning for Efficient Super-Resolution Models.
Chu Chu; Li Chen; Zhiyong Gao. IEEE International Symposium on Broadband Multimedia Systems and Broadcasting, 2020
Decision: Reject