NTK-SAP: Improving neural network pruning by aligning training dynamics
Authors: Yite Wang
Dawei Li
Ruoyu Sun
Venue: ICLR 2023 poster (2023)
Keywords: empirical deep learning
pruning at initialization
neural network pruning

Abstract: Pruning neural networks before training has received increasing interest due to its potential to reduce training time and memory. One popular method is to prune the connections based on a  certain metric, but it is not entirely clear what metric is the best choice. Recent advances in neural tangent kernel (NTK) theory suggest that the training dynamics of large enough neural networks is closely related to the spectrum of the NTK. Motivated by this finding, we propose to prune the connections that have the least influence on the spectrum of the NTK. This method can help maintain the NTK spectrum, which may help align the training dynamics to that of its dense counterpart. However, one possible issue is that the fixed-weight-NTK corresponding to a given initial point can be very different from the NTK corresponding to later iterates during the training phase. We further propose to sample multiple realizations of random weights to estimate the NTK spectrum. Note that our approach is weight-agnostic, which is different from most existing methods that are weight-dependent. In addition, we use random inputs to compute the fixed-weight-NTK, making our method data-agnostic as well. We name our foresight pruning algorithm Neural Tangent Kernel Spectrum-Aware Pruning (NTK-SAP). Empirically, our method achieves better performance than all baselines on multiple datasets.

Published as a conference paper at ICLR 2023
NTK-SAP: IMPROVING NEURAL NETWORK PRUNING BY ALIGNING TRAINING DYNAMICS
Yite Wang's Dawei Li', Ruoyu Sun
l University of Illinois crhaan-Champaign, USA
Shenzhen International Center for Industrial and Applied Mathematics, Shenzhen Research Institute of Big Data
3 "Scoool of Data Science, The Chinese University of Hong Kong, Shenzhen, China (y (yitew2, dawei2 @ fillinois edu, sunruoyu cuhk. edu. cn.
ABSTRACT
Pruning neural networks before training has received increasing interest due to its potential to reduce training time and memory. One popular method to prune the connections based on a certain metric, but it is not entirely clear what metric is the best choice. Recent advances in neural tangent kernel (NTK) theory suggest that the training dynamics of large enough neural networks is closely related to the spectrum of the NTK. Motivated by this finding, we propose to prune the connections that have the least influence the spectrum of the NTK. This method can help maintain the NTK spectrum, which may help align the training dynamics that of its dense counterpart. However, one possible issue is that the fixed- weight-NTK corresponding to a given initial point can be very different from the NTK corresponding to later iterates during the training phase. We further propose to sample multiple realizations of random weights to estimate the NTK spectrum. Note that our approach is weight-agnostic, which is different from most existing methods that are weight-dependent. In addition, we use random inputs compute the Hxxedweightt-NTE making our method data-agnostic as well. We name our foresight pruning algorithm Neural Tangent Kernel Spectrum-Awarc Pruning (NTK-SAI) Empirically, our method achieves better performance than all baselines multiple datasets. Our code is available at hhtpp:: / // comm/iiteangee Soainngg/TKSS550
INTRODUCTION
The past decade has witnessed the success of deep neural networks (DNNs) in various applications. Modern DNNs are usually highly weer-parameterized, making training and deployment computation- ally expensive. Network pruning has emerged as a powerful tool for reducing time and memory costs. There are mainly two types of pruning methods: post-hoc pruning (Han et al. 2015) Renda al.
2020 Molchanov et al. 2019 LeCun et al.] 1989 Hassibi & Stork
1992) and foresight pruning (Lee
al. 2018 Wang et al. 20200] Alizadeh et al. 2022] Tanaka et al. 2020 de Jorge al. 2020b Liu
& Zenke 2020). The former methods prune the network after training the large network, while the
latter methods prune the network before training. In this paper, we focus on foresight pruning.
SNIP (Lee et al. 2018) is probably the first foresight pruning method for modern neural networks. prunes those initial weights that have the least impact on the initial loss function. SNIP can be viewed as a special case of saliency score based pruning: prune the connections that have the least "saliency scores", where the saliency score is a certain metric that measures the importance of the connections. For SNIP, the saliency score of a connection is the difference of loss function before and after pruning this connection. GraSP (Wang et al. 2020) and Synflow (aaaka et al. 2020) used two different saliency scores. One possible issue of these saliency scores is that they related to the initial few steps of training, and thus may not be good choices for later stages of training. Is there saliency score that is more directly related to the whole training dynamics?
"Corresponding author.

---

Published as a conference paper at ICLR 2023
1.1
OUR METHODOLOGY
Recently, there are many works on the global optimization of neural networks; see, e.g., Liang et al.
(2018b 2019: 202T k Venturi al. (2018); Safran & Shamir (2017): x Li al. (2022); Ding al.
(2022): Soltano kotabi et al. (2019) Sun et al. (2020a)) Lin et al. (202 l bb: Zhang et al. (022 and
the surveys Sun et al. (2020b) g Sun 2020p. Among them, one line of research uses neural tangent
kernel (NTK) (Jacot et al. 2018) to describe the gradient descent dynamics of DNNs when the network size large enough. More specifically, for large enough DNNs, the NTK is asymptotically constant during training, and the convergence behavior can be characterized by the spectrum of the NTK. This theory indicates that the spectrum of the NTK might be a reasonable metric for the whole training dynamics instead of just few initial iterations. It is then natural to consider the following conceptual pruning method: prune the connections that have the least impact on the NTK spectrum.
There are a few questions implementing this conceptual pruning method.
First, what metric to compute? Computing the whole cigenspectrum of the NTK is too time- consuming. Following the practice in numerical linear algebra and deep learning (Lee et al. 2019a Xiao et al. 2020), we use the nuclear norm (sum of eigenvalues) as a scalar indicator of the spectrum.
Second, what "NTK" matrix to pick? We call the NTK matrix defined for the given architecture with a random initialization as a fixee-weight-NTKK and use "analytic NTK" (Jacot et al.] (018)) to refer to the asymptotic limit of the Exed-weight-NTT as the network width goes to infinity. The analytic NTK is the one studied in NTK theory (Jacot et al. 2018), and we think its spectrum may serve as performance indicator of certain architecture throughout the whole training process [ However, computing its nuclear norm is still too time-consuming (either using the analytic form given in Jacot al. 2018) or handling an ultra-wide network). The nuclear norm of Exeddweiight-TTK NTK easy to compute, but the weed-weight-NN NTK may be quite different from the analytic NTK. To resolve this issue, we notice a less- mentioned fact: the analytic NTK is also the limit of the expectation (over random weights) of fixed-weigh--Ye weight-NTK for given width. The expectation of weigh-eigt shall better approximation of analytic NTK than single Exeddweight-NTe Of course, to estimate the expectation, we can use a few "samples" of weight configurations and compute the average of few Weight
and thus it can be approximated by the expectation of fixed-
One more possible issue arises: would computing, say, 100 Weigh- take 100 times more computation cost? We use one more computation trick to keep the computation cost low: for each mini-batch of input, we use fresh sample of weight configuration to compute one fixed-weight-NTK (or, more precisely, its nuclear norm). This will not increase the computation cost compared to computing the weigh-weight-NTK for weight configuration with 100 mini-batches. We call this "new-input-new-weige
(NINW) trick.
We name the proposed foresight pruning algorithm Neural Tangent Kernel Spectrum- Aware Pruning (NTK-SAP). We show that NTK-SAP is competitive on multiple datasets, including CIFAR-10, CIFAR-100, Tiny-ImageNet, and ImageNet. In summary, our contributions are:
We propose a dicory-motivated foresight pruning method named NTK-SAP, which prunes networks based on the spectrum of NTK.
We introduce a multi-sampling formulation which uses different weight configurations to better capture the expected behavior of pruned neural networks. A "new-input-ne www--nnuutneewwwieeeee weight" (NINW) trick is leveraged to reduce the computational cost, and may be of independent interest.
Empirically, we show that NTK-SAP, as data-agnostic foresight pruning method, achieves offee-of-th-aan art performance in multiple settings.
2 RELATED WORK AND BACKGROUND
Pruning after training (Post-hoc pruning). Post-hoc pruning can be dated back to the 1980s (Janowsky] 1989, Mozer Smolensky 1989) and they usually require multiple rounds train- prune-retrain procedure (Han et al. 2015 LeCun al. 1989). Most of these pruning methods use
Plicase see Appendix B.2 for more discussions from an empirical perspective. This is subtle point, and refer the readers Appendix B.1 for more discussions.
2

---

