MAX-AFFINE SPLINE INSIGHTS INTO DEEP NETWORK PRUNING
Year: 2021

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 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 on four networks and three datasets validate that our new spline-based DN pruning approach reduces training FLOPs by up to 3.5× while achieving similar or even better accuracy than current state-of-the-art methods. All the codes will be released publicly upon acceptance.

heading: 1 INTRODUCTION
text: Deep Networks (DNs) are powerful and versatile function approximators that have reached outstanding performances across various tasks, such as board-game playing (Silver et al., 2017), genomics (Zou et al., 2019), and computer vision (Esteva et al., 2019). For decades, the main driving factor of DN performances has been progresses in their architectures, e.g. with the finding of novel nonlinear operators (Glorot et al., 2011; Maas et al., 2013), or by discovering novel arrangements of the succession of linear and nonlinear operators (LeCun et al., 1995; He et al., 2016; Zhang et al., 2018). With a tremendously increasing need for DNs’ practical deployments, one line of research aims to produce a simpler, energy efficient DN by pruning a 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 a 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, or 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); Evci et al. (2019); Su et al. (2020); Blalock et al. (2020). In this paper, we shed new light on the inner workings of pruning techniques from a spline perspective, by leveraging recent advances in DN understandings and spline formulation (Montufar et al., 2014; Balestriero & Baraniuk, 2018). Specifically, current DNs are affine splines, that is the input-output mapping is affine in polytopal regions of the input space partition. From this viewpoint
pruning acts upon a DN by removing/altering the partition boundaries as demonstrated in Fig. 1, 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, 2019a)) by studying their impact on the DN input space partition, demonstrating how and when can pruning be used without sacrificing the final performances. Finally, we demonstrate how to derive a new pruning scheme based on our gained understandings that reaches competitive performances. In order to ease our development, we slightly abuse notations and refer to a DN as being overparametrized whenever it can be pruned while maintaining its performances and refer to a DN as being minimal whenever it can not be pruned without impacting its performances. We summarize our contributions as follows:
[C1] 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 to quantify the evolution of the partition boundaries during training, which allows us to efficiently detect early-bird (EB) tickets when an overparametrize DN has been trained enough and can be pruned; and as opposed to previous EB methods, ours detects EB tickets regardless of the employed pruning techniques or hyperparameters. [C3] We leverage the new insights and the finding of [C2] to derive an efficient pruning strategy from first principles, which only focuses on DN nodes whose corresponding spline partition boundaries contribute to the final decision boundary. A series of experiments on various benchmarked models and datasets validate that our pruning method achieves 3.5× training FLOPs reduction and maintains similar or even better accuracies over state-of-the-art pruning techniques, while being principled and interpretable.

heading: 2 BACKGROUND AND RELATED WORKS
text: A DN transforms an input x through a composition of L layers f `, ` = 1, . . . , L to form the final prediction: f(x) = (fL ◦ ⋅ ⋅ ⋅ ◦ f1)(x). Each layer is a (nonlinear) mapping taking as input a D `−1-dimensional feature map and producing a D`-dimensional one, where D` is the `th feature map’s dimension1; each layer’s parameters are collected in θ`. For a fully-connected and activation function layer, θ` comprises the D
` × D`−1 dense matrix W ` and the D`-dimensional bias vector b `. For convolution operators (LeCun et al., 1995), the dense matrix W ` is replaced with a circulant block circulant matrix C` for channel-wise convolutions and summations.
1we consider matrices and tensors as flattened vectors for clarity
Max-affine spline DNs. A key result of (Montufar et al., 2014; Balestriero & Baraniuk, 2018) is the reformulation of current DN layers with (leaky-)ReLu/Linear/Abs. 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
f `(z) = max r=1,...,R (A`rz + v`r) , (1)
with the maximum taken coordinate-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 input space partition Ω. A few work have focused on studying the relation between the number of regions and the DN architecture (Hanin & Rolnick, 2019b), the analytical form of the partition (Balestriero et al., 2019), the upper bound in the number of regions (Montufar et al., 2014; Montúfar et al., 2021).The fundamental property that we will leverage throughout this paper is that the internal weights of the layers are paired with their input space partition. As pruning impacts those weights and/or nodes directly, this will offer us new ways to study pruning in DNs’ input space. More background on DNs, their spline formulation, and its difference with our work can be found in Appendix F.
Network pruning. Pruning is a widely used DN compression technique reducing the number of activated nodes (Liu et al., 2019c; LeCun et al., 1990) in 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 to 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, granularity, and scheduling (Liu et al., 2019c; Blalock et al., 2020). Those techniques roughly fall into two categories: 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 a model and the final accuracy. For various energy efficient applications, novel pruning techniques have been able to push this trade-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-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.
Despite the above discoveries, the DN pruning literature lacks an explicit understanding and visualization via theoretical analysis that would bring insights into (i) current pruning techniques and (ii) observed phenomenons such as EB tickets, while leading to principled pruning techniques. We propose to approach this task by leveraging the spline viewpoint of DNs to provide novel interpretations of existing pruning techniques, study the conditions to their success and when should they be avoided, and finally, how to derive novel pruning strategies from first principles.

heading: 3 DEEP NETWORKS PARTITION, DECISION BOUNDARY AND PRUNING WORK HAND-IN-HAND
text: In this section, we first introduce our novel spline interpretation of pruning at various granularity levels. Then we 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.

heading: 3.1 INTERPRETING PRUNING FROM A SPLINE PERSPECTIVE
text: We first propose to leverage the DN input space partition to study the difference between node and weight pruning, representing structured and unstructured pruning, respectively. In the former, nodes of different layers are removed, while in the latter, entries of the W ` matrices (or C for convolutions) are removed. We demonstrate in Fig. 1 (b) and (c) that node pruning removes entire subdivision splines while weight pruning (or quantization) can be thought as finer granular limitations on the slopes of subdivision splines, and will only remove the subdivision lines when all entries of a specific row in W ` are pruned, in which case node and weight pruning become identical. From this
perspective, we can already identify the reason why pruned networks are less expressive than the overparametrized variants (Sharir & Shashua, 2018) as pruned DNs’ input space partition and final decision boundary shape are limited compared to their unpruned counterparts. 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 the regions of the DN input space partition.
Despite the constraints that pruning imposes on the DN input space partition, classification performances do not necessarily reduce when pruning is employed. In fact, the final decision boundary, while being tied with the DN input space partition, does not always depend on all the existing subdivision lines. That is, pruning will not degrade performances as long as the needed decision boundary geometry does not rely on the partition regions that are being affected by pruning. We demonstrate and provide explicit visualization of the above in Fig. 2 and Fig. 3 with fully-connected networks (FCNets) and convolutional networks (ConvNets), respectively. The observation consistently shows that only parts of subdivision splines are useful for decision boundary; and the goal of pruning is to remove those (redundant) subdivision splines and find winning tickets. For example, we observe that for a two-layer FCNet (20 nodes per layer), applying pruning ratios ranging from 20% ∼ 95% (i.e., prune 4 ∼ 19 nodes) does not prevent solving the task as long as the remaining subdivision lines are positioned to allow the decision boundary geometry to remain intact. We also extend the above experiment to a high dimensional case with MNIST classification and a DN with two convolutional layers, 20 filters, and kernel sizes of 21 and 5, respectively in Fig. 3. By adopting the same channel pruning method as in (Liu et al., 2017), we see that most of the pruned nodes remove subdivision lines that were not crucial for the decision boundary and thus only have a small impact on the final classification performance. Hence, as long as pruning leaves at least
Iterations
Lo ss
Epochs
Lo ss
(b) Spline Trajectory for ConvNets(a) Spline Trajectory for FCNets
those few subdivision lines, the final performances will remain high. Apart from the empirical study, we also provide some analysis about the connection between pruning (e.g, lottery ticket hypothesis (LTH)) and spline theory in Appendix G.

heading: 3.2 SPLINE EARLY-BIRD TICKETS DETECTION
text: Early-Bird (EB) tickets (You et al., 2020) provides a method to draw winning ticket sub-networks from a large model very early during training (10% ∼ 20% of the total number of training epochs). The EB drawn is based on an a priori designed pruning strategy and hyperparameters and compares how different (in terms of which nodes/channels are removed) are the hypothetical pruned models through the training steps; this method outperforms SOTA methods (Frankle & Carbin, 2019b; Liu et al., 2017). The main limitation of EB lies in the need to define a priori a pruning technique (itself depending on various hyperparameters). Based on the spline formulation, we formulate a novel EB method that does not rely on an external technique and only considers the evolution of the DN input space partition during training. Early-bird in the spline trajectory. First, we demonstrate that there exists an EB phenomenon when viewing the DN input space partition, which should follow naturally as the DN weights and the DN input space partition are tied. We visualize DN partition’s evolution at different training stages in Fig. 4 (a) and (b), under the same settings as Sec. 3.1. From this, we clearly see that the partition quickly adapts to the task and data at hand, and then is only slightly refined through the remaining training epochs. This fast convergence comes as early as the 2000-th iteration (w.r.t. 10000 iterations for FCNets) and the 30-th epoch (w.r.t. 160 epochs for ConvNets). Additionally, we observe that the contribution of the first layers in the input space partition becomes stable more rapidly than for deeper layers. We can thus leverage this early convergence to detect EB tickets with a novel metric based on those subdivision lines to draw more unified EB tickets than (You et al., 2020). Moreover, EB tickets have been found to be universal under different optimization and initialization methods, of which the experiments are provided 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 a metric that conveys such information. First, recall that each region from the DN input space has an associated binary code based on which side of the subdivision trajectories the regions lie (Montufar et al., 2014; Balestriero & Baraniuk, 2018). Given a large collection of data points, we can assign each datum the code of the region it lies in (found simply based on the sign of the per-layer feature maps). As training occurs and the partition adapts, the code associated with an input will vary. However, once training stabilizes and regions do not change anymore, this code will remain the same. In fact, one can easily show that in the infinite data sample regime covering the entire input space, DNs with 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 × 160) in Fig. 5, where the (i, j)-th element represents the spline distance between networks from the i-th and j-th epochs. The distances are normalized between 0 and 1, where a lower value (w.r.t. warmer temperature) indicates a smaller spline distance (and thus DNs with similar partitions). We consistently observe that such distance 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.15, 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
tickets drawn in (You et al., 2020), our formulation provide a more interpretable scheme that is invariant to the pruning strategy as well as its hyperparameters (e.g., the pruning ratio). Hence, our formulation allows for a unified solution that does not require to be adapted based on the pruning technique that users experiment with.

heading: 3.3 SPLINE PRUNING POLICY
text: We now propose to derive from first principles novel pruning strategies of DNs based on the spline viewpoint insights. Recall from Sec. 2 that the layer input space partition is formed by a successive subdivision process involving each per-layer input space partition. As we also studied in the previous section, for classification performances, not all the input space partition regions and boundaries are relevant since not all affect the final decision boundary. Knowing a priori which regions of the input space partition are helping in solving the task is extremely challenging, since it requires knowledge of the desired decision boundary and of the input space partition, both being highly difficult to obtain for high dimensional spaces and large networks (Montufar et al., 2014; Balestriero et al., 2019; Hanin & Rolnick, 2019a). What is simpler to obtain, however, is how redundant are some of the layer weights/units in terms of the forming of the DN partition relative to other units/weights. From that, it will become easy to prune the redundant units/weights as their impact on the forming of the decision boundary is already carried by another unit/weight.
When considering the layer input space partition, we can identify “redundant” units based on how each unit impacts the partition with respect to other units. For example, if two units have biases and slope vectors proportional to each other, then one can effectively remove one of the two units without altering the layer input space partition. While this is a pathological case, we will demonstrate that the angles between perunit slope matrices and inter-bias distances measure such a redundancy. We first introduce our pairwise redundancy measure as the following equation:
N ` ρ(k, k′) = (1 − ∣⟨[W `]k,., [W `]k′,.⟩∣ ∥[W `]k,.∥2∥[W `]k′,.∥2 ) + ρ∣[b`]k − [b`]k′∣, ρ > 0, (2)
where Wk refers to the corresponding slope matrices of the k-th unit, ρ is an hyper-parameter measuring the sensitivity of the difference in angle versus the biases. In the case of a convolutional layer, Wk 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 mink,k′/=kN ` ρ(k, k′) where the obtained couple (k, k′) encodes the two units which are the most redundant. In turn, one of those two units can be pruned such that the impact of pruning onto the DN input space partition is minimized. Proposition 1. Given a layer and its input space partition, removing sequentially one of the two units, k and k′, for which N `ρ(k, k′) = 0, leaves the layer input space partition unchanged.
The above result exploits (Balestriero et al., 2019). In short, if N `ρ(k, k′) for any positive ρ, then the layer-partition boundaries (of layer `) 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 a continuous operator i.e., the layer-partition boundaries that overlap will produce DN partition boundaries that overlap.In practice, units with small enough but nonzero N ` ρ(k, k′) are also highly redundant and can be removed. We provide an example of this procedure in Fig. 6, where a small DN input space partition (layer 1 trajectories in black and layer 2 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 in the DN input space (comparing the green trajectory to the others with coloring based on the induce similarity from dark to light). Based on this measure, pruning can be done to remove the “grouped partition trajectoris” and obtain the pruned partition on the right. 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 models 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).

heading: 4 EXPERIMENT RESULTS
text: In this section, we 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 pruning, respectively. Finally, we present ablation studies in terms of the only hyper-parameter ρ.

heading: 4.1 EXPERIMENT SETTINGS
text: Models, datasets, baslines, and metrics: Models & Datasets: We consider four DNN models (PreResNet-101, VGG-16, and ResNet-18/50) on 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 et al., 2017), lottery tickets (LT) (Frankle & Carbin, 2019a), SNIP (Lee et al., 2019), ThiNet (Luo et al., 2017), SFP (He et al., 2018), LeGR (Chin et al., 2020), GAL-0.5 (Lin et al., 2019), GDP (Lin et al.), C-SGC-50 (Ding et al., 2019), and meta pruning (Liu et al., 2019b). Metrics: We evaluate in terms of the retraining accuracy, total training FLOPs, and real-device energy cost, the latter of which are measured by training the models on an edge GPU (NVIDIA JETSON TX2) (NVIDIA Inc.), which considers both the computational and data movement costs.
Training settings: For the CIFAR-10/100 datasets, the training takes a total of 160 epochs; and the initial learning rate is set to 0.1 and is divided by 10 at the 80-th and 120-th epochs, respectively. For the ImageNet dataset, the training takes a total of 90 epochs while the learning rate drops at the 30-th and 60-th epochs, respectively. In all the experiments, the batch size is set to 256, and an SGD solver is adopted with a momentum of 0.9 and a 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 are run in a server with ten NVIDIA 2080 Ti GPUs.

heading: 4.2 LAYERWISE SPLINE PRUNING
text: Recall that the spline pruning policy is done by solving arg mink,k′/=kN ` ρ(k, k′). By regard k as the index of channels for convolutional layers, we are able to conduct channel pruning in a layerwise
manner. Table 1 shows the comparison between the spline pruning (w/ and w/o EB detection) and SOTA network slimming (NS) method (Liu et al., 2017) on CIFAR-10/100 datasets. We can see that the spline pruning consistently outperforms NS, achieving -0.08% ∼ 3.86% accuracy improvements. This set of results verifies our hypothesis that removing redundant splines incurs little changes in decision boundary and thus provides a good a priori initialization for retraining.

heading: 4.3 GLOBAL SPLINE PRUNING
text: 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 pruning. 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 as it can be used to measure the correlation between two units, and these FA experiments are provided in Appendix C.
Spline pruning over SOTA on CIFAR. Table 2 compares the retraining accuracy, the total training FLOPs, and the total training energy of our spline pruning methods with four SOTA pruning baselines, including two unstructured pruning baselines (i.e., the original lottery ticket (LT) training (Frankle & Carbin, 2019b) and SNIP (Lee et al., 2019)) and two structured pruning baselines (i.e., NS (Liu et al., 2017) and ThiNet (Luo et al., 2017)). The results demonstrate that our spline pruning again consistently outperforms all the 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 × ∼ 3.5 × training FLOPs reductions and 0.7 × ∼ 1.5 × energy cost reductions while offering comparable or even better (-0.67% ∼ 0.69%) accuracies. In particular, spline pruning consistently achieves 1.16 × ∼ 3.16 × training FLOPs reductions than all the structured pruning baselines, while leading to comparable or better accuracies (-0.17% ∼ 1.28%). More comparisons with baselines of pruning at initialization can be found in Appendix B.
Spline pruning over SOTA on ImageNet. We further investigate whether the spline pruning have consistent performance in a harder dataset, using ResNet-18/50 on 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 a reduced training FLOPs of 43.8% ∼ 57.5% and a reduced training energy of 42.1% ∼ 54.3% for ResNet-50, while leading to a top-1 accuracy improvement of -0.12% ∼ 3.04% (a top-5 accuracy improvement of 0.18% ∼ 1.91%). Consistently, EB Spline achieves a reduced training FLOPs of 44.7% ∼ 61.7% and a reduced training energy of 39.5% ∼ 54.2% for ResNet-18, while leading to comparable top-1 accuracies (-0.24% ∼ 0.71%) and top-5 accuracies (-0.16% ∼ 0.21%).

heading: 4.4 ABLATION STUDIES OF THE SPLINE PRUNING METHOD
text: Recalling that the only hyperparameters ρ in our spline pruning method (see Equ. 2 of the main content), which balances the difference between the angles versus the biases. Here we conduct ablation studies to measure the retraining accuracies under different values of ρ for investigating its sensitivity, as shown in Fig. 7. Without loss of generality, we evaluate two commonly used models,
VGG-16 and PreResNet-101, on the representative CIFAR-100 dataset. Results show that spline pruning consistently performs well for a wide range of ρ values ranging from 0.01 to 0.4, which also generalizes to different pruning ratios (denoted by p). This set of experiments demonstrate the robustness of our spline pruning methods.

heading: 5 CONCLUSIONS
text: 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 of DNs to sharpen our understanding of different pruning policies, study the conditions in which pruning does not deteriorate performances, and develop a novel and more principled pruning strategy extending spline EB tickets; and extensive experiments demonstrated the superior performances (accuracy and energy efficiency) of the proposed method. The proposed spline viewpoint opens new avenues to theoretically study novel and existing pruning techniques as well as guide practitioners via the proposed visualization tools.

heading: A ALGORITHM FOR SEARCHING SPLINE EB TICKETS
text: Algorithm 1: The Algorithm for Searching Spline EB Tickets 1: Initialize the weights W and the FIFO queue Q with length l; 2: while t (epoch) < tmax do 3: Update W and r using SGD training; 4: Calculate the distance between the input space partitions of the current and the previous
networks, and then add it to Q. 5: t = t + 1 6: if Max(Q) < then 7: Return f(x;W ) (Spline EB ticket); 8: end if 9: end while

heading: B COMPARISON WITH PRUNING AT INITIALIZATION BASELINES
text: We further supply another three pruning-at-initialization methods, RigL (Evci et al., 2019), GraSP (Wang et al., 2020), and SynFlow (Tanaka et al., 2020), as our baselines and present the comparison results as shown in Tab. 4. We can see that our method consistently outperforms the pruning-atinitialization baselines in terms of accuracy-efficiency trade-offs, achieving up to 2.68% accuracy improvement at comparable or even (up to 3.2×) lower total training FLOPs.

heading: C GLOBAL SPLINE PRUNING WITH FA DIMENSION REDUCTION
text: 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 it can be used to measure the correlation between two units. We think that studying the theoretical guarantees on 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.

heading: D HOW UNIVERSAL IS THE EB FOR DIFFERENT OPTIMIZATION METHODS?
text: We detect EB tickets using different optimization methods, including SGD, Adam, Adagrad, and RMSprop (Ruder, 2016), and report both the emerging epochs and the retraining accuracies of detected EB tickets on PreResNet-101 and VGG-16 in the Tab. 6. The results show that our spline EB tickets consistently emerge at early training stages and perform on par with their unpruned counterparts, and thus are empirically observed to be universal to different optimization methods.

heading: E HOW UNIVERSAL IS THE EB FOR ADVERSARIAL INITIALIZATION?
text: we also detect EB tickets with the adversarial initialization (Liu et al., 2019a). The results shown in the Tab. 7 demonstrate that our EB tickets can consistently be found under the adversarial initialization and perform on par with their corresponding unpruned dense networks after being retrained.

heading: F BACKGROUND OF MASO AND ITS TIES WITH OUR METHOD
text: 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 a DN from the MASO formulation. Those works did not study the contributions that we propose in this paper, i.e., (1) bridging the connection between spline theory and network pruning techniques, (2) discovering that a DN’s spline mappings exhibit an early-bird (EB) phenomenon whereby the spline’s partition converges at early training stages, and
(3) leveraging the aforementioned EB finding to develop a principled pruning strategy that focuses on a tiny fraction of DN nodes whose corresponding spline partition regions actually contribute to the final decision boundary.
Needless to say that, we do not claim that the MASO formulation is one of our contribution. In fact, we refer the readers to those prior works in Sec. 2. Instead, we propose to build-upon the MASO formulation to in-turn study pruning in deep networks, and this (as far as we are aware) has not been done (even succinctly) previously.

heading: G ANALYSIS ABOUT THE CONNECTION BETWEEN LTH AND SPLINE THEORY
text: At the lowest level, LTH and spline theory are connected as follows. A DN partitions its input space according to a power diagram subdivision that is formed by a recursive subdivision process through the layers. Each subdivision is analytically known and involves the layer weights of each unit and the biases. When pruning a unit at layer l, the subdivisions of layers 1,⋯, l − 1 are unchanged, the power diagram of layer l is altered only by removal of a single hyperplane from its boundary, and all the subdivisions of layers l + 1,⋯, L are altered.
Additionally, in 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 a 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 to obtain an input space partition obtained by a power diagram subdivision each containing significantly less regions, that can still be positioned such that the decision boundary solves the task at hand. This is the exact phenomenon we tried to highlight in Fig. 2 and Fig. 3 where we depicted that the same (or similar) decision boundary (in red) could be obtained from a much reduced input space partition.
While we have limited ourselves to mostly empirical evaluations and validations as an important first step, we agree that an in-depth theoretical study would be immensely beneficial for the community. This is something we are hoping to achieve in a next study as this theoretical question is incredibly challenging, for which this work can provide critical insights and inspirations.

heading: H ADDITIONAL VISUALIZATION

heading: I DN INITIALIZATION: AN ALTERNATIVE TO PRUNING
text: 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 a posteriori, one can remove the redundant parameters and obtain a final model with much better performances versus the non-overparametrized and non-pruned counterpart. This is the key motivation of Early Bird tickets. Furthermore, the parallel between DNs and K-means is most relevant as it has been shown in (Balestriero et al., 2019) that the DN decision process relies on an input space partition based on centroids that is very similar to the one of K-means and which thus benefit in the same way to overparametrization. Beyond this geometric aspect, overparametrization has been proven to facilitate optimization (Arpit & Bengio, 2019) and to position the initial parameters close to good local minima (Allen-Zhu 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 absence 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 cross-validation as overparametrizing greatly facilitates training and improves final results. We now show that if a 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 a minimal DN with random weights initialized from random Kaiming initialization (He et al., 2015). Second, we consider the same minimal DN architecture but with weights initialized based on unsupervised layerwise pretraining which we consider as a data-aware initialization (no label information is used) (Belilovsky et al., 2019). In both cases, training is done on the classification task in 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, we see that the ability of pruning methods and, in particular, LT to produce better-performing minimal DNs than directly training the same minimal DN lies in the lack of good initialization for Deep Networks.
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 pretraining, respectively. We observer that (1) when the pruning ratio is low (i.e., < 50%), networks with lottery initialization require a smaller number of computational FLOPs to provide a good initialization for the pruned network, while leading to a comparable or even higher retraining accuracy; and (2) when the pruning ratio is higher, layerwise pretraining requires a much smaller number of computational FLOPs as compared to training highly overparametrized dense networks. Such a phenomenon opens a door for investigating the following two questions, which we leave as our further works.
• Is there a clear boundary/condition to show whether we should start from overparametrization or consider pretraining as a good initialization for samll DNs instead?
• How much overparametrization do we need to maintain better trade-offs 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 et 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 LT training and DN pruning as they provide a universal solution.

heading: J ANALYSIS ABOUT WHY THERE ARE REDUNDANT PARTITION BOUNDARIES
text: Network pruning literature follows the chaining of (i) overparametrization, (ii) training, and (iii) pruning to obtain a small but critical subnetwork, i.e., “winning ticket” that achieve high accuracies. This offers a powerful alternative to training a small network from scratch as good initialization for such sparse network is not known (Frankle & Carbin, 2019a; Blalock et al., 2020) making the optimization challenging. This strategy finds benefits not only with DN but also with traditional methods such as K-means, in which case pruning removes centroids (Kanungo et al., 2002; Hamerly & Elkan, 2002; Celebi et al., 2013). We propose to briefly employK-means to demonstrate 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 a Gaussian Mixture Model (GMM) (Reynolds, 2009) with spherical and identical covariances. Against that baseline, we perform the three-step pruning strategy over multiple runs and with varying numbers of initial clusters to generate winning initialization (denoted as tickets). In all case the clusters will be pruned to 64 (true number of Gaussians) from the initial number that varies from 64 to 128 (-axis of Fig. 10).
We observe that the winning initialization perform near-optimal results (i.e., closer to kmeans++) when starting from overparameterization (i.e., initial clusters ≥ 100), otherwise suffer from large accuracy 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.

heading: K ADDITIONAL RESULTS ON INITIALIZATION AND PRUNING
text: Next we extend the overparametrization-pruning vs. initialization insights to univariate DNs on a carefully designed dataset. Considering a simple unidimensional sawtooth as displayed in Fig. 11 with P peaks (here P = 2). In the special case of a single hidden layer with a ReLU activation function, one must have at least 2P units to perfectly fit this function with the weight configuration being [1]1,k = 1, [1]k = −k with k = 1, . . . , D1 and [2]1,1 = 1, [2]1,k(−2)(k−1)%2, k = 2, . . . , D1. Note that these weights are not unique (other ones can identically fit the function) and are given as an example. At initialization, if the DN has only 2P units, the probability that a random weight initialization arranges the initial splines in 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 are advantageously 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). This is what empirically illustrated in Fig. 11 (right) where one can see that even repeating multiple initializations of a DN without overparametrization does not allow to solve the task, while overparametrizing, training, and then pruning that together preserve only the correct number of units allow for better approximation.

heading: L RELATION BETWEEN ACTIVATION PATTERNS AND SPLINE PARTITION OF
text: INPUT SPACE
Subdivision Lines. Every layer in 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 example, suppose the DNs’ input space is shaped as a square grid with N × N data points, we extract the activations from one intermediate layer of k hidden nodes, then each node corresponds one subdivision line to distinguish non-zero activations in the input grid, thus we have k subdivision lines in this layer, same as the number of hidden nodes. From such geometry perspective, there are two good characteristics to leverage: (1) Subdivision lines in the first layer are linear affine functions taking layer parameters as slopes and biases, following subdivision lines are piecewise linear, whose turning points are exactly located at the subdivision lines in previous layers; (2) The derived subdivision lines at
the final classification layer are exactly the network decision boundary. Such connection provides us a new perspective to analyze how the decision boundary are gradually formulated and what network compression methods (e.g., pruning, quantization) really mean from such geometry perspective.

heading: M EARLY-BIRD VISUALIZATION ON TEST AND RANDOM SAMPLES
text: To investigate what happens to the partitioned regions that do not contain any training data, we redraw Fig. 5 (early-bird visualization) on test samples, and show the visualization of early-bird phenomenon at Fig. 13.

heading: N SPLINE TRAJECTORY AND EB TICKETS WITH LEAKY RELU ACTIVATION
text: 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 at Fig. 15. From these figures, we can consistently observe that the splines
will adapt during the early phase while converging at later training stages, demonstrating that the early-bird phenomenon still holds under the Leaky 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 to -0.44% ∼ +1.38% accuracy improvement and up to 4× training flops savings.

heading: O COMPARISON UNDER 90% PRUNING RATIOS
text: As shown in the Table 10, the proposed spline pruning outperforms the baselines across two models (PreResNet-101 and VGG-16) and two datasets (CIFAR-10 and CIFAR-100), leading to -0.35% ∼ +63.87% accuracy improvements. Note that the network slimming (NS) method suffers from bottleneck layers due to the “over-pruning” channels on specific layers.

heading: P COMPARISON WITH ITERATIVE PRUNING METHODS
text: We further supply the comparison with network slimming with the mentioned iterative pruning method (NS-IP). As shown in the Table 11, our spline pruning again outperforms those methods in terms of both accuracy and efficiency, leading to -0.47% ∼ +1.11% accuracy improvement and up to 7.1× training flops savings. We will add this set of experiments and discussion in our revision.

heading: Q QUANTITATIVE DISTANCES OF DIFFERENT LAYERS ALONG TRAINING TRAJECTORY
text: 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.

heading: R SPLINE PRUNING FOR VISION TRANSFORMER (VIT)?
text: For self-attention layers in ViT, the spline theory is not directly applicable due to the softmax function 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.

Review summaries:
This paper presents a novel methodology for deep network pruning from the perspective of the max-affine spline. The key idea of the paper is to remove the redundant subdivision splines and find winning tickets. This is an interesting and very nicely written paper that bridges the max-affine spline formulation and empirical pruning techniques. The authors provide a sufficient and straightforward introduction of the behind motivation. Beyond these, the authors discuss robustness considerations and perform thorough experiments on various benchmarked models and datasets, showing the favorable performance of their method.

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. 

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. 

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.