Published as a conference paper at ICLR 2023
magnitude (Han et al. 2015), Hessian (LeCun al. 1989 Hassibi & Stork 1992. Molchanov et al. 2019) and other information (Dai et al. 2018: Guo et 2016 Dong et al. 2017; Yu et 20188) to define the scoring metrics which determine which weights to prune. Some other recent works (Verma & Pesquet 2021) identify sparse networks through iterative optimization. Most post-hoc pruning methods intend to reduce the inference time, with the exception of lottery ticket pruning (Frankle &
Carbin 2018 Renda et al. 2020) which prunes the networks for the purpose of finding trainable sub-network.
Pruning during training. Another class of pruning algorithms gradually sparsifies dense neural network during training. Some works use explicit & (Louizos et al. 2017) & (Wen et al.
2016)
regularization to learn a sparse solution. Other works introduce trainable masks (Liu et al.
2020
Savarese et al. 2020; Kang & Han 2020, Kusupati et al. 2020 Srinivas et al., 2017: 7 Xiao et al.
2019) or use projected gradient descent (Zhou et al. 2021) to specifically learn the connections
to be remained. DST methods (Mocanu al. 20188] Bellec et al. 2017; Mostafa & Wang 2019
Dettmers & Zettlemoyer 2019 Liu et al., 202 lb Evci et al. 2020 Liu et al. 2021e a) train the
neural network with a fixed parameter count budget while gradually adjust the parameters throughout
training. Moreover, another line of work (You al. 2019) tries to identify the winning ticket at early epochs. These methods can reduce some training time, but often do not reduce the memory cost of training.
Pruning before training (foresight pruning). SNIP Lee et al. 2018) is arguably the first foresight pruning method. Later, GraSP (Wang et al.] 2020) uses deessian-rrdden product design the pruning metric. To address the layer collapse issue of SNIP and GraSP at high sparsity ratios, Synflow (Tanaka et al. (2020) prunes the network iteratively in data-independent manner. FORCE and Heratiiv SNIP (de Jorge et al.) (220a) also intend to improve the performance of SNIP at high sparsity ratios. Lee al. (2019b) uses orthogonal constraint to improve signal propagation of networks pruned by SNIP. Neural tangent transfer (Liu & Zenke (020) explicitly lets subnetworks learn the full empirical neural tangent kernel of dense networks. PropsPr (Alizadeh et al., 2022) also mentions the "shortsightedness" of existing foresight pruning methods and proposes to use meta- tere-rrddiints to utilize the information of the first few iterations.
3 GENERAL PIPELINE FOR FORESIGHT PRUNING METHODS
In this section, we review the formulation of pruning- at- initializaaionn problem and revisit several existing foresight pruning methods. Here we consider Synflow (Tanaka et al., 2020). GraSP (Wang)
cet al. 2020), SNIP (Lee et al. 2018) and Iterative SNIP (de Jorge et al. 2020b). When given a dataset
D X3, yi) == and an untrained neural network f(:; 0) parameterized by 0 [0- 0 ...... .0} E
RP. we are interested in finding a binary mask = {mm] m² .m²) } (0. 1) } which minimizes the following equation:
min C(A(Oo, m) @ m; D) = min - Σ
1
C(f(x; A(0o. m) @ m)
1=1
s.t. m E 10, |mmll/p S dd1--
where A and d - 11 1--k k are the target sparsity and density, 0, is an initialization point which follows a specific weight initialization method P (e.g. Xavier initialization). C denotes the Hadamard product, and A denotes a training algorithm (e.g. Adam) which takes mask m as well as initialization Op. and outputs trained weights at convergence iimal @ m.
Since directly minimizing Equation (I) is intractable, existing foresight pruning methods assign each mask and corresponding weight at initialization og with saliency score S(()) in the following generalized form:
OI
OT ae
S(m²) = -(()) = 3má
0g
where I a function of parameters Ou and corresponding mask m. Intuitively, Equation 2 measures the influence of removing connection m on I. Once the saliency score for each mask computed, we will only keep the top-d masks. Specifically, the masks with the highest saliency scores will be retained (mi² = 1), while other masks will be pruned (m² 0).
3

---

Published as a conference paper at ICLR 2023
SNIP. SNIP (Lee et al. 2018) defines (SNIp(m²)= = Om 8 where D C. D is a subset of 00g
the whole training set. SNIP prunes the whole network in one round.
Iterative SNIP. The saliency score of Iterative SNIF (de Jorge et al. original SNIP. However, multiple rounds of pruning are performed.
2020b) remains the same as the
GraSP. GraSP (Wang et al. 2020 defines Surss((m²) = ( O m: D)
)C(0)em: b%.
30:
where H. is the Hessian matrix. Additionally, GraSP is also single round foresight pruning method.
Synflow. Synflow TTnaka et al. 2020) uses Ssyallow (m²) 0 0.,, f11:000)0mm.
18%| saliency
score, where Ju denotes the k-th output logit, 1 denotes an input full of 1s, and ( ((110)) means replacing all the parameters of the neural network by their absolute values. Similar to Iterative SNIP, Synflow is also an iterative pruning method but in a data agnostic manner.
REVIEW OF NEURAL TANGENT KERNEL
Recent works (Jacot et al. 2018 Lee et al. 2019a; Arora al. 2019 Xiao et al. 2020) study the training dynamics of large DNNs under gradient descent. Formally, let D = [ Yi) Yi) i= C
IT x R denote the training set and let X' = {x : (x,y) E D). y = ly (x,y) E D} denote inputs and labels, respectively. Consider neural network f(= () parameterized by weights O. Let ( E( ((xy)E(Xx))) {(f(x; y) denote the empirical loss where is the loss function. Thus, 0) E R is the concatenated vector of predictions for all training inputs. Under continuous time gradient descent with learning rate 7) the evolution of the parameters 0,, where we emphasize the dependence of 0 on time i, and the training loss of the neural network L can be expressed (Lee et al. 2019a) as
0, = - V. (x; 0x 1(2:0.)
C = V ,(x,,,) (x: ((.,((x)000
-V. XX,, s(
(4)
where we obtain the NTK at time t:
. X: 0,) I(X; 0.) Vo, E RR knxkn
(5)
It is proven that when the width of the neural network becomes sufficiently large (Jacot al. 2018
Arora et al. 2019). the feightweigtt-NTK converges to deterministic matrix ( X'), which we term analytic NTK. The analytic NTK remains asymptotically constant throughout training, i.c. O, (X, x Oo(X, Vt 2 0.
The condition number of the NTK is related to neural network optimization. The condition number of the NTK is known to be important in neural network optimization. Specifically, let the eigenvalue decomposition of the NTK at initialization be Oo X) UT AU where A diag(X), Ate) is the diagonal matrix containing all the eigenvalues of the NTK.
For ladth-width networks, the mean prediction of the neural network in the eigenbasis of NTK can be approximately described as (UE [f()))); = e (= (Xiao et al. 2020)) Therefore, when using the largest possible learning rate 7) ~ 2/X, (Lee et al. 2019a), the convergence rate of the smallest eigenvalue is related to / /An. which is the condition number of the NTK. Empirically, the condition number of the NTK has been successfully used to identify promising architectures in the neural architecture search (NAS) field (Chen et al. 2021 Wang et al. (022).
The entire spectrum of the NTK is a better measure. However, the smallest and the largest eigenvalues only provide very limited information on the optimization property of the DNNs. In the classical optimization theory, the convergence speed depends on all eigenvalues of the Hessians, as different eigenvalues control the convergence of different eigen-modes. Similarly, for neural networks, a few works (Kopitkov& & Indelman 2020 Su & Yang 2019) have shown that the convergence speed depends on eigenvalues other than the smallest eigenvalue. In this sense, compared only considering the condition number of the NTK, controlling the entire eigenspectrum may be better way to ensure the satisfactory optimization performance of DNNs.
'We do not consider FORCE in this work since we find empirically that FORCE is less stable than Iterative SNTP. See Appendix [ for a detailed comparison.
4

---

Published as a conference paper at ICLR 2023
5 OUR METHOD
5.1 ACCOUNT FOR THE EFFECTS OF THE ENTIRE EIGENSPECTRUM WITH TRACE NORM
As discussed Section the eigenspeetrum of the NTK captures the training dynamics of large DNNs, and thus we intend to use the NTK spectrum to guide foresight pruning. More specifically, we would like to keep the spectrum of the pruned network close to that of the large network, so that the pruned network may perform similarly to the large network.
As discussed in Section 3] the saliency-score-biine based method requires using a single metric to capture the optimization performance. This single metric is often scalar, and thus want to generate scalar to capture the information of the whole spectrum. A very natural choice is to use the average value of all eigenvalues. In fact. |Pennington the optimization property of DNNs through the average eigenvalues of the NTK (or a related matrix called input-output Jacobian) explicitly or implicitly Additionally, using the average eigenvalues have also a few good properties which make it more suitable than other metrics for pruning:
al. (2017) 2018); Shu et al. (202T) indeed analyze
Computational efficiency. To begin with, the computational cost of computing all the eigenvalues would be too expensive. On the contrary, trace norm can be efficiently computed, which we will show in Section 5.2
Potentially preserve the entire spectrum. As indicated in Section 3 the saliency score for each weight measures the change of the metric (here it is the trace norm of the NTK) when removing the weight. More precisely, removing weights with smaller saliency score is less likely to induce significant change to the eigenvalue distribution. Hence, using the NTK trace norm as the indicator beneficial in maintaining the entire spectrum.
5.2 APPROXIMATING THE TRACE NORM THE NTK
Nuclear norm proxy of the whole spectrum. The NTK is symmetric matrix. Hence, the trace of the NTK is equivalent to the squared Frobenius norm of parameter-output Jacobian, i.e.
1ool- ||Oullr = eV f (X: 0o)
(6)
Finite difference approximation. Computing the Frobenius norm of the Jacobian matrix [XX; 0o) Rp is memory and computation heavy. More specifically, a naive solution that constructs the Jacobian matrix explicitly for batch of training data may require at least rounds of backward propagation, where & is as large 1000 for ImageNet classification task. So approximation is needed.
One possible way is to lower-bound it using loss gradient with respect to weights Vv,CCll Such method has been studied in FORCE (de Jorge et al. 2020b) but found to inferior to Iterative SNIP.
Alternatively, we the finite difference expression ! [Eao [IIf(X;; f(X;; 6. + A0) to approximate the Jacobian norm. Please see Appendix for the justification.
Approximating the training set with pruning set. We use the following finite approximation expression to define a saliency score:
SNTK SAP(med = DESo [II((>;; On o m) ((X:: (On + A0) m
dmi
where we use the inputs of the pruning dataset Xp to approximate the whole training inputs X. Our foresight pruning method will use the same framework shown in Section which prunes the weights with the least saliency scores defined in Equation (7). Nevertheless, a few more tricks are needed to make this method practical, as discussed next.
5.3 NTK-SAP:
FORMULATION
The last subsection computes the saliency using the fiigh-wwigtt-NTKK We think the spec- trum of analytic NTK may serve as performance indicator certain architecture. While a single Wixe can be viewed as approximation of the analytic NTK, the expectation
5

---

Published as a conference paper at ICLR 2023
of Sked-weight-NTIE (expecation over random draw of weight configurations) shall be better approximation. Further, to approximate the expectation, we sample a few independent realization of weight configurations and compute the average of their fixed-weigtt Sxedd-wiggt--TKK This helps explore the parameter space and better capture the expected behavior of the pruned neural networks.
Specifically, with random weight configurations 0,, of the saliency score:
iid
P, we use the following stabilized version
0 n Er= (a
[X 0 m) f(Xpi (0o.- + A0)
SA
dm
(8)
There is a major difference between the proposed saliency score and most existing foresight pruning scores: our score weight-agnostic, i.e., is not defined by a specific random draw of weight configuration. In other words, the score is mainly determined by the mask structure rather than specific weights
New-input-new-weiie (NINW) trick. It seems that using multiple weight configurations will cause a large increase in the computational cost. Nevertheless, by utilizing the fact that the training subset
for pruning D = (z)
== C D is usually fed into neural networks in multiple batches, we further
[P]
approximate Equation with NINW trick
8 DDT
Σ
= Eso~N(0.))
[x); to, @ m) - f'x;;; (fo.i + A0) dmd
Replacing pruning set with random input. Furthermore, we find that replacing the training subset D with standard Gaussian noise Z ~ ~~(0 I) can generate comparable performance, which makes NTK-SAP purely data-agnostic. As for Gassuan perturbation, ideally, using multiple draws will indeed give a more accurate approximation. However, we empirically find that a single draw of Gaussian perturbation is good enough to generate satisfactory performance. Hence, by using one random draw of AO we have the final data-agnostic NTK-SAP with its saliency score
[Z: 0, m) f(2;; (Oo. + A0:) m)
SNTKsAA(mm')
(10)
dml
where Oo.; P. A0, /O el) and NOO I).
In addition, to potentially avoid layer collapse, we also iteratively prune neural networks like Synflow in T rounds The major steps of the NTK-SAP algorithm are given in Algorithm [
Computational cost. We compare the computational cost of -TK-SAP with Iterative SNIP as they are both iterative methods and use multi-batch inputs. Since the overhead of the reinitialization process is negligible, NTK-SAP needs roughly double the computational cost Iterative SNIP due to two forward passes with the computational graph in the formula. However, should note that NTK-SAP is a data- tata-agnostic method that can be computed beforehand, and the computation time can be reduced with smaller T; thus, the computational overhead is reasonable. Effects of T, detailed comparison of pruning time, and FL.OPs comparison can be found in Section 6.4 Appendix D.I and Appendix D.2. respectively.
EXPERIMENTS
In this section, empirically evaluate the effectiveness of our proposed method, NTK-SAP (red). We compare with two baseline methods random pruning (gray) and magnitude pruning (magenta), as
*lease refer to Appendix M for a discussion on whether a good pruning solution should be weight-agnostic.
*Plcase refer Appendix for discussion on why NTK-SAP could potentially avoid layer collapse.

---

Published as a conference paper at ICLR 2023
Algorithm 1 Neural Tagent Kernel Spectrun-Aware Pruning (NTK-SAP)
Require: Dense network ((:00m)) final density d, iteration steps T, batch size of noise imput B, perturbation hyperparameter Initialize m
2: for t in [1, ... 1" do
3: for i in [1,-... BJ do
4: Reinitialize neural network with oo, lid
5: Sample noise input z: sid (0, and parameter perturbation 20, iid N cl)
6: Evaluate saliency scores [mm],,
7:
end for
8:
Calculate S(m) = E (m)).
9:
Compute (1 - d+) percentile of S(m) as threshold
10: Update mask m @ (S(m) r)
end for
12: return Final mask m
2osNet-20 (CIFAR-1 10)
VGG- 16 (CIFAR 100)
Test Anturaty (1))
Text: Anturnyy (50
93.12
150
3kum
8aotti
73
80,220
093 PM
ah
87
40
Sparsity (g
Sparsty (%:
ResNet-18 18 (Tiny ImageNel)
SNIP
GraSP
22
Thst Anturacy (h0
Iterative SNIP
Synflow
Magnitude
Random
NTK-AAP (Ours)
14088
50648
RE228
89.mm
93128
2549%
97.7%
20.00%
Sparaty (
Figure I: Performance of NTK- SAP against other foresight pruning methods. Results are averaged over 3 random seeds, and the shaded areas denote the standard deviation. We highlight SNIP and GraSP as they perform best among baselines on mild and extreme density ratios, respectively.
well as foresight pruning algorithms SNIP (blue) Lee et al. 2018), Iterative SNIP (yellow) de Jorge al. 20206), GraSP (green) (Wang et al. 2020 and Synflow (cyan) (Tanaka al.) 2020 across multiple architectures and datasets.
Target datasets, models, and sparsity ratios. We develop our code based on the original code of Synflow (Tanaka et al., 2020). On smaller datasets, we consider ResNet-20 (He et al. 2016) on
CIFAR-10, VGG-16 (Simonyan Zisserman) 2014) on CIFAR- 100 (Krizhevsky et al., 2009) and
R8sNet-18 on Iiny-Ima For ImageNet (Deng al.) 2009) experiments, we consider ResNet- 18 and ResNet-50. For the training protocols, we roughly follow the settings in Frankle et al. (2020b). be found in Appendix A We divide the sparsity ratios into three ranges: trivial sparsity ratios (36.00%, 59.04% and 73.80%), mild sparsity ratios (83.22% 89.30% and 93.1 12%) and extreme sparsity ratios (95.60%, 97.17% and 98. 98.20%)
Details of training hyperparameters

---

Published as a conference paper at ICLR 2023
Implementation details. Following the original implementation, SNIP, GraSP, and Iterative SNIP are run by setting BatchNorm layers as train mode while Synflow metric is evaluated under evaluation mode. The number of training samples for pruning
use is ten times of the number of classes as suggested by the original implementations of SNIP and GraSP. For iterative methods, including Iterative SNIP and Synflow, we prune all the weights in 100 rounds in an exponential schedule following Tanaka et al. (2020); Frankle et al. (2020b). Further, following Frankle et al. (2020b), Kaiming normal initialization is used for all models. We prune networks using a batch size of 256 for CIFAR- 10/100 and Tiny- ImageNet datasets and batch size of 128 for ImageNet experiments.
For NTK-SAP, we use the same number of Gaussian noise batches as in Iterative SNIP and prunes neural network progressively in T = 100 rounds for CIFAR-100 and Tiny Imageee.. Since the pruning dataset for CIFAR-10 only contains batch of the training sample, we alternatively sample R 5 independent initialization points and prune progressively in T 20 rounds, keeping the overall computational cost roughly the same. More details can be found in Appendix
6.1 RESULTS ON CIFAR AND TINY-IMAGENET
In Figure T we evaluate NTK-SAP using ResNet-20 CIFAR-10, VGG-16 CIFAR-100 100 and ResNet-18 on Tiny-lmageNet. It can be observed that NTK- is competitive for all sparsity ratios.
Trivial and mild sparsity ratios. For trivial sparsity ratios, all methods show good performance except GraSP, magnitude, and random pruning. On ResNet-20, all methods are similar, while random pruning and GraSP show slightly worse performance. On VGG-16 16 (ResNet- 18), similar trend can be observed while the performance gap is larger. NTK-SAP shows consistent good performance, especially R8 (TinyImageNet).
For mild sparsity ratios, NTK-SAP is the only method that performs well across all datasets and models. On ResNet-20, SNIP and Iterative SNIP take the lead with NTK-SAP while suffering from performance drop starting at 92% sparsity. Magnitude pruning and GraSP have similar performance to NTK -SP after 89.30%. On VGG-16 and ResNet-18, NTK-SAP and SNIP remain dominant, while NTK SAP outperforms SNIP.
Extreme sparsity ratios. NTK-SAP's superior performance can be seen at extreme sparsity ratios, especially 98.20%. On the CIFAR-10 dataset, GraSP and magnitude pruning are competitive as in matching sparsity ratios. On VGG-16, SNIP first dominates with NTK-SAP and then becomes much inferior. At the sparsest level 98. 38.20% magnitude, Iterative SNIP, and GraSP show similar results, about percentage point lower than NTK-SAP.
6.2 RESULTS ON LARGER DATASET
We further evaluate the performance of NTK-SAP more difficult tasks: experiments the ImageNet dataset using ResNet-18 18 and ResNet-50 with pruning ratios (89.26%, 95.60% _ We compare NTK-SAP against Synflow, SNIP, Iterative SNIP, GraSP, Magnitude, and Random pruning.
The results are shown in Table I We find that SNIP, which performs reasonably well for smaller datasets, is longer competitive. For ResNet-50, NTK-SA beats other pruning methods with margins at least 0.5% and 1 % for sparsity ratio 99.26% and 95. 60%, respectively. For ResNet-18, 18, NTK-SAP slightly outperforms magnitude pruning under 89.26% sparsity, and GraSP follows. For sparsity ratio 95.60 %. GraSP is better than magnitude pruning while NTK-SAP still takes the lead.
One should note the surprisingly good performance of magnitude pruning. We hypothesize that mag- nitude pruning chooses an appropriate layer-wise sparsity ratio since Kaiming normal initialization already gives weights different variances depending on the number of parameters of different layers. Thus, layers with more parameters will be more likely pruned.
6.3 AN OVERALL COMPARISON WITH SNIP AND GRASP
In this section, we explicitly compare NTK-SAP with two competitive baseline methods detail, i.e., SNIP and GraSP, since there is state-of -ft-----tthhteeeee art foresight pruning algorithms (Frankle et al. 2020b).
'e choose these sparsity ratios as they include matching and extreme sparsity ratios and close to (90%. 95%) as used by Iterative SNIP (de Jorge 2020b) and ProsPr (Alizadeh et al. 2022.
8

---

Published as a conference paper at ICLR 2023
Table 1: Test performance of foresight pruning meth- ods on the ImageNet dataset. Best results are in bold; second- beooddbbett results are underlined.
Bune
10
Network
ResNet-18
ResNet-50
NTKSAP
Sparsity percentage
89.26%
95.60%
89.26%
95.60%
(Dense Baseline)
69.98
76.20
Synßow
57.30
45.65
66.81
58.88
16
SNIP
57.41
45.04
60.98
40.69
200
605
500
300
2000
Iterative SNIP
52.97
37.44
52.53
36.82
Ripeoraloon ttalos
GraSP
56.16
49.17
67.74
59.73
Magnitude
58.75
48.50
66.80
43.79
Figure 2:
Eigenvalue distribution of the fixed -eigh-eeigh--TTK on ResNet-20 (CIFAR-
Random
54.48
42.80
65,30
56.53
Our method
58.87
49,43
68.28
60.79
10) at sparsity ratio 73.80%.
We highlight both baseline algorithms in Figure [ Specifically, SNIP considered competitive as it generally performs well, especially for trivial and mild sparsity ratios. However, SNIP shows poor performance for ImageNet. On the contrary, GraSP indeed shows promising performance on the ImageNet dataset and extreme sparsity ratios smaller datasets, while it suffers from poor performance on trivial and mild sparsity ratios of smaller datasets. In this sense, NTK-SAP is the first foresight pruning algorithm that works consistently well on all datasets.
6.4 MORE ABLATION STUDIES
We finally evaluate the performance of NTK-SAP when varying the number of iterative steps (T), which can give better understanding of how iterative pruning helps NTK-SAP achieve better performance at higher sparsity ratios. We repeat experiments of Section 1 with varying T. Results show that increasing 7 consistently boosts the performance NTK-SAP. Moreover, such an increase saturates when 7 is roughly 1/5 of the adopted value in Section 6.1 Hence, the computational cost of -TP-SAP can be further decreased we use a smaller value T. Please refer to Appendix C for more details. We also conduct ablation study the effects of perturbation hyperparameter Results show that NTK-SAP is robust to the choices of c. See Appendix []] for more details.
6.5 THE EIGENSPECTRUM OF THE FIXED-WEIHT-IEE AFTER PRUNING
To visualize the effectiveness of our proposed NTK-SAP method, we show eigenspectrum pruned subnetwork on CIFAR-10 10 dataset with ResNet-20 at sparsity ratios 73.80%. Figure 2 shows that NTK-SAP successfully maintain the eigenspectrum of the txed-weight-We compared other methods. See Appendix G.1 for the eigenspectrum of the Neigh- for other sparsity ratios.
7 CONCLUSION
Pruning at initialization is appealing compared to pruning-afeer-trannig algorithms since it circum- vents the need for training to identify the masks. However, most the existing foresight pruning methods do not capture the training dynamics after pruming. We argue that such an issue can be miti- gated by using NTK theory. Hence, we propose NTK-SAP, which itcratively prunes neural networks without any data. Additionally, NTK-SAP pays attention to multiple random draws of initialization points. Empirically, our method is competitive in all datasets and models studied in this work. We consider that algorithm encourage more works apply theoretical findings to empirical applications. Additionally, our novel way of combining multiple initialization configurations may further encourage future work investigate the similarity of pruning and NAS just like Liu al. (0188: Abdelfattah et al. (2021).
The limitations of the work include the relatively heavy computation nature of iterative pruning methods compared to single-shot pruning methods. We also want to emphasize the great significance of pruning methods in reducing the energy cost of training and applying deep learning models.

---

Published as a conference paper at ICLR 2023
8 ACKNOWLEDGEMENT
This work utilizes resources supported by the National Science Foundation's Major Research Instru- mentation program, grant No. 17.57227 (Kindratenko al. 2020), well as the University of Illinois at Trbana-Champaiin. This paper is supported in part by Hetao Shenzhen-Hong Kong Science and Technology Innovation Cooperation Zone Project (No.HZQSWS-KE (CCCYB-202046)) University Development Fund UDF01001491 from the Chinese University of Hong Kong, Shenzhen; Guang- dong Key Lab on the Mathematical Foundation of Artificial Intelligence, Department of Science and Techonology of Guangdong Province.
We would like to thank the program chairs and the area chairs for handling our paper. We would also like to thank the reviewers for their time and efforts in providing constructive suggestions on our paper.
10

---

Published as a conference paper at ICLR 2023
REFERENCES
Mohamed S Abdelfattah, Abhinav Mehrotra, Lukasz Dudziak, and Nicholas D Lane. Zero-cost proxies for lightweight nas, arXiv preprint arXiv:2101.08134 2021.
Milad Alizadeh, Shyam Tailor, Luisa Zintgraf, Joost van Amersfoort, Sebastian Farquhar, Nicholas Donald Lane, and Yarin Gal. Prospect pruning: Finding trainable weights initialization using meta- gradients. arXiv preprint arXiv:2202.08132. 2022.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances Neural Information Processing Systems, 32, 2019.
Guillaume Bellec, David Kappel, Wolfgang Maass, and Robert Legenstein. Deep rewiring: Training very sparse deep networks. arXiv preprint arXiv:1711.05136 2017.
Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural architecture search on imagenet in four gpu hours: theoretically inspired perspective. arXiv preprint arXiv:2102.11535, 2021.
Bin Dai, Chen Zhu, Baining Guo, and David Wipf. Compressing neural networks using the variational information bottleneck. In International Conference on Machine Learning, pp. 1135-1144, PMLR, 2018.
Pau de Jorge, Amartya Sanyal, Harkirat S Behl, Philip HS Torr, Gregory Rogez, and Puneet K Dokania. Progressive skeletonization: Trimming more fat from network at initialization. arXiv preprint arXiv:2006.0900 09081, 2020a.
Pau de Jorge, Amartya Sanyal, Harkirat S Behl, Philip HS Torr, Gregory Rogez, and Puneet K Dokania. Progressive skeletonization: Trimming more fat from a network at initialization. arXiv preprint arXiv:2006.0908 2020b.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. Icee, 2009.
Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance. arXiv preprint arXiv: 1907,04400 2019.
Tian Ding, Dawei Li, and Ruoyu Sun. Suboptimal local minima exist for wide neural networks with smooth activations. Mathematics of Operations Research, 47(4):2784-2814, 2022.
Xin Dong, Shangyu Chen, and Sinno Pan. Learning to prune deep neural networks via layer-wise optimal brain surgeon. Advances in Neural Information Processing Systems, 30, 2017.
Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pp. 2943-2952. PMLR, 2020.
Utku Evci, Yani Ioannou, Cem Keskin, and Yann Dauphin. Gradient flow in sparse neural networks and how lottery tickets win. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 3577-6586, 2022.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv: aaoe::003303333 2018
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. In International Conference on Machine Learning, pp. 3259-3269, PMLR, 2020a.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Pruning neural networks at initialization: Why are we missing the mark? arXiv preprint arXiv:2009.08576 2020b.
Yiwen Guo, Anbang Yao, and Yurong Chen. Dynamic network surgery for efficient dnns. Advances in neural information processing systems, 29, 2016.
11

---

Published as a conference paper at ICLR 2023
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. Advances in neural information processing systems, 28, 2015.
Babak Hassibi and David Stork. Second order derivatives for network pruning: Optimal brain surgeon. Advances in neural information processing systems, 5, 1992.
Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Steven A Janowsky. Pruning versus clipping in neural networks. Physical Review A, 39 (9)66000 1989.
Minsoo Kang and Bohyung Han. Operation-aware soft channel pruning using differentiable masks. In International Conference on Machine Learning, pp. 5122-5131. PMLR, 2020.
Volodymyr Kindratenko, Dawei Mu. Yan Zhan, John Maloney, Sayed Hadi Hashemi, Benjamin Rabe, Ke Xu, Roy Campbell, Jian Peng, and William Gropp. Hal: Computer system for scalable deep learning. Practice and experience in advanced research computing, pp. 41 41-48.155 2020.
Dmitry Kopitkov and Vadim Indelman. Neural spectrum alignment: Empirical study. In International Conference on Artificial Neural Nefworks, pp. 168-179. Springer, 2020.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Aditya Kusupati, Vivek Ramanujan, Raghav Somani, Mitchell Wortsman, Prateek Jain, Sham Kakade, and Ali Farhadi. Soft threshold weight reparamcterization for learnable sparsity. In International Conference Machine Learning, pp. 5544-5555. PMLR, 2020.
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. Advances in neural information processing systems, 32, 2019a.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Single-shot network pruning based connection sensitivity. arXiv preprint
2018
Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip HS Tom. A signal propagation perspective for pruning neural networks at initialization. arXiv preprint arXiv:1906.0633 2019b.
Dawei Li, Tian Ding, and Ruoyu Sun. On the benefit of width for neural networks: Disappearance of basins. SIAM Journal on Optimization, 32(3): 1728)11788755 2022.
Shiyu Liang, Ruoyu Sun, Jason D Lee, and R Srikant. Adding one neuron can eliminate all bad local minima. In Advances in Neural Information Processing Systems, pp.
201 8a.
Shiyu Liang, Ruoyu Sun, Yixuan Li, and Rayadurgam Srikant. Understanding the loss surface of neural networks for binary classification. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2835-2843, PMLR, 10-15 Jul 2018b. URL htttt:tt////occedd/ mlr. wwress/v80/o ptress/v0//laaggll
html
Shiyu Liang, Ruoyu Sun, and R. Srikant. Revisiting landscape analysis in deep neural networks: Eliminating decreasing paths to infinity, 2019.
Shiyu Liang, Ruoyu Sun, and R. Srikant. Achieving small test error in mildly overparameterized neural networks. CoRR, abs/2104.11895 2021. URL
1895
Dachao Lin, Ruoyu Sun, and Zhihua Zhang. Faster directional convergence of linear neural networks under spherically symmetric data. Advances in Neural Information Processing Systems, 34, 2021a.
12

---

Published as a conference paper at ICLR 2023
Dachao Lin, Ruoyu Sun, and Zhihua Zhang. On the landscape of mne-hideen-laye -layer sparse networks and beyond, 2021b.
Junjie Liu, Zhe Xu, Runbin Shi, Ray CC Cheung, and Hayden KH So. Dynamic sparse train- ing: Find efficient sparse network from scratch with trainable masked layers. arXiv preprint wrXiv:2005.06877 2020.
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Zahra Atashgahi, Lu Yin, Huanyu Kou, Li Shen, Mykola Pechenizkiy, Zhangyang Wang, and Decebal Constantin Mocanu. Sparse training via boosting pruning plasticity with neuroregeneration. Advances in Neural Information Processing Systems, 34, 2021a.
Shiwei Liu, Decebal Constantin Mocanu, Yulong Pei, and Mykola Pechenizkiy. Selfish sparse mn training. In International Conference on Machine Learning, pp. 6893-6904, PMLR, 2021b.
Shiwei Liu, Lu Yin, Decebal Constantin Mocanu, and Mykola Pechenizkiy. Do we actually need dense over- parameterization? in-time over paramtteriiiiiionn in sparse training. In International Conference Machine Learning, pp. 6989-7000. PMLR, 2021c.
Tianlin Liu and Friedemann Zenke. Finding trainable sparse networks through neural tangent transfer. In International Conference on Machine Learning, pp. 6336-6347. PMLR, 2020.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell, Rethinking the value of network pruning. arXiv preprint arXiv:
2018.
Christos Louizos, Max Welling, and Diederik P Kingma. Learning sparse neural networks through 1_0 regularization. arXiv preprint arXiv: 1712.1331 2017.
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature communications, 9(1):1-12, 2018.
Pavlo Molchanov, Arun Mallya, Stephen Tyree, Iuri Frosio, and Jan Kautz. Importance estimation for neural network pruning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1264-11277 2019.
Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In International Conference on Machine Learning, pp- 4646-4655. PMLR, 2019.
Michael C Mozer and Paul Smolensky. Using relevance to reduce network size automatically. Connection Science, 1(1):3-16, 1989.
Franco Pellegrini and Giulio Biroli. Neural network pruning denoises the features and makes local connectivity emerge in visual tasks. International Conference on Machine Learning, pp- 17601-17626. PMLR, 2022.
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice. Advances in neural information processing systems, 30, 2017.
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. The emergence of spectral universality in deep networks. In International Conference on Artificial Intelligence and Statistics, pp. 1924- 1932. PMLR, 2018.
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. arXiv preprint NDt:20003.02889 2020.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. arXiv preprint arXiv: 1XI::1712.08663 2017.
Pedro Savarese, Hugo Silva, and Michael Maire. Winning the lottery with continuous sparsification. Advances in Neural Information Processing Systems, 33:1 33:11380 11111300-111 1390, 2020.
13

---

Published as a conference paper at ICLR 2023
Yao Shu, Shaofeng Cai, Zhongxiang Dai, Beng Chin Ooi, and Bryan Kian Hsiang Low. Nasi: Label- and aatt--agnotic neural architecture search at initialization. arXiv preprint arXiv:2109.00817, 2021.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: (eti::140..55500 1556, 2014.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742 769, 2019.
Suraj Srinivas, Akshayvarun Subramanya, and R Venkatesh Babu. Training sparse neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pp. 138- 145, 2017.
Lili Su and Pengkun Yang. On learning werrpaarameterized neural networks: A functional approxi- mation perspective. Advances in Neural Information Processing Systems, 32, 2019.
Ruo- Yu Sun. Optimization for deep learning: An overview. Journal of the Operations Research Society of China, pp. 1-46, 2020.
Ruoyu Sun, Tiantian Fang, and Alexander Schwing. Towards better global loss landscape of gans. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 10186-10198. Curran As- sociates, Inc., 2020a. htt_:ttpss//ppcceediiiii 738a645 220.:6888822223222222333332222
nwwrips CC/ http/paper2222200 file/
Ruoyu Sun, Dawei Li, Shiyu Liang, Tian Ding, and Rayadurgam Srikant. The global landscape of neural networks: An overview. IEEE Signal Processing Magazine, 37(5):95-108, 2020b.
Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks with- out any data by iteratively conserving synaptic flow. Advances in Neural Information Processing Systems, 33:6377- 6389, 2020.
Luca Venturi, Afonso Bandeira, and Joan Bruna. Spurious valleys in two-layer neural network optimization landscapes. arXiv preprint arXiv:1802.0633 2018.
Sagar Verma and Christohet Pesquet. Sparsifying networks via subdifferential inclusion. In International Conference on Machine Learning, pp. 10552.10552. PMLR, 2021.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. arXiv preprint arXiv:2002.07376, 2020.
Haoxiang Wang. Yite Wang. Ruoyu Sun, and Bo Li. Global convergence of maml and theory-inspires neural architecture search for few-shot learning. In CVPR, 2022.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. Advances in neural information processing systems, 29, 2016.
Lechao Xiao, Jeffrey Pennington, and Samuel Schoenholz. Disentangling trainability and generaliza- tion in deep neural networks. In International Conference on Machine Learning, pp. 10462-10472 PMLR, 2020.
Xia Xiao, Zigeng Wang, and Sanguthevar Rajasekaran. Autoprune: Automatic network pruming by regularizing auxiliary parameters. Advances in neural information processing systems, 32, 2019.
Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Richard G Baraniuk, Zhangyang Wang, and Yingyan Lin. Drawing early-bird tickets: Towards more efficient training of deep networks. arXiv preprint arXiv: 1909. 1957, 2019.
Ruichi Yu, Ang Li, Chun-Fu Chen, lui-Hsin Lai, Vlad I Morariu, Xintong Han, Mingfei Gao, Ching Yung Lin, and Larry S Davis. Nisp: Pruming networks using neuron importance score propagation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9194-9203, 2018.
14

---

Published as a conference paper at ICLR 2023
Jiawei Zhang, Yushun Zhang, Mingyi Hong, Ruoyu Sun, and Zhi- Zhi-Quan Luo. When expressivity meets trainability: Fewer than n neurons can work. Advances in Neural Information Processing Systems, 34, 2021.
Xiao Zhou, Weizhong Zhang, Hang Xu, and Tong Zhang. Effective sparsification of neural networks with global sparsity constraint. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 3599-3608, 2021.
15

---

Published as a conference paper at ICLR 2023
OVERVIEW OF THE APPENDIX
The Appendix is organized as follows:
Appendix A
introduuess the general experimental setup.
Appendix B
provides intuitions on our multi-sampling formulation.
Appendix shows an ablation study on the number of iterative steps.
Appendix D
provides a detailed comparison of computational costs different foresight
pruning methods.
Appendix E
provides a further comparison between foresight pruning methods and the early
pruning baseline.
Appendix F
provides comparison of SNIP variants.
Appendix G
shows eigenspectrum of pruned neural networks.
Appendix
provides full plots of the main experiments.
Appendix
provides ablation study on the perturbation hyper-parameter
Appendix
provides overview of foresight pruning methods considered in the paper.
Appendix K
provides comparison between neural tangent transfer and NTK-SAP.
Appendix
provides a comparison between ProsPr and NTK-SAP.
Appendix M
includes discussion on the
property NTK-SAP.
Appendix
includes discussion why NTK-SAP potentially avoid layer collapse.
Appendix O
justifies the finite difference formulation used in Section 5.2
A
EXPERIMENTAL SETUP
Our code is based on the original code of Synflow The original code does not contain license information. But we obtained approval via email. The authors grant free use for academic purposes.
A.1 ARCHITECTURE DETAILS
The networks architectures are as follows:
For the ResNet-20 model on CIFAR-20 and VGG-16 (with BatchNorm) model on CIFAR- 100, the default ones used Synflow (Tanaka et 2020) experiments. Lottery
ticket experiments (Frankle & Carbin 2018 Renda et al. 2020 Frankle et al. 2020a use the same architectures.
For ResNet- 18 and ResNet-50, the ImageNet version of ResNet models We the corchvisions implementations.
A.2 DATASETS
We use CIFAR- 10, CIFAR- 100, Tiny-ImageNet and ImageNet. They do not contain personally identifiable information or offensive content.
CIFAR-10 and CIFAR-100 datasets are augmented by per-channel normalization, applying random cropping (32 32, padding 4), and horizontal flip.
Tiny- Imagelm is augmented by per-channel normalization, choosing a patch with random aspect ratio between 0.8 and 1.25 and a random scale between 0.1 and 1.0, cropping to 64 x 64, and random horizontal flip.
ImageNet dataset is augmented by per-channel normalization, applying random resized cropping to 224 224, and random horizontal flip.
https::/ggitii thwp::///tthubuucooo wei cunzai wttpaaaa/ytoooocccfaaaaa
16

---

Published as a conference paper at ICLR 2023
A.3 TRAINING DETAILS
See Table 2 for training hyper-panne parameters, These byper-parameters are modified from the ones used in Synflow (Tanaka et al, 2020) and Frankle et al. (2020b). the following table, we use Nesterov optimizer to denote SGD optimizer with Nesterov momentum.
Table 2: Training
used in this work.
Network
Dataset
Epochs
Batch
Optimizer
Momectum
LR
LR drop
Weight decay
Initilization
ResNet-20
CIFAR-10
160
128
SGD
0.9
0.1
10x at spochs 80, 120
lc-4
Kaiming Normal
VGG-16
CIFAR- 100
160
128
Nesterov
0.9
0.1
10x at epochs 60, 120
Se
Kaiming Normal
R8sNet-18
Ting-ImageNet
200
256
SGD
0.9
0.2
10x epochs 100, 150
le4
Kaiming Normal
ResNet-18
InageNet
512
SGD
0.9
0.1
[0x, at spochs 30,
1c-4
Kaiming Normal
ResNet-50
ImageNet
90
448
SGD
0.9
0.1
10x at epochs 30, 60, 80
le-4
Kaiming Normal
A.4 PRUNING DETAILS
Sparsity ratios The x-axis for Figure 1 in the logarithmic scale of density (1-sparsity). More specifically, we obtain each sparsity ratio by removing 20% of the remaining parameters twice. For example, the first sparsity ratio 0..8+0.8=0.36. We choose these sparsity ratios evaluate mainly following the conventional practice used in Frankle et al. (2020b). The intuition is that for the first few rounds, the network over-parameterized and a large portion the weights can be removed.
Choosing pruning samples. Different from GraSP implementation, which uses exactly 10 ex- amples of each class, we follow the implementation of SNIP, Iterative SNIP, and Synflow to load multiple batches so that each class roughly has ten samples.
Pruning batch size. To compute the saliency scores, we use a pruning batch size of 128 for ImageNet experiments and use 256 otherwise.
BatchNorm layers. As pointed out by the original Synflow paper. BatchNorm layers are crucial for applying different pruning methods correctly. SNIP, Iterative SNIP, and GraSP prune networks under train mode, while Synflow uses evaluation mode. As for NTK-SAP, we compute the saliency score in a modified evaluation mode. More specifically, we first compute batch statistics without constructing a computational graph, and then use the same batch statisties get an approximation of the NTK nuclear norm under evaluation mode.
Pruning schedule for iterative methods. Following Synflow, all iterative methods, including Synflow, Iterative SNIP, and NTK-SAP, use an exponential pruning schedule. See Algorithm T for how to compute the pruning schedule.
More details about NTK-SAP. For each round of pruning, we use 40 batches (compared to 79 batches for Iterative SNIP) of noise inputs with a batch size of 128 for ResNet-50 on the ImageNet dataset. For other settings, the number of Gaussian inputs for pruning we use is times the number of classes.
As for the number of pruning rounds T. we use 25 for all ImageNet experiments. And we use T 20 rounds for ResNet-20 on CIFAR- 10 with 5 batches each round (as the batch size is larger than the number of classes 10). For CIFAR- 100 and
datasets, we use T' 100 rounds.
For we use value of 10-6 for ResNet- 18 on ImageNet and use value of c 10-4 otherwise.
A.S HARDWARE
All of our experiments were NVIDIA V100s. Experiments CIFAR-10/100 and Tiny- ImageNet datasets were run on a single GPU at a time. We use and GPUs for ResNet-18 18 and ResNet-50 in ImageNet experiments, respectively.
17

---

Published as a conference paper at ICLR 2023
B INTUITION OF MULTI-SAMPLING FORMULATION
B.I UNDERSTANDING MULTI-SAMPLING FORMULATION THROOGHI THE ANALYTIC NTK
In this section, we elaborate on our intuition of performing multi-sampling in NTK-SAP.
We still start our discussion with Equation 7 We note that Equation 7 alone is not enough to guarantee good performance, as there is actually gap in applying NTK theory directly to pruning:
real-world application, the Wxighteight-NTK may differ drastically from the analytic NTK.
Standard expression of the analytic NTK. We note that directly using the fixed-weight-NTKK to approximate the analytic NTK can be written in the following mathematical formulation:
(x),
lim ( (X, 2; 121 000000
(11)
(..:0) (.. with weight 0, A natural way to approximate the analytic NTK is to remove the "lim" operation and just use θ mm (X', X: 0) for a given set of large enough width (nz).
where θ is the analytic NTK, and Ô fgmc)
is the fixed-weight-TTK for width-ny neural networks
Two differences of the analytic NTK and the fixed-weight NTK. We point out that besides the choice of widths, the choice of weights also affects θ (X, 0). In other words, ( X) both width-agnostic and weight-agnostic, while (mx) (X, X:O) O) is width-dependent and weight- dependent. There are two differences between the analytic NTK and the fixed-weight-NTK, but the expression 11 only shows the difference in width and ignores the difference on weights. The underlying reason is that the effects of random weights are offset in infinite-width network, and thus there is no need to eliminate the randomness by adding an operator such as expectation.
Another expression of the analytic NTK. Although not necessary, is legitimate add an "expectation" operator in the expression. We rewrite the analytic NTK as the expectation (over random weights) of the limit (over width) of weight expressed mathematically as follows:
(X = Eg
lim
e fmr) (X', (X, ()
(12)
This formula is correct since Eg
lim 100,0
θ (mi) (X, Xe 0) = Eo (0(X = (x)
Another approximation of the analytic NTK. Although the expectation operator is redundant in the Equation 12] it makes a difference when we consider the finite-width approximation. A natural approximation coming out of Equation is is the following: first, remove the "lim" operation and use a fixed set of large enough width {m:}: second, sample multiple independent weight configurations
and use the average as an approximation the "expectation" Eg (m(m) x;:) for given set of large enough width (mz). Specifically, with R number of independent initialization points, we obtain the stabilized version of the saliency criterion Equation g
B.2 UNDERSTANDING MULTI-SAMPLING FORMULATION THROUGH THE FIXED WEED-WEIGHT-NTK EVOLUTION
In the previous section, we analyzed why multi-sampling gives a better estimate of the analytic NTK than a single draw of -xeddwwight-NTKK This analysis leads to the design of multi-sampling method. However, it may of a finite-width neural network. this section, we provide an explanation of the multi-sampling method from another perspective.
unclear why we want the analytic NTK the performance indicator
When the width goes to infinity, the NTK is almost deterministic and remains asymptotically constant throughout training.
Under such circumstances, the analytic NTK a good measure of the optimization of the large enough network since it measures the expected behavior over random weight configurations and
18

---

Published as a conference paper at ICLR 2023
training trajectory. Let (bu;; t) denotes the parameter of the network at training step t with initial random weight configuration 0g, then
+ O x) = Beo.t
lim >0c,V
@ 0,
(13)
In the finite-width (real-world) setting, the weig- no longer stays constant and is function of time. Though we can no longer describe the whole training process with a single deterministic and constant kernel,
still describe the process with sequence of NTKs.
For simplicity, we consider discrete gradient descent update rule. We can char- acterize the training dynamics of linite-width neural networks with the sequence Og,
(x, 0o), (x(, (x."))").....( 0g)], which contains all the fixed-weight weed-weight-NTKS each time step.
In this case, we hope all the elements in the sequence are well-conditioned the neural network performs well during the training phase. As result, we need to quantify the influence of removing mask on the nuclear norm of these fixed fixed- weight-NTKs.
One possible metric E+1 Ee |,,, X;; 0.) which is the average of the nuclear norm of the fxxedweiiht-NTKs computed on the parameter sequence (du. .,, )0))
We suspect that the parameter space is well explored during the training. The elements in the pa- rameter sequence (0a, .,.... 05} may be well-spread, and thus हमा Σ ,,, (X', X;; 0,) can
be viewed as an approximation of Ee | 0)1) As another way to approximate this ex- pectation, we can approximate Eg Σ 0,, (X, A: 0o.-)ll., which the saliency criterion Equation
O (x (X, 0)1 by multiple random weight configurations as
As comparison, many existing works compute the weie-weight-NKK with a single random weight configuration at initialization and are hence not a very good measure the optimization of the network with practical size. In our work, we compute the expected Exed-weight-NTT and we believe such an expected version of the fixed-weight-NTK better captures the expected behavior of the subnetworks over random weight configurations and training trajectory. Hence, aim to find subnetwork with well-conditioned expected Exed-weight-NTKK
To make the expected wixgh-weihht-NTK well-conditioned, choose to align it to the fixed-weight NTK of the dense network at initialization. Such a choice is justified for the following two reasons:
The eigenspectrum of the dense fexgh-weigtt-NTKK is good candidate. We believe that the good performance of the dense network implies that the eigenspectrum of the dense network at initialization is well-conditioned (See Section 6.5 and Appendix G. for the eigenspectrum of the dense network.).
The eigenspectrum of the dense fixed-weight-NTKK practical choice. For foresight pruning, we can only access the feigh-weigtt-NTK at initialization. Also, the foresight pruning framework mentioned in Section is is a general framework that preserves a scalar indicator of the dense network. Hence, due to the intrinsic nature of the framework, can only try to align the eigenspectrum of the sparse network to the dense counterpart at initialization, rather than some given well-conditioned spectrum.
Indeed, for practical networks, the eigenspectrun of the dense network may be changing during the training procedure. Hence, our method can only approximately align the training behavior to the dense network at the early training stage. For the later epochs, the expected well-conditioned property of the subnetwork ensures that the determined subnetworks have better optimization performance compared to other foresight pruning methods.
C ABLATION STUDIES ON THE NUMBER OF ITERATIVE STEPS
We show experiment results in Section 6.4 here. Figure shows that for smaller datasets, we can use smaller number of iterations 7 for NTK-SAP without seeing significant performance drop.
19

---

Published as a conference paper at ICLR 2023
T-1
75
90.0
T=2
74
Test Accuracy (%)
Test Accuracy (%6)
T=10
-3
T=
65.0
-2
82.5
21
80.0
70
T-5
T-10
77.5
T-100
00.00%
59 99.04%
73 80%
8.3 2222
89 30%
93 12%
85 80%
17%
98 20%
36.00%
59 -4.0%%
73,806
83.22%
89 30%
93. 12%
60%
97. 17%
96 20%
95
Sparsity (%)
Sparsity (%)
(a) ResNet-20 on CIFAR- datasct.
(b) VGG-16 on CIFAR- R-0 dataset.
50
Test. Accuracy (%%
30-
20
TH5
T-10
T=20
T-50
T-100
59.0 59.04%
73 80%%
83 22.2%%
89.30%
93 12%
95 60%
97.17 17.1%%
98.2 98.21%
36.0m
Sparsity (%)
(c) ResNet-18 18 on Tiny-ImageNer dataset.
Figure 3: Evaluate the effect of number of iterations (T) performance of NTK-SAP CIFAR-10
(ResNet-20), CIFAR- 100 (VGG-16), and Tiny-lmageNet (ResNet-18).
D DETAILED COMPUTATIONAL COST
D.1 DETAILED COMPUTATIONAL TIME COMPARISON
Table 3: Pruning time of considered methods compared to time for I epoch of training.
Dataset
CIFAR-I0
CIFAR-100
Tiny-ImageNer
ImageNet
Model
ResNet-20
VGG-16
ResNet-18
ResNet-18
ResNet-50
Training time of epoch
9.6
11s
24
15 min 42
18 min
SNIP
s
s
I s
13
34
GraSP
1
1
50
5 min 32
Synflow
12s
34
min 2
6 min 34
5 min 39
Iterative SNIP
2
46
I min 18
16 min 42
23 min 17
NTK-SAP
17s
1 min 14
2 min 14 s
17 min s
22 min 49 s
NTK-SAP-S
38
14
31 s
We include detailed comparison of the pruning time of considered methods along with the time for I epoch model training in Table 3 with the training time of epoch since it is empirically shown be Jorge et al. (2020b) that most foresight pruning methods are not worse than magnitude pruning after round of training. We also repeat such experiments in Appendix F
We are interested in comparing the pruning time of NTK-SAP de
20

---

Published as a conference paper at ICLR 2023
For ImageNet experiments, the pruning time of NTK-SAP is similar to the time for 1-2 epochs of model training. As for smaller datasets, Appendix [ shows that we can use a smaller number of pruning rounds T. Thus instead compare the rest of the methods to NTK-SAP with smaller T for smaller datasets. We name such a modified version for CIFAR-10 experiment and use T 20 for CIFAR-100 and Tiny-mmageNer. We can that NIK-SBA is able to finish pruning in 1-2 epochs of training time. Thus, we believe that the computational cost of NTK-SAP reasonable.
Specifically, we use 7 =
D.2 DETAILED FLOPS COMPARISON
In this section, we compare different foresight pruning methods in terms of FLOPs. We use the default FLOPs counter in the Synflow codebase. We approximate backward FLOPs twice as the inference/forward FLOPs. Pruning FLOPs are calculated with a simplification that the neural network dense when computing the gradients.
Pruning cost. Comparison of pruning cost for different foresight pruning methods are present in Table 4 Synflow has the lowest pruning cost since its saliency score is computed with input containing all 1s. NTK-SAP uses roughly twice the pruning cost compared to Iterative SNIP, making it the method which requires more costs compared to other foresight pruning methods. However, want to emphasize that the pruning cost of NTK-SAP can be reduced by using smaller as shown in Section 6.4 and Section
Inference cost. We further compare the inference cost of subnetworks found by different foresight pruning methods. Results are present in Table 5 and
Total pruning and training cost. Finally, compare the total pruning and training FLOPs of considered foresight pruning methods Table 8 and [O] As discussed Section 6.4 NTK-SAP generally needs more total computational costs. However, we believe that the additional computational cost is reasonable, especially considering that NTK-SAP is a data-agnostic method and can be easily applied to different datasets once the mask is found. Furthermore, we again want to emphasize the possibility of decreasing the computational cost of NTK-SA SAP by reducing T.
E EARLY PRUNING BASELINE
We repeat experiments from FORCE (de Jorge et al. 2020b) where we compare mentioned foresight pruning methods against early pruning. Precisely, train the dense neural network for 1 epoch and then prune the trained neural network using magnitude pruning. Then the weights are rewound to their initial values in the LTH work. We term such baseline as Mag-lepoch. Figure iillustrate that I epoch of training slightly improves the performance of magnitude pruning. However, NTK-SAP still outperforms such an early pruning method.
F SNIP VARIANTS
In this section, we investigate variants of SNIP, including SNIP, Iterative SNIP, and FORCE.
Effects different sparsity schedules. We first investigate the effects of the sparsity schedule used in Iterative SNIP. Specifically, we compare Iterative SNIP (Exp), which is used in the main paper, with Iterative SNIP (Linear), where we use a linear sparsity schedule. As is shown in Figure [ we find that linear schedule slightly improves the performance of Iterative SNIP smaller datasets. However, Table shows that the linear schedule does not necessarily improve the performance of Iterative SNIP larger datasets.
The performance gap between Iterative SNIP implemented in this work and what is reported in (de Jorge et al.] 2020b) may be due the different initialization methods and the number of batches used for pruning. Additionally, de Jorge et al. (2020b) only considers relatively large neural networks, including VGG-19 and ResNet-50. However, note that it is also empirically shown Frankle et al.
21

---

Published as a conference paper at ICLR 2023
Table Pruning FLOPss comparison. Results with the largest FL.PPs are in blue and results with the smallest FLOPs are in bold.
Dataset
CIFAR-10
CIFAR-100
Siny-ImaeNNet
Model
ResNet-20
VGG-16
ResNet-18
SNIP
2.48 x 10
1.88 10
8.94 x 10
GraSP
4.95 x 10"
3.77 x 10
1.79 x 10
Synflow
1.24 X 1040
9.42 x 1040
4.47 X 1040
Iterative SNIP
2.48 x 1013
1.88 1044
8.94 x 1013
NTK-SAP
4.95 x 1013
3.77 x 1044
1.79 x 10
NTK-SAP (small 7)
9.91 x 10
7.54 x 10
3.58 x 1013
Table 5: Inference FLOPSs (x 10%) comparison on CIFAR-10(ResNet-200 Results with the largest FL.PSs are blue and results with the smallest FLOPSs are in bold.
Sparsity
36.00%
73.80%
89.30%
95.60%
98.20%
SNIP
31.90
19.40
12.30
7.37
3.77
GraSP
24.20
13.50
8.65
4.95
3.20
Synflow
33.20
21.60
12.20
5.73
2.67
Iterative SNIP
31.30
16.70
7.80
3.46
2.10
NTK-SAP
31.30
18.20
10.10
5.30
2.83
Table 6: Inference FLOPs (x10') comparison on CIFAR-100(VGE) Results with the largest FLOPs are blue and results with the smallest FLOPs are in bold.
Sparsity
36.00%
73.80%
89.30%
95.60%
98.20%
SNIP
25.50
17.10
11.80
8.19
5.34
GraSP
18.30
10.30
6.15
3.75
2.48
Synflow
25.80
17.60
11.50
6.95
3.71
Iterative SNIP
25.20
15.80
9.67
5.51
2.97
NTK-SAP
26.10
17.50
11.60
7.54
4.58
Table 7: Inference FLOPS (x10²) comparison on Teng Results with the largest FLOPSs are blue and results with the smallest FLOPss are bold.
Sparsity
36.00%
73.80%
89.30%
95.60%
98.20%
SNIP
12.30
8.62
6.13
4.14
2.51
GraSP
8.14
5.29
3.59
2.45
1.65
Synflow
12.80
9.49
6.77
4.31
2.36
Iterative SNIP
12.20
7.91
4.40
2.00
0.80
NTK-SAP
12.70
9.47
6.77
4.53
2.73
22

---

Published as a conference paper at ICLR 2023
Table 8: Total pruning training FLOPs (x1044) comparison on CIFAR- (EFAR-10(ReNNet200) Results with the largest FLOPs are in blue and results with the smallest FLOPs are in bold.
Sparsity
36.00%
73.80%
89.30%
95.60%
98.20%
SNIP
7.65
4.67
2.95
1.77
0.91
GraSP
5.81
3.24
2.08
1.19
0.77
Synflow
7.98
5.19
2.93
1.38
0.64
Iterative SNIP
7.75
4.25
2.12
1.08
0.75
NTK-SAP
8.01
4.86
2.91
1.77
1.17
Table Total pruning + training FLOPs (x10 comparison on the largest FLOPs are in blue and results with the smallest FLOPs are in bold.
Results with
Sparsity
36.00%
73.80%
89.30%
95.60%
98.20%
SNIP
6.13
4.09
2.83
1.97
1.28
GraSP
4.39
2.47
1.48
0.90
0.60
Synflow
6.19
4.23
2.76
1.67
0.89
Iterative SNIP
6.24
3.99
2.51
1.51
0.90
NTK-SAP
6.65
4.58
3.17
2.19
1.48
Table 10: Total pruning + training FLOPs (x10'4) comparison on Tiny-ImageNe((ReeNee// Results with the largest FLOPs are in blue and results with the smallest FLOPs are in bold.
Sparsity
36.00%
73.80%
89.30%
95.60%
98.20%
SNIP
73.70
51.70
36.80
24.80
15.10
GraSP
48.80
31.80
21.50
14.70
9.91
Synflow
76.70
57.00
40.60
25.90
14.10
Iterative SNIP
73.90
48.40
27.30
12.90
5.71
NTK-SAP
78.20
58.60
42.40
29.00
18.10
Table 11: Comparison of SNIP variants on ImageNet dataset. Best results are in bold.
Network
ResNet-18
ResNet-50
Sparsity percentage
89.26%
95.60%
89.26%
95.60%
(Dense Baseline)
69.98
76.20
SNIP Lee et al. (2018)
57.41
45.04
60.98
40.69
Iterative SNIP (Hxp) de Jorge et al. (202bb)
52.97
37.44
52.53
36.82
Iterative SNIP (Linear)
50.29
40.98
56.54
30.55
2020b and Tanaka et 2020 that Iterative SNIP does not necessarily improve the performance of SNIP.
Unstable performance of FORCE. In addition, FORCE (de Jorge et al. 2020b), which allows pruned masks to resurrect in the process of iterative pruning, is also considered. Results are also presented in Figure 5 We observe significant performance drop of FORCE on VGG-16 (CIFAR- 100). As result, we do not report FORCE in the main paper.
"See the author feedhack file of the Synflow paper.
23

---

Published as a conference paper at ICLR 2023
ResNet-20 CIFAR-110
VGG- 16 (CIFAR- 100)
1005 Acturacy
Toxt: Anturayy
36.996
Steds
72.000
92122
57.7%
58 20.0%
7340%
$2.22%
39.20%
92.12%
95.00%
69
Sparsiy (k)
Starsty (g
ResNel-18 (Tiny ImageNel)
SNIP
Iterative SNIP
Test Aocurscy CN1
GraSP
Synflow
Magnitude
Random
Mag- Mag-lepoch
NTK (OURS)
10.00%
72.0%
$2.200
92.2%
19
97.4%
20%
Spersity og
Figure 4: Comparison of foresight pruning methods against magnitude pruning after 1 epoch of training. Results are averaged over 3 random seeds and the shaded areas denote the standard deviation of the runs.
ResNet-20 (CIFAR-10)
VGG-16 (CIFAR-100)
That Ancurncy (861
1051 ACCRUSSCY
-1
36,8596
$0,000
22,00m
80 2019
86 2006
30,000
39.000
75,005
83 2012
300
83 1296
95
07.
Sparsity R
Sparsity (%)
ResNet-18 (Iny--mmgeNNet)
SNIP
Berative SNIP (Exp)
10st Anturslyy 186
Beralive SNIP (Linear)
FORCE
36,009
23,0m
R0.2
20n9
23
99
20%6
Sparsity +
Figure 5: Comparison SNIP variants. Results are averaged over random seeds and the shaded
areas denote the standard deviation of the runs.
24

---

Published as a conference paper at ICLR 2023
Desse
Desse
SNIP
SNIP
Megmituble oleth esjetwal
10
Teeraiive SNIP
Bemaiive SNIP
GrdPp
GraS
10F
LO
Megnitade
NIXSAP (Qun)
(Guns)
10a
100
101
200
600
500
600
1000
200
400
600
500
1000
Eigenvalue index
Bigenvaliue index
(a) sparsity 36.00%
(b) sparsity = 73.80%
100
Dense
10a
Dense
SNIP
SNIP
Megnltunte of eath eiperool
10a
SNIP
Resative
1.0
SysBow
Mageltude NTXSAP (Ouis)
Magnitude
L0*
NIKSAP (Ours)
100
100
200
600
1000
600
500
1000
sparsity 89.30%
(d) sparsity 95.60%
Magnitate each eigiovales
1OP
SysBow
Magnitude
NT&SAP (Gund
10
10-1
10
Elgenvaiuee
(e) sparsity 98.20%
Figure 6: Eigenvalue distribution of the weigh- on ResNet-20 (CIFAR-10) at different
sparsity ratios. We put the index of each eigenvalue on the x-axis, and the corresponding eigenvalue magnitude is presented the y-axis.
G EIGENSPECTRUM OF PRUNED NEURAL NETWORKS
G.1 EIGENSPECTRUM AT INITIALIZATION
To visualize the effectiveness of our proposed NTK-SAP method, we conduct experiments on CIFAR-
10 dataset with ResNet-20 at sparsity ratios (36.00%, 73.80%, 89.30% 95.60% 98. 98.20% 10 We compute the weigh- with a batch size of 100. Thus the fixed-weight-NTK is of size 1000 1000.
!*ther datasets have much larger value of k. and thus the fixed-weight-NTKK is much more difficult to compute.
25

---

Published as a conference paper at ICLR 2023
10'
SNIP
10
Maquiulk ofwads sqgenvaaas
GraSP
Tamnirr SNIP
Magniadl aigunnvhbe
Syethow
Magtitude
10.
NIXSAP (Quss
1.0
1.01
GraSP
SysBlww
Maptitude
Denan
10a1
10-1
NTX SAP
200
600
500
800
1000
200
400
6.00
500
1000
Eigenvalue index
Bigenvaluee index
(a) Epoch 0
(b) Epoch 40
Magiituk each equezoalas
10P
10a
10F
10F
SNIP
SNIP Jaentive SNIP
[aaniive SNIP
GraSP
100
GrsPP
10:11
Magnitude
Syetkow
10:1
Maptitude
Synllow
10-2
NTX- (Ours)
(Ours)
600
800
1000
600
800
1000
Eigenvalue
(c) Epech 80
Epoch 120
Figure 7: Eigenvalue distribution of the fixed-weight-NTK on ResNet-20 (CIFAR-10) with different training epochs sparsity ratio 98.20%. We put the index of each eigenvalue the x-axis, and the corresponding eigenvalue magnitude is presented on the y-axis.
Figure 6 shows eigenvalue distributions of neural networks pruned by mentioned foresight pruning methods. It illustrates the effectiveness of NTK-SAP in keeping the spectrum close to the dense network.
As is shown in Figure training. On the contrary, the seedd-weigtNNTT eigenspectrum of all the pruned networks shows similar behavior and deviates from the dense However, show that, compared to other foresight pruning methods, the eigenspectrum epochs (As is shown that the majority of the eigenvalues of NTK-SAP are the closest the dense network for most of the time.). Secondly, the Hxxed-weight-TTK of NTK-SAP is well-conditioned throughout the entire training process, which aligns with our motivation.
that the spectrum of the dense network is changing throughout the
NTK-SAP aligned with the dense counterpart for the first few
G.2 EIGENSPECTRUM DURING TRAINING
We also plot eigenvalue distributions of neural networks pruned by these foresight pruning methods during training. Since the test performance of different methods does not vary too much on the CIFAR-10 dataset for wide range of sparsity ratios, only focus the most extreme sparsity, i.c 98.20%. We report relative cigenvalues by dividing each eigenvalue by the average of 10% smallest eigenvalues. Results presented in Figure
We observe that the best three methods on the CIFAR- dataset, i.e, NTK-SAP, GraSP, and Mag- nitude, have relatively low condition numbers. Furthermore, the best two methods, i.e., GraSP and NTK-SAP, have almost stable/unchanging relative eigenvalue distribution during training. That could possibly explain why GraSP and NTK-SAP perform well this sparsity ratio.
26

---

Published as a conference paper at ICLR 2023
10
Epoch=0
10"
Epoch=0
Epoch=40
Epochw40
Epoch=80 80
Epach=80
1.0
1poch-120
Bpach-120
(bllaive tragee cottoatt wach
1.00
10F
1.01
200
400
500
800
1000
200
400
600
500
1000
Eigenvalue indox
Bigenvaluue Index
(a) Iterative SNIP
(b) GraSP
Telett caage sodee mach segeaaat
Epochei
Epoch=O
Tpotheit
Spocheit0
100
Epoch-B0
Epoch=B0
1.0
101
200
1000
Eigenvalue Index
(c) Magnitude
SNIP
Baleiiv casgstiuus wach MigHrsA
10"
Epoth-B0
10*
Epoch=B0
10
120ch=120
Epoch=120
10P
10
101
107
600 Eipenvalue index
Eipetvallas
(e) Synflow
NTK-SAP (Ours)
Figure 8: Relative eigenvalue distribution of the fixed-weight-No during training ResNet- 20 (CIFAR-1O) 10) at sparsity 98.20%. We put the index each eigenvalue on the x-axis, and the corresponding relative eigenvalue magnitude is presented the y-axis.
27

---

Published as a conference paper at ICLR 2023
Spanddy 18
Spunday
Caayy ImageNeti
GraSP
Iterotive SNIP
Synflow
Magaitude
Random
NTK-SAP (Ours)
aP
am
Spandty 1g
Figure Train accuracy of NTK-SAP against other foresight pruning methods. Results are averaged over 3 random seeds and the shaded areas denote the standard deviation of the runs.
RecKet-20 (CIPAR-10)
VGG-16 (CIPAR-100)
adlord
Spurayy
Spansty
BeoNeet-18 Natt))
GraSP
Iterative SNIP
Syallow
Magnitude
Random
NTK-AP (Ours)
Speethy
Figure 10: Test accuracy of NTK-SAP against other foresight pruning methods. Results are averaged over 3 random seeds and the shaded areas denote the standard deviation of the runs.
28

---

Published as a conference paper at ICLR 2023
Table 12: Ablation study of perturbation hyper-parameter e on CIFAR-I0 (ResNet-20).. Best results are in bold.
Sparsity
36.00%
73.80%
89.30%
95.60%
98.20%
1.0
10 41
91.36 + 0.41
90.04 = 0.23
87.86 0.13
83.84 + 0.28
77.66 + 0.50
c 2.5
10
91.34 + 0.11
90.30 = 0.17
17.442.22
83.82 + 0.24
77.33 = 0.10
1.0 10-5
91.45 + 0.13
90.26 0.06
87.64 0.18
83.92 0.44
77.53 = 0.34
= 1.0 x 10
91.41 + 0.03
90.44 0.33
88.00 0.36
83.66 + 0.23
76.90 + 0.44
i Used in the experiments the main body.
Table 13: Ablation study of perturbation hyper-parameter CIFAR-100 (VGG-16). Best results are bold.
Sparsity
36.00%
73.80%
89.30%
95.60%
98.20%
1.0 x 10 10 4
74.10 + 0.37
74.12 + 0.19
73.28 - 0.32
71.85 = 0.41
69.27 + 0.39
c 2.5 x 10
74.25 + 0.16
74.09 0.20
73.20 - 0.24
71.49 = 0.08
68.97 = 0.16
c 1.0 10
74.31 +: 0.41
74.08 0.20
73.18 0.39
71.68 = 0.25
69.24 + 0.21
= 1.0 x 10-6
74.27 + 0.22
73.90 + 0.25
73.37 = 0.37
71.49 0.13
69.26 = 0.48
Used the experiments the main body.
Table 14: Ablation study of perturbation hyper-parameter on Tiny-ImageNet (ResNet-18) Best results are bold.
Sparsity
36.00%
73.80%
89.30%
95.60%
98.20%
e 1.0 x 10 41
51.89 + 0.38
52.69 + 0.14
51.90 + 0.12
49.29 + 0.15
43.92 + 0.39
e 2.5 10-5
52.10 + 0.51
52.18
0.16
51.95 0.26
49.48 = 0.38
43.63
0.19
c 1.0 x 10
51.86 + 0.16
51.97
+: 0.46
52.00 + 0.30
48.83 = 0.09
43.36 + 0.53
<= 1.0 x 10-6
51.94 + 0.45
52.31
0.19
51.32 = 0.20
49.15 = 0.38
42.94 + 0.22
Used in the experiments of the main body.
H FULL PLOTS OF THE MAIN EXPERIMENTS
We further include the complete plots of train/test accuracy of the main experiments reported in Section 6.. Results are shown in Figure g and Figure 10] NTK-SAP provides higher training accuracy than other foresight pruning methods, showing its capability to identify subnetworks that casier to train.
Generally, the test performance of all foresight pruning methods degrades with more sparsity induced. And the speed of performance degradation accelerates as the sparsity ratio increases. Additionally, for VGG-16 (CIFAR-100 and ResNet-13 18 (Tiny- ImageNe)), it can be clearly seen that the test perfor- mance of NTK-SAP first increases and then decreases, which shows the generalization improvements brought by pruning. However, it is not observed in ResNet-20 (CIFAR-10).
I ABLATION STUDY ON PERTURBATION
In this section, conduct ablation study the effects of choosing different values of perturbation
hyper-paramete parameter c. We choose from {1.0 x 10 2.5 x 10-5 1.0 x 10-5 1.0 x 10 10-6), where 1.0 10 4 is the value used in the main body. Results CIFAR-10, CIFAR-100, and Tiny- ImageNet are shown in Table 12 and 14 respectively.
The tables show that NTK-SAP is robust to the choices of perturbation hyper-parameter
29

---

Published as a conference paper at ICLR 2023
Table 15: Overview of considered foresight pruning methods.
Pruning method
Weight agnostic
Data-free
Iterative method
SNIP (Le al. 2018
GraSP Wang al.
2020
ProsPr Alizadeh et al. 2022
FORCE (de Jorge et al. 2020b
Iterative SNIP (de Jorge et al.
2020b
Synflow Tanaka al. 2020)
NTK-SAP (Ours)
J OVERVIEW OF THE CONSIDERED FORESIGHT PRUNING METHODS
Synflow and NTK-SAP are the only two data-free foresight pruning methods. In this section, summarize all the mentioned foresight pruning methods in Table [5 Synflow and NTK-SAP are the only foresight pruning methods that do not need any data. It indicates that once pruning is done, subnetworks found can be easily applied different datasets. Moreover, NTK-SAP is the first foresight pruning method that is weight agnostic.
best knowledge.
K DIFFERENCE BETWEEN NTK-SAP AND NEURAL TANGENT TRANSFER
In this section, briefly discuss the difference between NTK-SAP and Neural Tangent Transfer (NTT) (Liu & Zenke 2020). NTT also uses the theory of NTK to guide foresight pruning. Its goal is to jointly optimize and 0 so that the output and the txigh-wiigt-NTKK of the pruned model are as close as to the dense counterpart.
However, the computational cost of explicitly constructing the fixed- weight-eight-TTK is much larger than that of estimating the spectrum used in NTK-SAP. As a result, NNT may be too expensive to use for large models including ResNet-18 18, ResNet-34, and ResNet-50 III Indeed, the original NTT paper only considers small networks, including multi-layer perceptrons, LeNet, and Conv-4.
Another question can we apply the approximation used in NTK-SAP to NTT? We believe is not trivial. The idea of NTK-SAP is to remove those masks that have the least influence on the fixed-weit weight-ei spectrum. Hence, the spectrum is likely to stay roughly the same after pruning. On the contrary, NTT, to penalize the change of the feigh-weigt--NTK spectrum since two spectrums can have the exact summation but with totally different cumulative distribution functions (CDF).
pptidizatioo-baseed method, may need extra efforts to modify the loss
L COMPARISON WITH PROSPR
Before submission, has come to our attention that ProsPr (Alizadeh et al. 2022) has been published recently new competitive foresight pruning method. We tried to reproduce the results of ProsPr so that we can conduct a fair comparison between ProPr and NTK- SAK Nevertheless, we are unable to reproduce the reported results in the original ProsPr paper. We suspect that this is because use the same hyperparameters as the authors, and then asked the authors for their hyperparameters. The authors told that the hyper-pane paramm-prseeters information is not yet released and will be released later some time. We will conduct such a comparison once this information is available.
did not
11 See related discussions in issue #2 of NTT GitHub page.
Note that there are some differences hetween architectures used in ProsPr and the benchmark they used Frankle et al. 20206.
30

---

Published as a conference paper at ICLR 2023
However, want to emphasize that, ProsPr, data-dependent method (See Table 15). requires data to perform the pruming procedure. On the contrary, NTK-SAY does not require any data. Once the model is pruned, it can be applied to any datasets without additional computation.
M DISCUSSION ON THE WEIGHT-AGNOSTIC PROPERTY NTK-SAP
In Section 5.3 we have discussed the weight-agnostic property of NTK-SAP. Here we include a discussion if good pruning solution should also be weight-agnostic, least in the sense of expectation.
We think it depends the type of pruning methods. For post-hoe pruning, good pruning solution may be weight-dependent. For example, when using one good post-hoc pruning method "lottery ticket algorithm" (Frankle Carbin 2018), mask-dependent weight configuration performs better than random weight contigurations.
However, as pointed by (Frankle al. 2020b), most existing foresight pruning methods very sensitive to newly sampled initialization. One reason could be that foresight pruning methods do the images (Pellegrini & Biroli 2022) or the basin of the pruning solution (Evei et al. 2022). So in this sense, good solution for foresight pruning may be weight-agnostic. Anyhow, this argument is not decisive evidence that the best foresight pruning method shall be weight-agnostic.
not have access to enough information learn the local features/patterms
Another question may be since NTK-SAP intends to find subnetworks that perform well expectation, what happens if a really bad initialization that has zero overlaps with the binary mask? Will this network be trained well? We believe that such a network indeed should not be trained well. However, the probability of such situation is 0 since known initialization methods, e.g., Xavier or Kaiming normalization, draw initial weights from continuous random distributions. Furthermore, a worst- case initialization is allowed, dense network also encounter all-zero initialization which leads to poor results.
N
WHY NTK-SAP CAN POTENTIALLY AVOID LAYER COLLAPSE
mention that NTK-SAP uses iterative pruning potentially avoid layer collapse. We would like to give possible explanation of why NTK-SAP implicitly avoids layer collapse for the following reasons:
In Section 5.3
Firstly, Synflow (Tanaka et al. 2020) proves that synaptic saliency-based foresight pruning methods broadly follow conservation law and iterative pruning can help them avoid layer collapse. As result, NTK-SAP, as an iterative synaptic saliency-based pruning method, could also theoretically avoid layer collapse.
Secondly, Lee et al. (019b) is a re-initialization method based on SNIP aiming at improving signal propagation when layer collapse is about to happen. This work reveals that when layer collapse about to occur, the spectrum of the layer-wise input-output Jacobian is extremely poor so it breaks layer-wise dynamical isometry. Similarly, the spectrum of the NTK can also serve as such an indicator. Specifically, it can be proved that when layer collapse is about to happen, the spectrum of the NTK deteriorates as well. Here, we would like to give a simple example for a better understanding. For example, when layer collapse happens, the weight gradients of DNNs will be zeros and the fix- Eix-weight-NTK will zero matrix with all zero eigenvalues. this sense, NTK-SAP works in a way very similar to Iterative SNIP (de Jorge et al. 2020b avoid layer collapse.
31

---

Published as a conference paper at ICLR 2023
O JUSTIFICATION OF FINITE DIFFERENCE FORMULATION
In this section we justify the finite difference formulation we used Section 5.2 approximation, we have
To justify this
10.-) [I] f(':: 0. 10)1
~E (2)
Σ [e, E A0,
=c (d;
32


Reviews:
[{"review_id": "tdbpO0eB9FG", "reviewer": "Reviewer_8ZBV", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "In this paper the authors proposed a foresight pruning method for the pruning of neural networks by maintaining the spectrum of the neural tangent kernel (NTK) of the network during the pruning. The quantity that the proposed method, named NTK-SAP, tries to keep is the trace of the NTK matrix. To save computational cost, a finite difference is used to approximate the Jacobi matrix of the network. To obtain good estimate of the trace of the analytic NTK, multiple weights are sampled from the initialization distribution to compute an average of fixed-weight-NTK. A \"new-input-new-weight\" approach is used to lower computational cost. Finally, by replacing the input data by random Gaussian, the method is made data agnostic. Numerical experiments are conducted, showing that the NTK-SAP method has better performance compared with existing methods, especially when the pruning rate is large. ", "summary_of_the_review": "This paper proposes a new method to prune neural networks without training. The method can be made data-agnostic. Experiments in the paper show that the method can provide better pruned model than existing methods, especially when the pruning rate is high. The application part is interesting. It will be more interesting if the real mechanism behind the good performance of the proposed method can be further explored. ", "strength_and_weaknesses": "Strength: \n1. The authors proposed a pruning method that can be applied before training and without training data. The method shows better performance compared with existing methods in some cases.\n2. Several tricks are proposed to alleviate the computational cost of the method, such as finite difference and new-input-new-weight trick.\n\nWeaknesses:\nAs the source of intuition, whether preserving the NTK spectrum is really the reason that NTK-SAP works is not discussed. I tend to be skeptical because \n1. The NTK dynamics approximates neural network dynamics only when the network is very large. Usually used networks are not large enough to enter the kernel regime, especially for those after pruning.\n2. For practical neural networks, the NTK can change significantly during training, thus keeping the spectrum of initial NTK may not be important. \n3. Since the Jacobi is a very large matrix, approximating it using finite difference can introduce large error. Also, error may appear in the weight sampling step.\nTo address these concerns, I suggest the authors do more investigation on the NTKs and NTK dynamics of the networks before and after pruning. For example, discussion can be made on:\n1.Does the NTK spectrum change a lot over training?\n2.How close is the approximated spectrum to the real one? How large is the variance?\n3.Does the pruned network still have similar NTK spectrum with the dense network after some training?\n\nOf course, even if the NTK cannot explain why the proposed method works, the method can still be useful, and there may be more interesting mechanism behind the performance of the method. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "V6Y4QDUPOc", "reviewer": "Reviewer_w2XF", "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": "", "summary_of_the_paper": "A new pruning method for deep networks is proposed. The method is motivated as computing weight saliencies so that after pruning, the spectrum of the NTK remains as close as possible to the original NTK. In practice, a series of tricks are used to make computing saliencies more efficient. At the end of the day, saliencies are computed using eq. 10 that is claimed to approximately ensure that the spectrum of the NTK is kept close to the original one. The claimed equivalence between eq. 10 and the intuition using the NTK is made through a series of steps, which I tentatively summarize here:\n\n 1. estimate the spectrum of the infinite width NTK using an average of finite-width NTKs\n 2. summarize the spectrum of the NTK using the trace norm of the NTK or equivalently the frobenius norm of the weight-output jacobian\n3. estimate the trace norm of the jacobian by computing its product with normally distributed parameter space vectors $\\Delta \\theta$\n4. estimate the jacobian using finite difference\n5. estimate saliencies of randomly drawn input vectors from a normal distribution\n6. NINW trick where all random quantities are re-sampled at every mini-batch in order to improve efficiency\n\nThe method is tested on several datasets and architectures, demonstrating improved test accuracy compared to other benchmarks. A sensitivity analysis to hyperparameters is provided.", "summary_of_the_review": "A sound new method for computing saliency scores for pruning deep nets but I am not entirely buying the link between the method and the proposed intuition using the NTK framework.", "strength_and_weaknesses": "It looks to me that you could have written the same paper with no mention of the NTK since eq. 10 suffices by itself to motivate your method: saliencies are computed so that on average, the pruned function is similar to the original one, as measured by the l2 norm, even after training in directions $\\Delta \\theta$.\n\nIf you posit that the reason for your method to give good empirical results is linked to the theory around NTK, I think that the series of steps that you follow to link your saliency scores (eq. 10) to the intuition using the NTK should be carefully checked, either:\n - theoretically by providing closed-form expressions for the variance of the estimator on simpler models\n - empirically on models for which you are able to actually compute NTKs\n\nThe fact that your method is weight-agnostic is also in my opinion not explored as much as it should: did you check which parameters are actually pruned, corresponding to what layers? Given the symmetry invariance of deep nets if e.g. you swap neurons A and B of the same layer (and swap accordingly the corresponding parameters of the previous and next layers), why should neuron A be pruned rather than neuron B ? At high sparsity ratio, how do you ensure that not all parameters of a layer are pruned?", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SzRSk2CMwhT", "reviewer": "Reviewer_B3ZS", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper proposed a new foresight pruning metric, which prunes the connections that have the least influence on the trace norm of the NTK. The motivation is to align the training dynamics of the sparse and dense model by maintaining the spectrum of NTK. To alleviate the burden of estimating the expectation of the fixed-weight-NTKs, the authors propose to sample a weight configuration for each mini-batch and compute the averages of their fixed-weight-NTKs. ", "summary_of_the_review": "NTK-SAP explores an important pruning topic, foresight pruning. The method is novel by considering preserving the spectrum of NTK. The experiment results demonstrate its effectiveness over existing baselines, though at the expense of some computational efficiency.", "strength_and_weaknesses": "Strength:\n\n1. Foresight pruning is an important research direction, as well as the explorations on weight-agnostic and data-agnostic pruning. \n2. NTK-SAP is a simple and novel pruning metric. Choosing the average value of all eigenvalues of NTK as saliency metric should be able to capture some valid spectrum information while providing computational benefits. \n3. The experiments and analysis show NTK-SAP can preserve the NTK spectrum and leads to better accuracy.\n\nWeakness:\n\n1. Since the approximation requires two forward passes, the method still induces larger computational cost.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8kPD1A88u9", "reviewer": "Reviewer_2M9f", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "The authors consider the problem of improving the training efficiency of neural networks by pruning them at initialization. Unlike prior literature work, which often considers weight-dependent metrics to find \"dead units\" and remove them, the authors provide a spectrum-aware metric for identifying removable units. In particular, the critical insight of this work relies on how well the NTK approximates the training dynamics of neural networks beyond the infinitely-wide setting. The authors show that by removing connections that least impact the NTK spectrum during training, they achieve competitive (and often better) performance when compared to solid baselines (e.g., SNIP). To provide a computationally efficient pruning algorithm, the authors identify some challenges in estimating the NTK spectrum at convergence and show that when averaged appropriately, multiple random initializations of the NN provide a good approximation for the spectrum. ", "summary_of_the_review": "The authors consider alternative metrics for searching connections for pruning while maintaining training performance and improving learning efficiency. Unlike weight-dependent metrics, the authors consider the NTK-spectrum as a proxy for evaluating the 'goodness' of connections and propose removing connections that don't perturb the NTK-spectrum post-pruning. Finally, the authors assess some computational bottlenecks in the efficient computation of the spectrum and offer well-motivated approximations that significantly reduce the overhead. With extensive experiments on CIFAR10/100, Tiny-Imagenet, and across model families (ResNet/VGG), NTK-SAP performs quite well compared to alternative approaches in the literature. ", "strength_and_weaknesses": "### **Strengths**\n+ The problem is well-motivated; pruning neural networks by aligning the dynamics could be a good diagnostic tool for dynamics-aware pruning (and potentially improve the generalization of the sparse models).\n+ Authors provide exhaustive comparisons to strong baselines, outperforming most approaches across multiple datasets. \n\n\n### **Weaknesses**\n- The iterative pruning algorithm poses significant computational overhead as compared to baselines. Therefore, comparing the runtime/time complexity of NTK-SAP with baselines would help evaluate the approaches head-to-head.\n- The plots don't present a linear x-axis for the sparsity ratios. Is it logarithmic along the x-axis? Discussion on the choice of the evaluation checkpoints and quality of performance degradation with a reduction in parameters would be helpful.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster