How Sparse Can We Prune A Deep Network: A Fundamental Limit Perspective
Authors: Qiaozhe Zhang
Ruijie ZHANG
Jun Sun
Yingzhuang Liu
Venue: NeurIPS 2024 poster (2024)
Keywords: Network Pruning
Fundamental Limit
Convex Geometry
Primary area: learning_theory

Abstract: Network pruning is a commonly used measure to alleviate the storage and computational burden of deep neural networks. However, the fundamental limit of network pruning is still lacking. To close the gap, in this work we'll take a first-principles approach, i.e. we'll directly impose the sparsity constraint on the loss function and leverage the framework of statistical dimension in convex geometry, thus enabling us to characterize the sharp phase transition point, which can be regarded as  the fundamental limit of the pruning ratio. Through this  limit, we're able to identify two key factors that determine the pruning ratio limit, namely, weight magnitude and network sharpness. Generally speaking, the flatter the loss landscape or the smaller the weight magnitude, the smaller pruning ratio. Moreover, we provide efficient countermeasures to address the challenges in the computation of the pruning limit, which mainly involves the accurate spectrum estimation of a large-scale and non-positive Hessian matrix. Moreover, through the lens of the pruning ratio threshold,  we can also provide rigorous interpretations on several heuristics in existing pruning algorithms. Extensive experiments are performed which demonstrate that our theoretical pruning ratio threshold coincides very well with the experiments. All codes are available at: https://github.com/QiaozheZhang/Global-One-shot-Pruning

How Sparse Can We Prune A Deep Network: A Fundamental Limit Perspective
Qiaozhe Zhang, Ruijie Zhang, Jun Sun, Yingzhuang Liu
School of EIC, Huazhong University of Science and Technology qiaozhezhangChust edu. cn, rui jiezhangguucsbbb.... edu juns0hust edu. cn, liuyzāhust. edu.cn cn
Abstract
Network pruning is commonly used measure to alleviate the storage and com- putational burden of deep neural networks. However, fundamental limit of network pruning is still lacking. To close the gap, in this work we 'lll take first-principles approach, i.c. we'll directly impose the sparsity constraint on the loss function and leverage the framework of statistical dimension in con- vex geometry, thus enabling us to characterize the sharp phase transition point, which be regarded the fundamental limit of the pruning ratio. Through this limit, we're able to identify two key factors that determine the pruning ra- tio limit, namely, weight magnitude and network sharpness. Generally speaking, the flatter the loss landscape or the smaller the weight magnitude, the smaller pruning ratio. Moreover, we provide efficient countermeasures address the challenges in the computation of the pruning limit, which mainly involves the accurate spectrum estimation of large-scale and non-positive Hessian matrix. Morcover, through the lens of the pruning ratio threshold, we can also provide rigorous interpretations on several heuristics in existing pruning algorithms, Ex- tensive experiments are performed which demonstrate that our theoretical pruning ratio threshold coincides very well with the experiments. All codes are available https: gi thub. com Qww.oiaeeaang/llllloa One- shot Pruntt-ruiig
Introduction
Deep neural networks (DNNs) have achieved huge success in the past decade, which relies heavily on the overparametrization, i.e. the number of parameters normally several order of magnitudes more than the number of data samples. Though being key enabler for the striking performance of DNN, overparametrization poses huge burden for computation and storage in practice. It is therefore tempting to ask: I) Can we prune the DNN by large ratio without performance sacrifice? 2) What's s the fundamental limit of network pruning?
For the first question, a key approach is to perform network pruning, which was first introduced by [21]. Network pruning can substantially decrease the number of parameters, thus alleviating the computational and storage burden. The basic idea of network pruning is simple, i.e., to devise metrics to evaluate the significance of parameters and remove the insignificant ones. Various pruning
algorithms have been proposed so far: 21 12
13
23
35 36 24; 22 15) and [13].
In contrast, understanding on the second question, i.c., the fundamental limit of network pruning, far less. Some relevant works are: [19] proposed to characterize the degrees of freedom
DNN by exploiting the framework of Gaussian width. (25 directly applied the above degrees of freedom result to the pruning problem, in the main purpose of unveiling the mechanisms behind the
Jun Sun (juns @ hust..du.co is the corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Lottery Thicket Hypothesis (LTH) [6]. The lower bound of pruning ratio is briefly mentioned in 221, unfortunately, their predicted lower bound does not match the actual value well, in some cases even with big gap. And there is no discussion on the upper bound in that paper.
Despite the above progress, systematic of the study on the fundamental limit of network pruning is still lacking. To close this gap, we'll take a first principles approach to address this problem and exploit the powerful framework of the high-dimensional convex geometry. Essentially, we impose the sparsity constraint directly on the loss function, thus we can reduce the pruming limit problem to a set intersection problem, then we leverage the powerful approximate kinematics formula MI] in convex geometry, which provides very sharp phase transition point to easily address the set intersection problem, thus enabling a very tight characterization of the limit of network pruning. Intuitively speaking, the limit of pruning is determined by the dimension of the loss sublevel set (whose definition in Sec. 2 of the network, the higher the latter, the smaller the former.
The key contributions of this paper can be summarized as follows:
We fully characterize the limit of network pruning, which coincides perfectly with the ex- periments. Moreover, this limit conveys two valuable messages: 1) The smaller the network sharpness (defined as the trace of the Hessian matrix), the more we can prune the network; 2) The smaller the weight magnitude, the more we can prune the network.
We provide an efficient spectrum estimation algorithm for large-scale Hessian matrices when computing the Gaussian width of a high-dimensional non-conver set.
We present intuitive explanations on many heuristics utilized in existing pruning algorithms through the lens of our pruning ratio limit, which include: (a). Why gradually changing the pruning ratio during iterative pruning is preferred. (b). Why employing le regularization
makes significant performance difference in Rare Gems algorithm (28). (c).Why magnitude pruning might be the optimal pruning strategy.
1.1 Related Work
Pruning Methods: Unstructured pruning involves removing unimportant weights without adhering to some structural constraints. Typical methods in this class include: [3] presented the train- main-prune- retrain method, which reduces the storage and computation of neural networks by learning only the significant connections. [37| 38) employed the energy consumption of each layer as the metric to determine the pruning order and developed latency tables to identify the layers that should be pruned.
III proposed dynamic network surgery, which reduced network complexity significantly by pruning connections in real time. (6) proposed pruning by iteratively removing part of the small weights, and based on Frankle's 's iterative pruning (6. (28) introduced 22-norm to constrain the magnitude of unimportant parameters during iterative training. To the best of our knowledge, there is still no systematic study on the fundamental limit of pruning from the theoretical perspective.
Understanding Neural Networks through Convex Geometry: Convex Geometry is a powerful tool for characterizing the performance limit of high-dimensional statistical inference [5] and learning problems. For statistical inference, [5] pioneered employ the convex geometry study the recovery threshold of the classical linear inverse problem. For statistical learning, 19 studied the training dimension threshold of the network from a geometric point of view by utilizing the Gordon's 's Escape theorem 10), which shows that the network can be trained with less degrees of freedom (DoF) than the network size in the affine subspace. The most relevant work ours is 25 which studied the Lottery Tickets Hypothesis (LTH))6) by applying the above DoF results in 19 to demonstrate that iteration is needed in LTH and that pruning is impacted by the eigenvalues of the loss landscape. The main difference between (25] and ours are as follows: 1) The lower bound of the pruning ratio is only briefly mentioned in 25 and their predicted lower bound does not match the actual value well, in some cases even with quite big gap (the main reason lies in the spectrum estimation error in their algorithm). 2) The core results in (25) are based on Gordon's Escape theorem [10] which can only provide the lower bound (necessary condition). 3) Rigorous analysis as well as the computational issues regarding the pruning limit are lacking in 25 contrast, all the above issues are addressed in this paper.

---

2 Problem Setup & Key Notions
To explore the fundamental limit of network pruning, we'll take the first principles approach. In specific, we directly impose the sparsity constraint on the original loss function, thus the feasibility of pruning be reduced to determining whether two sets, i.e. the sublevel (determined by the Hessian matrix of the loss function) and the k-sparse set intersects. Through this framework, we're able to leverage tools in high- high-dimensional convex geometry, such as statistical dimension (Л].
Gaussian width [34] and Approximate Kinematics Formula M.
Model Setup. Let ý s(w, x) be deep neural network with weights E RD and inputs E RR For a given training data set {xn: Yn and a loss function E, the empirical loss landscape defined as [(w)= = Em=1 ((f(w, vn).
Pruning Objective. In essence, network pruning can be formulated the following optimization problem:
min |wllo s.t. ((w) S [(w") +e
(1)
where w is the pruned weight and w is the original one.
Sparse Network. Given dense network with weights w*, we denote its sparse counterpart k-sparse network, whose weight is given by: w = w" @ m, where @ is element-wiss multiplication and |||lo k.
Loss Sublevel Sets. A loss sublevel set of a network is the set of all weights w that achieve the loss up to L(w")++ +
S(c) == (w E RRP L(w) S L(w") + e).
Feasible k-Sparse Pruning. We define the pruning ratio k/ D and call sparse weight w as feasible k-sparse pruning it satisfies:
S(c) (w*) + 0,
Below some key notions and results from high dimensional convex geometry, which of critical importance to our work.
Definition 2.1 (Convex Cone & Conic Hull) A convex cone C E TR. is a corvex set that satisfy: Σ, 1: E C for all ni > and T; The convex conic hull of a set S is defined as:
C(S) = Σ n.W:W 1 > 0, w, S}
Definition 2.2 (Gaussian Width The gaussian width of subset S E R.D is given by:
w( (S)
E sup (g. x g N(0,
2
x.yES
Gaussian width is useful to characterize the complexity of a convex body. On the other hand, statistical dimension is an important metric to characterize the complexity of convex cones. Intuitively speaking, the bigger the cone, the larger the statistical dimension, as illustrated in Fig. [b).
Definition 2.3 (Statistical Dimension ( The statistical dimension 8(C) of convex cone C is:
6(C) == (g)
(6)
where Te is the Euclidean metric projector onto C and (10, is standard normal vector.
To characterize the sufficient and necessary condition of the set intersection, we'll resort to the powerful Approximate Kinematics Formula [1. which basically says that for convex cones (or generally, sets), if the sum of their statistical dimension exceeds the ambient dimension, these two cones would intersect with probability 1, otherwise they would intersect with probability O.
Theorem 2.4 (Approximate Kinematies Formula, Theorem 7.1 of (1) Let be convex conic hull of sublevel set S(e) in RD,, and draw a random orthogonal basis Q E RDDD For k k-dimensional subspace Sk, holds that:
8(C) + k $ D P QS₁ = =0 m2 8(C) + P(Cn QS: 0] m0
3

---

sublevei
Tel
samil come
sub
Projerisa
sphete
(b)
(
Figure 1:
Illustration of a convex conic hull and the statistical dimension. Panel (c): Effect of projection distance projection size and intersection probability.
Panel (a, b):
Bounds of Pruning Ratio
3.1 Lower Bound of Pruning Ratio
In this section, we aim to characterize the lower bound pruning ratio, i.e. when the pruning ratio falls below some threshold, it's impossible to retain the generalization performance. To establish this impossibility result, we'll leverage the Approximate Kinematics Formula as detailed in Theorem 2.4
3.1.1 Network Pruning As Set Intersection
To demonstrate that when k is smaller than given threshold, it is impossible find performance- preserving k-sparse network induced by the dense network, we need to prove that the loss sublevel set has intersection with any k-sparse set resulting from the dense weight, i.e. S(e) n {w*] 0.
To that end, suffices to prove its translated version, namely Sw* (e) {0) 0, where Sw (c) (())) To prove the latter, we'll further prove its strengthened version, i.e. the
{w w convex conic hull of S (e) and random orthogonal rotation of the subspace S(w*), which is comprised of all vectors that share the same zero-pattern as w (including the point O), has no intersection. Namely, we'll prove that
C(S (e)) QS(w*) = 0,
where Q denotes the Haar-measures orthogonal rotation.
To prove Eq we can easily invoke the necessary condition of the Approximate Kinematics Formula (Theorem 2.4.. order calculate the involved statistical dimension therein, we choose calculate
the corresponding Gaussian width the proxy by taking advantage of the following theorem.
Theorem 3.1 (Gaussian Width vs. Statistical Dimension, Proposition 10.2 of (1] Given a unit sphere gD-1 = {x E TR ||||| 1), let C be conver cone in R.D then:
(C n D-12 8(C) I w(CnsD-1ja +1
(8)
To calculate the Gaussian width of C(S (e)). we need project the sublevel set Sw (e) onto the surface of the unit sphere centered at origin. which is defined as
p(S (e)) = (xx w / - w*1l2 x Sw (t)},
and illustrated in Fig. c).. It is easy to see that as the distance x|x- w ||2 increases, the projected Gaussian width will decrease, as a result the statistical dimension of the set will also decrease, thus increasing the difficulty of its intersecting with a given subspace.
Theorem 3.2 (Lower Bound of Pruning Ratio) Let C be convex conic hull of sublevel set Swi (c) in RD w doesn't constitute a feasible k-sparse pruning with probability 1. if the fol- lowing holds:
w(p(S (c)) +
(10)
This theorem tells us that when the dimension of the sub-network is lower than ky, w(p(Sw> (e)))2 the subspace will not intersect with Sw (e), i.c. no feasible k-sparse pruning be

---

found. Therefore, the lower bound of the pruning ratio of the network can be expressed as:
PI. = - w(((S (c)))² = = ( (c)))²
(11)
D
D
It's worth mentioning that this lower bound has been provided in 25 by utilizing the Gordon's Escape Theorem [0]. The main difference between our work and [10] lies in that Gordon's 's Escape Theorem is not strong enough to provide the upper bound (sufficient condition) the pruning ratio, while the Approximate Kinematic Formula we employ does.
Reformulation of the Sublevel Set. Consider well-trained deep neural network model with weights w" and loss function L(w), where w lies in a small neighborhood of w". By performing a Taylor expansion of ((w) at w", using the fact that the first derivative is equal to O and ignoring the higher order terms, the loss sublevel set SE)) can be reformulated as:
S(c) (w f E ER: w Hw cc
(12)
where w = w w and H denote the Hessian matrix of L(w) w.r.t w. Due to the positive- definiteness of H, S(e) corresponds to ellipsoid. The related proofs can be found in Appendix D.I
3.1.2 Gaussain Width of the Ellipsoid
We leverage tools high-dimensional probability, especially the concentration of measure, which enables us to present rather precise expression for the Gaussian width of high-dimensional ellipsoid.
Lemma 3.3 For an ellipsoid S(c) defined by : S(c) == fw RD, 1 ! S c) where
H e DxD is a positive definite matrix, its Gaussian width is given by:
w(S(c)) ~0 (2TTH 2 1
r -//
(13)
where r. X is the radius of ellipsoidal body and X is the i-th eigenvalue of H.
The proof of Lemma 3.3 is in Appendix
The Gaussian width of an ellipsoid has been provided 22)1/2), in contrast we sharpen the estimation of Gaussian width point (ED r2 1/2 For the settings which involve projection, the squared radius 73 should be modified to I
D.I
in 19 as in the interval [[ 2 1/2
19 Therefore, the Gaussian width of projected S(e)
defined in Eq. 12 equals:
rf
(pp(S)((c))
1/2
(14)
w w 11
3.1.3 Computable Lower Bound of Pruning Ratio
Combining 11 and Eq. 14). we obtain the following computable lower bound of the pruning ratio:
Corollary 3.4 Given well-trained deep neural network with trained weight w E R and loss function L(w), C(w).for a k-sparse pruned weight w the lower bound of pruning ratio of model is:
D
r
PL P1=1-
(15)
W
w
1
+
where Ti /2e/Nr and > is the eigenvalue of the Hessian matrix of L(w) w.r.t.
5

---

3.1.4 Pruning Ratio vs Magnitude & Sharpness
It is evident from Eq. (15) that for a given trained network (whose spectrum of the Hessian matrix is fixed), to minimize the lower bound of the pruning ratio, we just need minimize ||w* w w i.e. the sum of magnitudes of the pruned parameters. Therefore, the commonly-used magnitude-basee pruning algorithms get justified. Moreover, it also inspires us to employ the one-shot magnitude pruning algorithm detailed in Section[4] whose performance proves to be better than other existing algorithms, to the best of our knowledge.
Besides the above-discussed magnitude of the pruned sub-vector, we also identify another important factor that determines the pruning ratio, i.c. the network sharpness. which describes the sharpness of the loss landscape around the minima, as defined by the trace of the Hessian matrix, namely Tr (H) ([26) and 9 network flatness is the opposite of network sharpness; as sharpness increases, flatness decreases, and vice versa.).
Lemma 3.5 (Pruning Ratio vs. Sharpness) Given a well-trained neural network f((), where w the parameters. The lower bound of the pruning ratio and the sharpness obeys:
2eD
PL S
(16)
w* (1)
+ 2ED DED
where H is the hessian matrix of the loss function w.r.f. w.
Lemma 3.5 is obtained by utilizing the Cauchy-Schwarz Inequality, whose proof can be found in Appendix F It can seen from Lemma 333 that the lower bound of the network pruning ratio heavily dependent on the sharpness of the network, i.c. flatter networks imply more sparsity. This can be a valuable guideline for both training and pruning the networks. Intuitively, a flatter loss landscape is less sensitive to weight perturbations, indicating greater tolerance to weight removal.
3.2 Upper Bound of Pruning Ratio
In order establish the upper bound of the pruning ratio, we need to prove that there exists an k-sparse weight vector intersects with the loss sub-level set.
For a given trained weight w we split it into two parts, i.e. the unpruned subvector, w [wi, w wi] and the pruned one w = [Wi+1 wh+ set can be reformulated as:
wi). By fixing w the loss sublevel
S(w e) = (w's E EDD- L([w', w' S L(w") +e}
(17)
In order to prove the existence of a k-sparse weight vector w we just need to show that the all-zero vector is in S(w", e). To that end, we'll take advantage of the sufficient condition of the approximate kinematies formula (Theorem (24) show that it suffices render the statistical dimension of the projected cone of S(w', .e) being full, i.e. D - k. Thus we can obtain the upper bound of the number of unpruned parameters, i.e. k.
Specifically, by invoking the sufficient part of Theorem 2.4 the upper bound of the pruning ratio by given pruning strategy is as follows:
Theorem 3.6 (Upper Bound of Pruning Ratio) Given a sublevel set S(w', ,e) in D- To ensure that the all-zero vector E TR. D-k contained in S(w', .)), it suffices that:
w(p(S(w', ee)) 2 D - k.
The Gaussian width of projected S(w', .e) can be easily obtained by employing Lemma 3.3 i.e.
w(p(S(w', ()) D- [ -w--=**++7
where 7 / 2c /Ne X; is the eigenvalue of the hessian
matrix of C([w', w }) w.n.t to and the fact that || w ||| ||w is used. Correspondingly, the upper bound the pruning ratio can be expressed as
Py w(p(S(w' ,e)))²
D
??
(18)
w
w
2 +

---

3.3 Fundamental Limit of Pruning Ratios
As demonstrated above, the pruning ratio can be bounded as follows:
1 D
+ s 1 E w 12
(19)
is easy to notice that the upper bound and lower bound are of nearly identical form. In fact, as we' Ill claborate in the following, they are also of quite close value, which implies that a sharp characterization the fundamental limit of pruning ratio. Meanwhile, it is worthwhile noting that the pruning limit depends the magnitude of the final weights, which might be significantly impacted by the weight initialization. Therefore, we still need to explore whether the magnitude of final weights is dependent on the initialization values. In the appendix, we'll el'll demonstrate that once the data, network architecture and training method are fixed, the distribution of trained network weights remains nearly insensitive to the initializations, thus yielding affirmative answer about the above question.
able to obtain
4 Achievable Scheme & Computational Issues
Thus far we have established the lower bound and upper bound of the pruning ratio by leveraging the Approximate Kinematic Formula in convex geometry []] To proceed, we will demonstrate that devise achievable pruning algorithm whose
obtained bounds are tight in the sense that corresponding upper bound is quite close to the lowest possible value of the lower bound. As argued in Corollary 3.4 the magnitude pruning, which removes all the smallest D k weights, will result in the lowest pruning ratio lower bound. Inspired by this result, we'll 'Ill focus on the magnitude pruning methods in order approach the lower bound in the sequel.
For the lower bound part, we need to address several challenges regarding the computation of the Gaussian width of a -ithnnimeniin deformed ellipsoid, which involves tackling the non- positiveness of the Hessian matrix as well as the spectrum estimation of a large-scale Hessian matrix.
For the upper bound part, we'll focus on a relaxed version of Eq. [ by introducing the I regularization term, for the sake of computational complexity. Then we'll Il employ the one-shot magnitude pruning to compress the network.
4.1 Computational Challenges Countermeasures
To compute the lower bound of the pruning ratio, we need to address the following two challenges:
Gaussian Width of the Deformed Ellipsoid. In practice, it is usually hard for the network to converge to the exact minima, thus leading to a non-positive definite Hessian matrix. In other words, the ideal ellipsoid gets deformed due the existence of negative eigenvalues. Determining the Gaussian width of the deformed ellipsoid is a challenging task. To address this prohlem, we resort to convexifying (i.e. taking the convex hull of) the deformed ellipsoid and then calculating the Gaussian width of the latter instead, by proving that the convexifying procedure has no impact on the Gaussian width. (The proof is presented in Appendix D.2).
Improved Spectrum Estimation. Neural networks often exhibit a quite significant number of zero-valued or vanishingly small eigenvalues in their Hessian matrices. It's hard for the spectrum estimation algorithm SLQ (Stochastic Lanczos Quadrature) proposed by [39] to obtain accurate estimation of these small cigenvalues. To address this issue, propose to enhance the existing large-scale spectrum estimation algorithms by a key modification, i,e, to estimate the number of these exceptionally small eigenvalues by employing the Hessian matrix sampling. See Algorithm T for the details of the improved spectrum Estimation algorithm. A comprehensive description of the algorithm and its experimental results are presented in Appendix C
4.2 Achievable Scheme: 4 Regularization & One-shot Magnitude Pruning
Inspired by the lower bound as well as upper bound of the pruning ratio, in which the magnitude of pruning parameters plays key role, it's sensible to focus the magnitude-based pruning methods.
7

---

Algorithm Improved SLQ (Stochastic Lanczos Quadrature) Spectrum Estimation Algorithm
Input: Hermitian matrix A of size n, Lanczos iterations m, ESD computation iterations 7, gaussian kernel f and variance o², sampling nums and row I norm threshold c.
Output: The spectral distribution of matrix A
i -2,..., :o.... /o
1). Get the tridiagonal matrix T of size x through Lanczos algorithm 18]
2). Compute m eigenpairs (A Uk
(0) from T;
(6) (8) 3). (ttt)) T f(A it, O).,, where (t) (4)
T (ok [1])² is the first component of 1/2
(8)
end for
4). Random sample rows A, of matrix and calculate every 4 norm ||il| by take i [].
5). Compute the number 2 of || ||A, which satisfy || ||A,|| S
6). Compute the integration of | Σ @ (f), termed as c, Φ(() | E/= 02(1) + _ 5(1-30)
Return: o(t)
On the other hand, to find exact solutions of original problem for the best pruning in Eq. T is obviously very hard due to the existence of to norm. To make it feasible, it's natural to perform convex relaxation of lo norm, namely, by employing 4 regularization instead. Aside from the computational advantage of this relaxation, it is worthy noting that [ regularization provides two extra benefits: 1) A large portion of eigenvalues quite small value, which renders the calculation of the pruning limit more accurately and fast. 2) A large portion of trained weights are of quite small value, thus making the lower bound and upper bound very close. Detailed statistics about the eigenvalues and magnitudes can be found in Figure 6
the trained Hessian matrix are zero-valued or of
Specifically, by utilizing the Lagrange formulation and convex relaxation of norm, the pruning objective in Eq T can be reformulated as:
min [(w) + A||w|11
(20)
After training with this relaxed objective, the network weights will be pruned based on magnitudes
time, rather than in iterative way in [13 6 28 The performance of the above described pruning scheme (termed as "I regularized one-shot magnitude pruming" and abbreviated as "LOMP") can be found in Table 10 in Appendix. The above stated "zero-dominating" property due li regularization gets supported in Figure bb), where it can be seen that the majority of weights are indeed extremely small.
402000
500000
IC2 (igg3)
Und sptiere
-10
1-00 Parmi Value 1og101
-20
Incke (2)
Figure 2: Effect of extremely small projection distance on projection size and intersection probability and statistics of ResNet50 on Tinylmagenet. Statistics regarding all experiments can be found in Appendix
The above "zero-domination" property turns out to critical value for our proposed pruning scheme to nearly achieve the limit (lower bound) of the pruning ratio. Fig. ( illustrates the curve ||w?||, i.e. the lı norm of the D - & smallest weights, w.r.t. k/D. The vertical line therein represents PL, the lower bound of the pruning ratio predicted in Section 3.I When DPL, the curve and the line will intersect as shown in Figure cc). Mathematically, the upper bound for the pruning ratio can be approximated as follows:
k
D
k
pu pu=
D
Pr.
(21)

---

It can be seen from the above demonstration that the upper bound corresponding to our proposed pruning scheme almost coincides with the minimal lower bound! other words, we have established the fundamental limit of the pruning ratio. To provide further validation of the above claim, we performed the experiments five times across eight tasks and reported the differences between the upper bound and lower bound, denoted as A, in Table 9
Table The Difference Between Lower Bound and Upper Bound of Pruning Ratio.
CIFARIO
FC5
FC12
Alexnet
VGG16
A(%)
0.17:10.05
0.05+00.3
0.02=0001
0.01
ResNet
I8 on CIFARI00
50 on CIFARI00
18 on Tinylmagenet
50 on TinyImagenet
A(%)
0.12+0.05
0.11=0.09
0.09=0.01
0.27=0022
Experiments
In this section, we validate our pruning method well as the thcoretical limit of the pruning ratio by experiments.
Tasks. We evaluate the pruning ratio threshold on: Full-Commett5((CS))
AlexNet (17) and VGG16 (27] on CIFARIO [16], ResNet18 and ResNet50 (14] on CIFARIO 100 and TinylmageNet [20]. We employ the regularization during training, and execute one-shot magnitude-basee based pruning and assess its performance with various sparsity ratios, in terms of the metrics of accuracy and loss. Detailed descriptions of datasets, networks, hyper-parameters, and eigenspectrum adjustment can be found in Section of the Appendix. Moreover, the performance comparison between | Iy-regularization found in Table 10 in Appendix.
magnitude pruning and other pruning methods can be
5.1 Validation of Pruning Lower Bound
After training with the I regularization, we compute the eigenvalues and present the theoretical limit of pruning ratio. By pruning the trained network to various sparsity levels, we depict in Figure 3 both the line of theoretical lower bound and the the figures we can see that our theoretical result matches the numerical pruning ratio quite well.
curve for the above-listed tasks. From
Test Loss
Test Accuracy
PESICIFAR1O
FCARCIFANIO
Allas NeOCCALL
2.0
VSGLSICFALLL
1.0
3.0
1.5
Acc
1.0
0.5
100
70
40
100
40
10
302 10
102
BuzNetLE PARLOC
PN5N FARLDO
Ra677015 Ninttmageett
1.5
1.0
Acc
0.5
0.5
0.5
0.0
1..0
0.0
100
70
40
10
100
73
40
10
6
300
10
103
70
40
10
Pruning Ratio(%)
Pruning Racio
Pruning Ratio(%)
Pruning Ratio(%)
Figure 3: The impact of sparsity loss and test accuracy are obtained the test dataset, and mark the theoretical pruning ratio limit with vertical lines. The loss values have been normalized and translated.
5.2 Prediction Performance
We present a more detailed comparison between our theoretical limit of pruning ratio, and the actual values by experiments in Table which shows nearly perfect agreement between them. The difference between the theoretical value and the actual value is donated as A.
6 Interpretation of Pruning Heuristics
Equipped with the fundamental limit of network pruning, we're now able to provide rigorous interpretations of several heuristies employed by existing pruning algorithms.

---

Table 2: Comparison between Theoretical and Actual Values of Pruning Ratio
Dataset
Model
Theo, Value( (%)
Actual Value(%)
A(%)
FCS
2.1=0.25
1.7+0.12
-0.40++0.35
FC12
10000.00
0.810.06
-0.24:10.33
CIFARIO
AlexNet
0.9=0.00
0.840.08
-0.14::0.88
VGG16
0.8=0.06
0.8+0.08
0.04=0.08
ResNer18
1.5-0.05
2.0+0..13
0.54++0.15
CIFARI00
ResNet50
1.950.5
2.1110.16
0.28
ResNer18
3,9-0.82
4.3+0.38
0.46+0.71
Tiny Imagenet
ResNet50
2.2-0.24
0.33
0.36
Magnitude Pruring
Theory Prediction
Sparse Network
0.5
150
250
55
150
151
AN Rania Pruning Patton
0.0
50
0.-
0.0
03
100
150
200
50
105 150 203
50
160
150 201
50
100
150 260
twithout 12)
R (with (2)
R
(without 12)
R (with 12]
Figure 4: Top Row: From left to right, the number of iterations increases, it leads to increase in the theoretical pruning ratio threshold. The horizontal line represents the last pruning ratio. Bottom Row: The comparison of the pruning ratio threshold between using and not using lz-regularization. Sparse networks are obtained by magnitude-bas based pruning with fixed pruning ratios. The two plots on the left and the two plots on the right correspond to different fixed pruning ratios. Here, R = -|ww" -----" w2112, which is the projection distance.
Pruning ratio adjustment is needed in IMP. For the IMP (Iterative Magnitude Pruning) algorithm 77 we determine the pruning ratio thresholds for various stages through calculations. as depicted in top row of Figure 4 noteworthy that as the pruning depth gradually increases, the theoretical pruning ratio threshold also increases. Therefore, it is appropriate to prune smaller proportions of weights gradually during iterative pruning, Both 44] and (28) have employed pruning rate adjustment, which gradually prunes smaller proportions of the weights with the iteration of the algorithm.
drregularizatton enhances the performance of Rare Gems. For the Rare Gems algorithm 228 is shown that le regularization makes significant difference in terms of the final performance, as shown in the bottom row of Figure The main reason behind this phenomenon is: when Ie-reuularization is applied, the pruning ratio tends to be larger than the theoretical limit, however, the absence of l rergulaaizzatinn would result excessive pruning, which can be regarded as wrong pruning.
Conclusion
In this paper we explore the fundamental limit of pruning ratio of deep networks by taking the first principles approach and leveraging the framework of convex geometry. Specifically, we reduce the pruning limit problem to the sets intersection problem, and by taking advantage of the powerful Approximate Kinematic Formula, we are able to sharply characterize the fundamental limit of the network pruning ratio. This fundamental limit conveys key message as follows: the network pruning limit is mainly determined by the weight magnitude and the network sharpness. These two guidelines can provide intuitive explanations of several heuristics in existing pruning algorithms. Moreover, to address the challenges in computing the involved Gaussian width, we develop improved spectrum estimation for large-scale and non-positive Hessian matrices. Experiments demonstrate the almost perfect agreement between our theoretical results and the experimental ones.
Limitations. In this paper, the (almost) coincidence of the upper bound and lower bound of the pruning ratio depends on the condition that removed weights are of quite small value, which enabled by the I regularization we employed. Therefore, it is important to demonstrate whether the regularized training optimal or nearly optimal the sense of obtaining the smallest sub-network without performance degradation for the original learning problem.
10

---

Acknowledgments and Disclosure of Funding
This work was supported in part by the National Key Research and Development Program of China under Grant 2024YFE0103800 in part by the National Natural Science Foundation of China under Grant 62071 1992. We thank the anonymous reviewers for their valuable and constructive feedback that helped in shaping the final manuscript.
References
[1] Dennis Amelunxen, Martin Lotz, Michael B McCoy, and Joel A Tropp. Living on the edge: Phase transitions in convex programs with random data. Information and Inference: A Journal of the IMA, 3(3):224 ((3, 2014.
[2] Haim Avron and Sivan Toledo. Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. Journal of the ACM (JACM), 58(2):1-34 2011.
[3] Zhaojun Bai, Gark Fahey, and Gene Golub, Some large-scale matrix computation problems. Journal of Computational and Applied Mathematics, 74(1-2):71-89, 1996.
[4] Riade Benbaki, Wenyu Chen, Xiang Meng. Hussein Hazimeh, Natalia Ponomareva, Zhe Zhao, and Rahul Mazumder. Fast as chita: Neural network pruning with combinatorial optimization. In International Conference Machine Learning, pages 2031-2049. PMLR, 2023.
[5] Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo, and Alan S Willsky. The convex geometry of linear inverse problems. Foundations of Computational mathematics, 12:805-849, 2012.
[6] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint 1rXiv:1803.085 2018.
[7] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. In International Conference on Machine Learning, pages 3259-3269. PMLR, 2020.
[8] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Pruning neu- ral networks at initialization: Why are we missing the mark? arXiv preprint (XXi:20009008770 2020.
[9] Khashayar Gatmiry, Zhiyuan Li, Ching-Yao Chuang, Sashank Reddi, Tengyu Ma, and Stefanie Jegelka. The inductive bias of flatness regularization for deep matrix factorization. arXiv preprint 1iXiv:2306.13233 2023.
[10] Yehoram Gordon. On milman's 's inequality and random subspaces which escape through a mesh in IR" In Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 1986-87, pages 84-106. Springer, 1988.
[11] Yiwen Guo, Anbang Yao, and Yurong Chen. Dynamic network surgery for efficient dnns. Advances in neural information processing systems, 29, 2016.
[12] Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural net- works with pruning, trained quantization and huffman coding. arXiv preprint arXiv:1510.0011 2015.
[13] 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.
[14] Kaiming He, Xiangyu Zhang, Shaoging Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[15] Yang He, Ping Liu, Ziwei Wang, Zhilan Hu, and Yi Yang. Filter pruning via geometric median for deep convolutional neural networks acceleration. Proceedings the IEEE/CVF conference on computer vision and pattern recognition, pages 4340-4349, 2019.
2019.
11

---

[16] A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto. 2009.
[17] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 60(6):84 90, 2017.
[18] Cornelius Lanczos. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Natl. Bur. Stand. B, 49.255555-222 282, 1950.
[19] Brett W Larsen, Stanislav Fort, Nic Becker, and Surya Ganguli. How many degrees of freedom do we need to train deep networks: a loss landscape perspective. arXiv preprint arXiv:2107.05802, 2021.
[20] Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
[21] Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
[22] Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. arv preprint 1oXiv:6008.085 10, 2016.
[23] Jian-Hao Luo, Hao Zhang, Hong-Yt Yu Zhou, Chen-Wei Xie, Jianxin Wu, and Weiyao Lin. Thinet: pruning enn filters for thinner net. IEEE transactions on pattern analysis and machine intelligence, 41(10) 2538, 2018.
[24] Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz. Pruning convolutional neural networks for resource efficient inference. arXiv preprint arXiv:161 1.0:4400106444,, 2016.
[25] Mansheej Paul, Feng Chen, Brett W Larsen, Jonathan Frankle, Surya Ganguli, and Gintare Karolina Dziugaite. Unmasking the lottery ticket hypothesis: What's encoded in winning ticket's mask? arXiv preprint arXiv:2210.03044, 2022.
[26] Henning Petzka, Michael Kamp, Linara Adilova, Cristian Sminchisescu, and Mario Boley, Rela- tive flatness and generalization. Advances in neural information processing systems, 34:18420- 18432, 2021.
[27] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint
2014.
[28] Kartik Sreenivasan, Jy-yong Sohn, Liu Yang. Matthew Grinde, Alliot Nagle, Hongyi Wang. Eric Xing, Kangwook Lee, and Dimitris Papailiopoulos. Rare gems: Finding lottery tickets at initialization. Advances in Neural Information Processing Systems, 35:14529-14540, 2022.
[29] Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang, and Jason Lee. Sanity-checking pruning methods: Random tickets win the jackpot. Advances in neural information processing systems, 33:20390-20401, 2020.
[30] M. Talagrand. New concentration inequalities for product spaces. Inventionnes Math., 126:505- 563, 1996.
[31] M. Talagrand. A New Look at Independence. Ann. Probab., 24:1-34, 1996.
[32] Michel Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de I'Institut des Hautes Etudes Scientifiques, 81:73-205, 1995.
[33] Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012.
[34] Roman Vershynin. Estimation in high dimensions: a geometric perspective. In Sampling Theory, Renaissance: Compressive Sensing and Other Developments, pages 3-66. Springer, 2015.
[35] Xin Wang, Fisher Yu, Zi-Yi Dou, Trevor Darrell, and Joseph E Gonzalez. Skipnet: Learning dynamic routing convolutional networks. Proceedings of the European Conference on Computer Vision (ECCV), pages 409-424, 2018.
12

---

[36] Qian Xiang, Xiaodan Wang, Yafei Song, Lei Lei, Rui Li, and Jie Lai. One-dimensional convolutional neural networks for high-resolution range profile recognition via adaptively feature recalibrating and automatically channel pruning. International Journal of Intelligent Systems, 3333-333333 2021.
[37] Tien-Ju Yang. Yu-Hsin Chen, and Vivienne Sze. Designing energy-efficien efficieent convolutional neural networks using energy- pruning. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 5687-5695, 2017.
[38] Tien-Ju Yang, Andrew Howard, Bo Chen, Xiao Zhang, Alec Go. Mark Sandler, Vivienne Sze, and Hartwig Adam. Netadapt: Platforn-aware neural network adaptation for mobile applications. In Proceedings of the European conference on computer vision (ECCV), pages 285-300, 2018.
[39] Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W Mahoney. Pyhessian: Neural networks through the lens of the hessian. In 2020 IEEE international conference on big data (Big data), pages 581-590. IEEE, 2020.
[40] Lei You and Hei Victor Cheng. Swap: Sparse entropic wasserstein regression for robust network pruning. In The Twelfth International Conference on Learning Representations, 2024.
[41] Xin Yu, Thiago Serra, Srikumar Ramalingam, and Shandian Zhe. The combinatorial brain sur- geon: pruning weights that cancel one another in neural networks. In International Conference Machine Learning, pages 00666-25683..8 PMLR, 2022.
[42] Hao Zhou, Jose M Alvarez, and Fatih Porikli. Less is more: Towards compact cnns. In Computer Vision-ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings. Part IV 14, pages 662-677. Springer, 2016.
[43] Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression. arXiv preprint arXiv: 1rXiv:1710.0187. 2017.
[44] Liu Ziyin and Zihao Wang. spred: Solving 11 penalty with sgd. In International Conference Machine Learning, pages 43407-43422 PMLR, 2023.
13

---

A
Organization of Appendix
The appendix is organized follows:
Sec.
A
an overview of the organization of the appendix.
Sec. B
detail descriptions the datasets, models, hyper-parameter choices used in our
experiments. Additionally, figures illustrating the theoretical pruning threshold included.
Sec. [ this section delves into the practical calculation of the Gaussian Width. It addresses the challenges associated with the non posiiiiisissses of the Hessian matrix and the spectrum estimation of large-scale Hessian matrix. Experimental results highlighting the "important eigenvalues" are also showcased.
Sec. D a comprehensive proof of the Gaussian Width for both the ellipsoid and the deformed
ellipsoid is provided.
this section presents the proof of the "sub-sublevel set" utilized in deriving the upper bound of the pruning ratio. Furthermore, straightforward explanation of the relationship between the general lower bound and the upper bound is offered.
Sec. B
Sec. F omitted proof of the connection between the sharpness and the lower bound of the pruning ratio is detailed in this section.
Sec. G performance comparison between the regularized one-shot magnitude pruning, termed as "LOMP", and several prominent pruning strategies. Results from a hypothetical experiment verifying the importance of magnitude in pruning and comprehensive statistical results from Sec. 4.2 are also included.
Sec. H
limitations our assumptions and theoretical results.
Sec. T
broader impacts statement of this research.
14

---

B Experimental Details
In this section, we describe the datasets, models, justment used in our experiments. All of experiments using PyTorch 1.12.1 on Nvidia RTX3090s with ubuntu20.04-cudal1 1.3.11.uddnd. docker.
choices and eigenspectrum ad-
B.1 Dataset
CIFAR-10. CIFAR-I0 consists of 60,000 color images, with each image belonging to one of ten different classes with size 32 x 32. The classes include common objects such airplanes, automobiles, birds, cats, deer, dogs, frogs, horses, ships, and trucks. The CIFAR-10 dataset is divided into two subsets: training set and test set. The training set contains 50,000 images, while the test set contains 10,000 images [6]. For data processing, we follow the standard augmentation: normalize channel-wise, randomly horizontally flip, and random cropping.
CIFAR-100. The CIFAR-100 dataset consists of 60,000 color images, with each image belonging to one of 100 different fine-grained classes [T6]. These classes are organized into 20 superclasses, each containing 5 fine-grained classes. Similar to CIFAR-10. 10, the CIFAR- 100 dataset is split into training set and a test set. The training set contains 50,000 images, and the test set contains 10,000 images. Each image is of size 32x32 pixels and is labeled with its corresponding fine-graines class. Augmentation includes normalize channel-wise, randomly horizontally flip, and random cropping.
TinyImageNet. TinyImageNet comprises 100,000 images distributed across 200 classes, with each class consisting of 500 images (00). These images have been resized to 64 x 64 pixels and are in full color. Each class encompasses 500 training images, 50 validation images, and 50 test images. Data augmentation techniques encompass normalization, random rotation, and random flipping. The dataset includes distinct train, validation, and test sets for experimentation.
B.2 Model
In all experiments, pruning skips bias and batchnorm, which have little effect on the sparsity of the network. Non-affine batchnorm is applied in the network, and the initialization of the network is kaiming normal initialization.
Full Connect Network(FC-5, FC-12). We train a five-layer fully connected network (FC-5) and twelve-layer fully connected network FC-12 on CIFAR-10 10, the network architecture details can be found in Table
Table 3: FC-5 and FC-12 architecture used in our experiments.
Model
Layer Width
FC-5
1000, 600, 300, 100, 10
FC-12
1000, 900, 800, 750, 700, 650, 600, 500, 400, 200, 100, 10
We use the standard AlexNet architecture. In order to use CIFAR-10 10 to train AlexNet, we upsample each picture CIFAR- to x 224 224. The detailed network architecture parameters shown in Table
AlexNet [7).
VGG-16 [27] In the original VGG-16 network, there are 13 convolution layers and 3 FC layers (including the last linear classification layer). We follow the VGG-16 architectures used in 7 (] to remove the first two FC layers while keeping the last linear classification layer. This finally leads to a 14-layer architecture, but we still call VGG- 16 as it is modified from the original VGG-16 architectural design. Detailed architecture is shown in Table 5 VGG-16 is trained on CIFAR-10. 10.
We use the standard ResNet architecture for Tiny and tune for the CIFAR- 100 dataset. The detailed network architecture parameters are shown in Table 6 ResNet-18 18 and ResNet-50 is trained on CIFAR-100 and TinylmageNet.
ResNet-18 18 and ResNet-50 14]
15

---

Table 4: AlexNet architecture used in our experiments.
Layer
Shape
Stride
Padding
convl
3 x 96 x 11 x 11
4
max pooling
kernel size:3
2
N/A
conv2
96 x 256 x 5 x 5
1
2
max pooling
kernel size:3
2
N/A
conv3
256 x 384 x 3 3
1
I
conv4
384 x 384 x 3
conv4
384 x 256 x 3 x 3
1
max pooling
kernel size:3
2
N/A
linearl
6400 x 4096
N/A
N/A
linearl
4096 x 4096
N/A
N/A
linearl
4096 10
N/A
N/A
Table 5: VGG-16 architecture used in our experiments.
Layer
Shape
Stride
Padding
conv1
64 x
conv2
64 x 64 x 3
1
max pooling
kernel size:2
2
N/A
conv3
64 x 128 x 3 3
I
1
conv4
128 x 128 x 3
1
max pooling
kernel size:2
2
N/A
conv5
128 x 256 x 3
1
conv6
256 x 256 X 3
I
conv7
256 x 256 x 3
I
max pooling
kernel size:2
2
N/A
conv8
256 x 512 x x 3
1
conv9
512 x 512 x x
I
conv10
512 x 512 x x 3
max pooling
kernel size:2
2
N/A
conv
512 x 512 x x 3
conv 12 conv 13 max pooling avg pooling linearl
512 512 x x
1
512 x 512 x 3 x 3
1
I
kernel size:2
2
N/A
kernel size:1
1
N/A
512 10
N/A
N/A
Table 6: ResNet architecture used in our experiments.
Layer convl
ResNet-18
ResNet-50
61,3 x 3; stride:1; padding::
61,3 3; stride:1; padding:
64, stride:1; padding:0
64,3 3; stride:1; padding:1
block1
64,3 x 3; stride:1; padding:
x
64,3 stride:1; padding:
256, stride:1; padding:0
128, stride:1; padding:0
128, 3 stride:2; padding:1
bluck1
128, 3 x 3; stride:1; padding:1
x
128, x 3; stride:2; padding:1
x 4
512,3 x 3: stride:1; padding::)
256, 1 x 1; stride:1; padding:0
[28, stride:2; padding:1 256,3 stride:1; padding:1
block1
x 2
256, 3 x 3: stride:2: padding:1
1024, 1; stride:1; padding:0)
512, stride:1; padding:1
512,3 x 3: stride:2; padding:1
block1
512, stride:2; padding:1
512, 3 x 3; stride:1; 0
2048, 1 stride:1; padding:0)
avg pooling linearl
kernel size:1; stride:1
kernel size: stride:
512 x Class um
2048 x ClassNun
16

---

B.3 Training prpper-paramttrrs Setup
In this section, we will describe in detail the training algorithm on multiple datasets and models. The various hyperparameters are detailed in Table 7
the Global One-shot Pruming
Table 7: Hyper Parameters used for different Datasets and Models.
Epachs
Optimizer
Momentum
Up
Weight Decay
CasineLR
Lambda
FC5
CIFARIO
128
200
SGD
0.01
0.9
0
0
NIA
0.00005
FC12
CIFARIO
200
SGD
001
0.9
0
NiA
0,00005
VGG16
CIFARIO
200
SGD
0.01
0.9
5
0
True
0.00015
AlexNet
CIFARIO
128
200
SGD
0.01
0.9
5
0
Trac
0.00003
ResNet18
CIFARIOU
200
ResNet50
CIFARI00
128
200
SGD
0.1
0.9
5
0
Truc
0.00002
ResNct18
TinyInageNet
200
SGD
0.01
0.9
Trae
0.00023
ResNet50
TinyImageNet
200
SGD
0.01
0.9
0
Truc
0,9001
B.4 Sublevel Set Parameters Setup.
Given a dense well-trained neural network with weighted donated as w', the loss sublevel set is defined as [w E RDD W Hw S c} where w - w w', under the assumption that the test data is often unavailable and we also generally assume that the training and test data share the same distribution, thus we use the training data to define the loss sublevel set. compute standard deviation of the network's 's loss across multiple batches on the training data set and denote it by
Table 8: Hyper Parameters used in SLQ Algorithm.
Model
Dataset
Runs
Iterations
Bins
Squared Sigma
FC5
CIFARIO
128
100000
le-10
FC12
CIFAR1O
128
100000
le-10
VGG16
CIFARIO
128
100000
le-07
AlexNet
CIFARI0
96
100000
le-07
ResNet18
CIFARI00
128
100000
le-07
ResNet50
CIFARI00
128
100000
1e-07
ResNet18
TinylmageNet
128
100000
lc-07
ResNet50
TinyImageNer
88
100000
1e-07
B.5 Theoretical Pruning Ratio
Taking w as the initial pruning point and calculating the corresponding value R = l| w' for different pruning ratios k/D. We then plot the corresponding of the theoretically predicted pruning ratio and the calculated R in the same graph. The intersection point these two curves is taken the lower bound of the theoretically predicted pruning ratio. All results are shown in Figure
Magnitude Pruning
Theory Prediction
Pruning Ratio
1.0
1.0
10
0.5
0.5
0.5
0.5
Pruning
0.0
0.0
0.0
0.0
100
200
300
400
250
500
750
1000
10
Figure 5: The theoretically predicted pruning ratio in eight tasks. The first row, from left right, corresponds to FC5, FC12, AlexNet, and VGG16 on CIFAR10. The second row, from left to right, corresponds ResNet18 and ResNet50 on CIFAR100, well ResNet18 and ResNet50 on Tinylmagenet.
17

---

C Practical Calculation of Gaussian Width
In practical experiments, determining the Gaussian width of the ellipsoid defined by the network loss function is challenging task. There are two primary challenges encountered in this section: 1.) the computation of eigenvalues for high-dimensional matrices poses significant difficulty; 2.) the network fails converge perfectly the extremum, leading to a non-positive definite Hessian matrix for the loss function. In this section, we tackle these challenges through the utilization of fast eigenspectrum estimation algorithm and an algorithm that approximates the Gaussian width of deformed ellipsoid body. These approaches effectively address the aforementioned problems.
C.1 Improved SLQ (Stochastic Lanczos Quadrature) Spectrum Estimation
Row L1 Norm
Row L1 Norm
0.75
0.4
0.2
0.25
25
50
75
1000
25
50
75
100
25
50
75
100
25
50
75
100
Row Norm
100
2000
50-
1000
0.0
25
50
75
100
25 50 75
100
25
50
75
1000
25
50
Hessian Matrix Index(5)
Hessian Matrix Index(%%
Hessian Matrix Index(%)
Hessian Matrix Index(%)
Figure 6: The statistical analysis of the L1 norm of the Hessian matrix in eight tasks. The first row, from left to right, corresponds to FC5, FC12, AlexNet, and VGG16. The second row, from left to right, corresponds ResNet18 and ResNer50 CIFARI00, as well as ResNet18 and ResNet50 on Tinylmagenet.
Calculating the cigenvalues of large matrices has long been a challenging problem in numerical analysis. One widely used method for efficiently computing these eigenvalues is the Lanezos algorithm [8), which is presented in Algorithm 2 However, due to the huge amount of parameters of the deep neural network, it is still impractical to use this method calculate the eigenspectrum of the Hessian matrix of a deep neural network. To tackle this problem, [39] proposed SLQ (Stochastic Lanezos Quadrature) Spectrum Estimation Algorithm, which estimates the overall eigenspectrum distribution based on small number of eigenvalues obtained by Lanczos algorithm. This method enables the efficient computation of the full eigenvalues of large matrices. Algorithm 2 outlines the step-by-step procedure for the classic Lanczos algorithm, providing comprehensive guide for its implementation. The algorithm requires the selection of the number of iterations, denoted as m, which determines the size of the resulting triangular matrix T.
In general, the Lanezos algorithm is not capable of accurately computing zero eigenvalues, and this limitation becomes more pronounced when the SLQ algorithm has a small number of iterations. Similarly, vanishingly small eigenvalues large-scale deep neural network, the experiment found that the network loss function hessian matrix has large number of zero eigenvalues and vanishingly small eigenvalues. In the Gaussian width of the ellipsoid, the zero eigenvalues and vanishingly small eigenvalues have the same effect on the width (insensitive other parameters), and we collectively refer to these eigenvalues as the "important" cigenvalues. We divide the weight into 100 parts from small to large, calculate the recond-order derivative (including partial derivative) smallest weight in each part, and sum the absolute values of all second-orde derivatives of the weight, which corresponds to 1ı-norm of a row in hessian matrix, and the row I nnor is zero or a vanishingly small corresponds to an "important" eigenvalue, the experimental results can be seen in the Figure from which the number of missing eigenvalues of the SLQ algorithm can be estimated, we then add same number of le-30 as the missing eigenvalues in the Hessian matrix eigenspectrum. All the SLQ algorithm parameters are discribed in Table 8 and the statistical analysis of the norm of Hessian matrix rows for all experiments presented Figure For details of the SLQ algorithm and the improved SLQ algorithm, see Algorithm 3 and Algorithm
also ignored by Lanezos. However, in a well-trained
18

---

Algorithm 2 The Lanczos Algorithm
Input: Hermitian matrix A of size n, number of iterations
Output: tridiagonal real symmetric matrix T of size m X m initialization:
1. Draw a random vector V1 of size n x 1 from (0,1) and normalize it;
2. W1 = AV1; a1 =< W1, V1 >; W1 = W1 V1V
3.
for j = 2, m do
1). {3 |w
2).
if 8; 0 then
stop
else
Vj w 1/3
end if
3). Wj = Avj;
4). a, = < ....V Vj >;
5). Wj Wj -ojVj VjVj-
end for
4. T(i, i) = 0x, i= 1,..... m:
i + 1, Br, i == ,,... 1.
Return: T
Algorithm 3 SLQ(Stochastic Lanczos Quadrature) Spectrum Estimation Algorithm
Input: A hermitian matrix A of size n, Lanczos iterations m, ESD computation iterations 7, gaussian kernel f and variance o². Output: The spectral distribution of matrix A
:ri==,.... do
1). Get the tridiagonal matrix T of size x m through Lanczos algorithm:
2). Compute m eigenpairs (A o (0) from T;
3). ot (1) Σm= Tb J(A
(8) (6) (0,40 o),, where (2) T ( (1))² is the first component of r
end for
4). @(t) - (t)
Return: ((t)
C.2 Gaussian Width of the Deformed Ellipsoid
After effective training, generally assumed that a deep neural network will converge to the global minimum of its loss function. However, in practice, to oscillate around the minimum instead of converging to it. This leads to that the Hessian matrix of the loss function would be non-posites non-positive definite, and the resulting geometric body defined by this matrix would change from an expected ellipsoid to a hyperboloid, which is unfortunately nonconvex. the perfect minima, propose
after meticulous tuning, the network tends
To quantify the Gaussian width of the ellipsoid corresponding to approximate by convexifying the deformed ellipsoid through replacing the associated negative eigenvalues with its absolute value. This processing turns out be very effective, demonstrated by the experimental results.
Lemma C.1 Consider well-trained neural network with weights w, whose loss function defined by has Hessian matrix H. Due to the non-positive definiteness of H, there exist negative eigenvalues. Let the eigenvalue decomposition of H be H = Ev, where E is diagonal matrix of eigenvalues. Let v Elv, where |- means absolute operation. the geometric objects defined by and
1wW are S(c) = [w ERR 3 l.w"Ho "Hw SwwS <) and Š(e) = {w W TRD } Dw S <), then:
w(S(e)) (((())
(22)
19

---

The proof of Lemma C.I is in Appendix D.2 converges to vicinity the global minimum of the loss function, the Gaussian width of the deformed ellipsoid body can be approximated by taking the convex hull of S(e).
Lemma C.1 indicates that if the deep neural network
20

---

D Gaussian Width of the Sublevel Set
In this section, we provide detailed proofs regarding the Gaussian Width of the sublevel sets of quadratic wells.
D.1 Gaussian Width of the Quadratic Well
Gaussian width is an extremely useful tool to measure the complexity of convex body. In our proof, we will use the following expression for its definition:
w(S) (S) = 2 x.eS
E sup (g.x - y) N
Concentration of measure is universal phenomenon in high-dimensional probability. Basically, it says that a random variable which depends a smooth way on many independent random variables (but not too much any of them) is essentially constant, (30 31 32
Theorem D.1 (Gaussian concentration) Consider random vector x ~ (O0, Inxn) and an L--
Lipschitz function f R" R (with respect to the Euclidean metric). Then for t
1
P(I((x) - Ef(x) St, c 222
Therefore, if e is small, fxx be approximated as f(x) RO Ef(x) --2
Lemma D.2 Given random vector NO, Laxn) and the inverse of positive definite Hessian matrix Q = H-1, where H E RRx,, we have:
E x ExxQx
Proof.
1.) Concentration of xTQx Qx
Define f(x) = =xQQx, we have:
f(x) =x
=xTUEU'X
Figenvalue Decomposition of Q Q = UEUT.
w. p. almost 1.
Invariance of Gaussian under rotation.
where X; is the eigenvalue of Q. The lipschitz constant L, of function f(x) is
L = max( of = max([2A;ara]
Let g(x;)) = 2A,r, whose lipschitz constant is L, = |2A;]. Invoking Theorem D.I we have:
g(x;)= Eg(x;) + 222
-888Aflnes
Therefore, the lipschitz constant of f(x) can be approximated by:
L = marl -8AfIne)) = --8lne Amaz
Invoking Theorem D.I again, we establish the concentration of f(x) as follows:
f(x) ~ [x) / -2(L)) P
Theorem D.1
= Ex) + 4. Ine InegAmas
21

---

2.) Jensen ratio of V x Tx
E EVI(() EV [x(x) + 4v Inc Ine Amar
Concentration of fxx).
Ef 2 Ineg1
Taylor Expansion.
VEf(x)
Therefore, the Jensen ratio of v fxx) can be approximated by:
Evf(x f() V [x
Amaz
+ 2V Ine lne2
Hutchinson's method 2
21=1 A
-1+8
Q is a Wishart matrix, i.e. Q ATA, where A random matrix whose elements are independently and identically distributed with unit variance, according to the Marchenko-Pane Pastur law 33.. the maximum eigenvalue of Q is approximately 4n and the trace of Q is approximately n². Therefore, the above Jensen ratio approaches to with decaying rate (
For the inverse of a positive definite Hessian matrix which is of our concern, we take = = 10 numerical simulations show that when the dimension n 10 the corresponding Jensen ratio is on the order of 10-3, which is in good agreement with the theoretical value and is arguably negligible. Similar the case of the discusdd Wishart matrix, when the dimension increases, the value of ó will further decrease.
the above
Consequently, we can conclude that E R Ef(()), i.. E x Rs Ex
Definition D.3 (Definition of ball) A (closed) ball B(c,r) (in RDP) centered at c RD with radius r the set
B(c,r) == x
The set B(0, 1) is called the unit ball. An ellipsoid is just an affine transformation of a ball.
Lemma D.4 (Definition of ellipsoid) An ellipsoid S centered the origin is the image L(B(O, 1)) of the unit ball under an invertible linear transformation L -RD' + +RD. An el- lipsoid centered general point RRD is just the translate S of some ellipsoid centered at the origin.
Proof.
L(B(O.1)) = (Ix B(0,
(y L L E B(0,
(y: (L "y)
= (y y (LL")
{y y Q 1
where - LL is positive definite. The radius r; along principal axis e; obeys r? X where X; is the eigenvalue of Q-1 and e; is eigen vector.
Lemma D.5 (Gaussian width of ellipsoid) Let S be an ellipsoid in T&D defined by the positive definite mairix H E DxD,
5(c) (WER 1
W <)
Then wS) or the squared Gaussian width of the ellipsoid satisfies:
w(S)² 2T = Σ
where Ti / with X is i-th eigenvalue of H.
22

---

Proof. Let ~ (D( and LL' = 2cH"
Then:
wcL(BB))
E supxyem(..))
<g. Lx Ly>
2
E SUPx.EE((..)
L -
El|LTgle
Definition of Ball.
EvggLL""g
8gl2 = Vggg, where E IR Dx1
E/22gTT-
2
Lemma D.2
(2TT((H-1)
Invariance of Gaussian under rotation.
Thus, w(S)² x 2eTT(H- Σ 1/.
D.2 Gaussian Width of the Deformed Ellipsoid
Generally, it is assumed that the gradient descent algorithm will converge to minimum point. However, in practice, even with small learning rates, the network may oscillate near the minimum point and not directly converge to it, but rather get very close to it. As a result, the actual Hessian matrix is often not positive definite and its eigenvalues may have negative values.
Lemma D.6 Let the Hessian matrix at the minimum point be denoted by H with eigenvalue X and the Hessian matrix at an oscillation point be denoted by H with eigenvalue X The negative eigenvalues of H have small magnitudes.
Proof. Let the weights at the minimum point be denoted by wo and the Hessian matrix at oscillation point be denoted by wo. Consider a loss function L. and a loss landscape defined by [(w). taking Taylor expansion of L( [(w) at Wo:
[(w) L(wo) + 7 (w (ww-wo) HoW wo) + R(wo)
Let wo = wo + with is closed to 0:
L(Wo) L(wo + v)
= =[(w)) + 2 v"
"H Hv + R(wo + +v)
Therefore, the second order derivative of L(Wo) is:
E" (w) = L" (wo + v)
H + R (wo + +v)
2 HH
where ('(w)= = H, Let H = H + Ho with Hg is closed to 0, considering the Weyl inequality:
(HH - R₂ (H) < Hullz
where ||oll is small enough. So if (H) is less than O, since (H) > ( Holl its absolute value (H) S [Ho (H) Holl2 which means that the negative eigenvalues of the Hessian matrix have small magnitudes.
Lemma D.7 For sublevel set S(e) fw wW c) defined by matrix H with small magnitude negative eigenvalues. The Gaussian width of S(e) can estimated by obtaining the absolute values of the eigenvalues of the matrix H.
23

---

Proof. Assuming that the eigenvalue decomposition of H - = = where Σ is diagonal matrix consisting of the eigenvalues of H, let D v' be positive definite matrix and | be negative definite matrix. Consider the definition of S(e):
w Hw w² (H D D)w w Mw Dw
S
Therefore, (c) be expressed D' Sc- wC Since the magnitudes of the negative eigenvalues of H are very small, we can assume that w Mw is also small, and thus w' Dw S Ww Mw can be approximately equal w Dw e. As a result, can estimate the Gaussian width of (e) by approximating it with the absolute values of the eigenvalues of H.
Corollary D88 Consider a well-trained neural network with weights w, whose loss function defined by has a Hessian matrix H. Due the non-positive definiteness of H. there exist negative eigenvalues. Let the eigenvalue decomposition of H be H Ev, where E is a diagonal matrix of eigenvalues. Let v'' Elv, where | means absolute operation. the geometric objects defined by and are S(e) := {w E RR: 3 T Hw S e) and S(e) = {w E RP: // WW S e). then the gaussian width of the two set sutisfy:
w(((()) w((())
24

---

E
Comparison between the Upper and Lower Bound
This section provided the proofs used in the upper bound derivation and roughly analyzed how the lower bound changes when the upper bound varies.
E.1 D - k: Dimension Sublevel Set is Still an Ellipsoid
In the derivation of the upper bound for the pruning ratio threshold, we employed D dimensional loss sublevel set:
S(w) {w" P- C((w', w')) () S [(w") +
(23)
Perform Taylor expansion to L((w?, w') with respect to w', the sublevel set is represented as:
S(w') = (w RDD (w )'''' H'wws sc}
(24)
where H is the Hessian matrix of C(ww', w () with respect w'.
Given that the full sublevel set S(e) = {w RDD f Hw S }} an ellipsoid body, which implies that H is a positive definite matrix, it is evident that H is the principal submatrix of H. Consequently, H is also positive definite matrix, which implies that the sublevel set S(w') remains an ellipsoid.
E.2 Relationship between the Upper and Lower Bound
Theorem E.1 (Eigenvalue Interlacing Theorem) Suppose A E Rax= is symmetric, Let B E mmxm with m n be a principal submatrix obtained by deleting both i-th row and i-th col- umn for some values of i). Suppose A has eigenvalues \₁ S .... S An and B has eigenvalues B1 S ... S Bm. Then
À S 8k S dctn-m for k = =,.....,
(25)
And m- = n 1,
\1 S 31 A2 S S Bn-1 S An
(26)
Next, we provide an elucidation on the relationship between the upper bound and lower bound variations:
Lemma E.2 The direct and straightforward relationship between the upper bound and the lower bound can be articulated as follows:
1. When the eigenvalues change, the upper and lower bounds will change in the same direction;
2. When the weight magnitude changes, the upper bound will change in the same direction as the upper bound or do not change.
Proof. 1. When the eigenvalues change, the upper and lower bounds will change in the same direction;
By leveraging the Eigenvalue Interlacing Theorem (Theorem E.I. the eigenvalues of the principal submatrix in the upper bound is bounded by the eigenvalues in the lower bound. It's obvious that the eigenvalues in the lower bound change, the eigenvalues in the upper bound will also change in the same direction, leading to the upper and lower bounds will change in the same direction.
2. When the weight magnitude changes, the upper bound will change in the same direction as the lower bound do not change.
It's noted that the number of weights in the lower bound is more than the one of weights in the upper bound. These weights are used calculate the projection distance. So it's clear that when the weight magnitude changes, the upper bound will change in the same direction as the lower bound or not change.
25

---

Sharpness & Lower Bound
In this section, we will provide the relationship between the lower bound of the pruning ratio and the sharpness of the loss landscape w.r.t the weights. We first introduce the definition of sharpness, which is similar to the sharpness definition in [26 and
Definition F.1 Given second-order derivable function f(w), where is the parameters. Consid- ering a hessian matrix w.r.t parameters w, the sharpness of f(w) w.r.t parameters defined as the trace of H, Le. Tr(H).
As defined in definition F.1 a smaller trace indicates flatter function. Next, we will provide the connection between the sharpness and the lower bound:
Lemma F22 Given a well-trained neural network f(w, x), where w is the parameters and the x is the input. The lower bound pruning ratio pi and the sharpness Tr(H) obeys:
2eD
P1 S
(27)
w (T) 2eD
where H is the hessian matrix of f(w) wirt. w.
Proof.
D
=
D
W
w*
1/ +
i=1
2E
1
1
|
w 1/ 2E
1=1
2E
D
< 1
Cauchy- Sehch-SShhwrz Inquality.
D
Ei=((//'*
(1/W*
w 112,1 2c)
2eD
|| |
w Ei
2&D 2eD
2cD
=1 w*1) 2eD
It's obvious that if the trace of the hessian matrix becomes smaller, the lower bound will also decrease, indicating higher sparsity level. Utilizing sharpness as the optimization objective for network pruning is both rational and efficacious approach.
Corollary F.3 Given a well-trained neural network f(w,x) where w is the parameters and the is the input. The pruning ratio lower bound and the sharpness obeys:
2eD
PI S
(28)
| w (T) 2eD
where H is the hessian matrix of f(w) w.r.f. An informal version of this corollary can be stated as: sharpness controls the lower bound of the pruning ratio, specifically, a flatter neural network can be pruned more sparsely.
26

---

G
Full Results
Here present the full set of experiments performed for the results in the main text.
G.1
The Distance Between the Distribution of Weights
In this section, we provide the total variation(TV) distance between the distribution of trained weights with independent initialization.
Table 9: The TV Distance Between the Distribution of Weights.
CIFARIO TV
FC5
FC12
Alexnet
VGG16 0.01 10.000
0.02:10011
0.01=0.001
0.02=0.02
ResNet
CIFARI00
50 CIEARIO0
18 Tinylmagenet
50 TinyImagenet
TV
0.04
0.03=00.2
0.02=0.03
0.03+:0.02
G.2
Comparison of Pruning Algorithms
As discussed in Section 4 we adopt 4 regularization during the training phase, and the hyper- parameter for the I regularization is selected empirically. After thorough training, applied magnitude pruning to reduce the network to the lowest pruning ratio at which the network's 's perfor- mance is maintained, and we didn't apply fine-tuning after pruning.
We validated ( regularized one-shot magnitude pruning algorithm(LOMP) against four baselines: dense weight training and three pruning algorithms: (i) Rare Gems(RG) proposed by (28). (ii) Iterative Magnitude Pruning(IMP) donated by 77 (iii) Smart- (SR) which is the random pruning method proposed by (29]. Table I0 shows the pruning performance of the above algorithms, our pruning algorithm is better performing than other algorithms.
Table 10: Performance comparison of various pruning algorithms.
Test Ace (% 1@oop-1
Dataset
Model
Dense Acc (%)
Sparsity (%)
LOMP(ours)
RG
IMP
SR
FC5
55.3:10.62
1.7
59.96:10.45
58.7620.15
58.83-0.24
CIFARIO
FC12
55.5:::.26
60.84:10.21
54.96:10.28
59.37=0.21
VGG16
90.73++0.22
0.6
91,66
88.76#0.13
89.22=0.24
87.32-0.11
ResNet18
72.19=0..23
1.9
71.82:10.09
69.33=0.22
68.55=0.21
65.74=0.27
CIFARI00
ResNet50
74.07=00.33
2.0
7..12++0.11
72.21
69.02-0.23
68.58-0.33
ResNet18
$2.92-10.13
4.2
55.42:10.02
45.43:0.27
45.12-0.19
43.28=0.21
TinyImageNet
ResNet50
56.45:10.17
57.49:10.01
514110.28
46.93-0.41
40.42-0.31
Remark. To demonstrate the effectiveness of ( regularization, the dense performance is obtained by training without any regularization. we obtained the dense performance by training without any regularization. According to our theoretical findings, LOMP is the optimal pruning strategy in the pruning-after after-training regime, as the is the closest convex relaxation to the 4o regularization, and the magnitude pruning can achieve the lowset pruning ratio. Consequently, we compared LOMP with several pruning algorithms that are not part of the pruning- after-triinng regime. Notably, LOMP outperforms these other pruning algorithms.
Discussion. The I regularization metric is not new, and in practice, it becomes increasingly challenging to empirically select the hyper-parameter for 4 regularization and train models with I regularization the model size grows. Nevertheless. some reparametrization techniques address the 4 regularization issue, as discussed in [44], may facilitate the use of 4 regularization for pruning, making l regularization one-shot pruning a very promising approach.
G.3 Comparison of Pruning Optimization
In this section, we compared our I regularization-bast one-shot magnitude pruning with those works treating pruning as optimization 4 40 41. Our results are obtained by searching the hyper-
27

---

parameters of 1 regularization, all the data and model settings are followed from 4.. The comparison results can be found in Table IT As is shown in Table [T] extremely high levels of pruning schemes, our proposed method performs better than other methods.
Table 1:: The pruning performance (model accuracy) of various methods on MLPNet, ResNet20, and ResNet50. As to the performance of MP, WF, CBS, CHITA, and EWR, we adopt the results reported in [4] We take five runs for our approaches and report the mean and standard error (in the brackets). The best accuracy values (significant) are highlighted in bold. Here sparsity denotes the
fraction of zero weights in convolutional and dense layers.
Network
Sparsity
MP
WF
CBS
CHITA
EWR
LOMP(ours)
0.5
93.93
94.02
93.96
95.97 (+0.05)
95.24 (1:0.03)
97.43(
0.6
93.78
93.82
93.96
95.93 95.93 (#0.04)
95.13 (+0.001)
07.42(++.222)
0.7
93.62
93.77
93.98
95.89
95.05 (1:0044)
97.45(110.24)
MI PNNet on MNIST
(93.97%)
0.8
92.89
93.57
93.90
95.80
94.84 (=00003
97.534+0.21)
0.9
90.30
91.69
93.14
95.55 (+0.03
97.61(11.00)
0.95
83.64
85.54
88,92
94.70 (#0.06)
92.86 (+0.05)
96.85(+0.14)
0.98
32.25
38.26
55.45
90.73 (=0.11)
85.71 (#0.09)
92.90(10.67)
0.5
88.44
90.23
90.58
91.04 (#0.09
92.04 (L10.03)
91.05 (L00077
0.6
85.24
87.
88.88
90.78 (#0.12)
91.98 (+0009)
91.05 (=0.06)
0.7
78.79
81.05
81.84
90.38 (+0.10)
91.89 (+0.10)
90.82 (+0099)
ResNer20 CIFARIO
(91.36%)
0.8
54.01
62.63
51.28
88.72 (=0.17)
90.15 (+0.09)
90.28 (=006)
11.79
11.49
13.68
79.32 (#1.19)
88.82 (L10.10)
89.26 (L
0.95
81.33 (+0..15)
86.16 0=1.11)
0.98
69.21 (+:0224)
79.15 0.26)
ResNer50 on CIFARIO
0,95
84.96 (L10.15)
93.62 (1 0.16)
(92.78%)
0.98
82.85 (++.220)
89.55 (-5.88)
G.4 Small Weights Benefits Pruning
We verify that small sharpness is not equal to high sparsity through hypothetical experiments. Considering that the hessian matrix of network A and network B1, B2, B3, B4 share eigenvalues {X1, A2....... A_. ). the weight magnitude of network B1, B2, B3, B4 is 2,3,4,5 times that of network A, we take the eigenvalues and weights from a FC network trained without regularization. In this way, the gap between the curves will be more obvious. For other networks. the trend of the curve gap is consistent, the prediction of the network pruning ratio is shown in the Figure. 7 It is observed from Figure. thhat as the magnitude of network weights increases, the capacity the network to tolerate pruning decreases. The pruning ratio threshold is affected not only by loss sharpness but also the magnitude of weights. This finding, on the other hand, provides further evidence of the effectiveness of the 1 norm in pruning tasks.
G.S Statistical Information of Weights in Various Experiments
The same plots as Fig. ((b) and Fig. ((c) are provided in Figure g
28

---

Original Prediction
x3
1.0
0.8
Pruning Ratio
0.6
0.4
0.2
0.0
100
120
R
Figure 7: Pruning ratio prediction on different weight magnitude.
ECSC HALD
FCLDCCWA222
18300
6990
-25
75300
R"2
-329
-125
VCC:SOFMEE
1.0
303030
(lop100
223330
-25
133950
-20
$23030
430030
338000
8-2-000
333530
500300
310000
4333330
(1og10)
333300
50000
220000
-35
-35
-28
100
40
Patamn Value 0eg16)
Panam Indea (9))
Param Value 0eg10)
Param Inden (%6
Figure 8: The same plots as Fig. bb) and Fig. 2 on eight tasks.
29

---

H
Limitations
In this paper, consider a well-trained neural network and argue that the weight magnitude and network sharpness with respect to the weights constitute the fundamental limits of a one-shot network pruning task. Although popular methods such as Iterative Magnitude Pruning Ticket Hypothesis [6] involve multiple rounds of one-shot pruning, the fundamental limits of such multi-shot pruning remain unclear. Furthermore, we demonstrate that when the magnitude of removed weights is small, the upper bound of the pruning ratio nearly coincides with the lower bound. However, not all training strategies result small removed weights, and in such cases, the upper and lower bounds do not coincide. Nevertheless, weight magnitude and network sharpness with respect to the weights still represent the fundamental limits of one-shot network pruning task.
and the Lottery
Broader Impacts
Our work aims advance the theoretical understanding of network pruning, with the anticipation that theoretical insights can guide future designs of network pruning methods. There are no ethically related issues negative societal consequences in our work.
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: See corollary 3.4
Lemma 3.5
Theorem 3.6
Section 4.1 and Algorithm |
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitations of our assumptions and our theoretical
results, limitation section has been included in the appendix, see Section H
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
31

---

Justification: In the main paper, we introduced all the assumptions and provided intuitive explanations. Comprehensive proofs are included in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: See Section 4 in the main paper and Section B in the Appendix.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
32

---

Answer:
[Yes]
Justification: We have provided open access to our code, the anonymized URL is included in the abstract.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https /nipps.cc/pulli//uuui guwdes/ddee/// Coc//ooodeeesiseeeeeeo wwwpobmmsssioooooooooooooooi for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the details and settings are included in the appendix. See Section B in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We provided statistical results of our results under multiple independent runs. See Table
and and Table
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
33

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided information of the computer resources in Section B and our code (see the URL in abstract).
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips: httpp//wwiip.cppppuuu/c/tcccaaaa
Answer: [Yes]
Justification: We confirm that our research adheres to the NeurIPS Code of Ethics in every respect and preserves anonymity.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws or regulations their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed and have included an impact statement in the appendix, see Section] !
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
34

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our research didn't release any data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We have cited the assets we used in our paper, See References.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
35

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our work introduces
assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
36


Reviews:
[{"review_id": "iO3EWXVhvX", "reviewer": "Reviewer_DBJe", "summary": "This paper tries to answer the question of how sparse can a deep neural network be pruned without increasing the loss function. The authors employ high-dimensional geometry tools such as statistical dimension, Gaussian width, and the Approximate Kinematic Formula to derive the lower bound and upper bound of the ratios of weights that can be pruned. The authors also provide an improved algorithm for estimating the eigenvalues of large Hessian matrices, which is used to estimate the Gaussian width.", "questions": "Please see the weakness part.", "limitations": "Yes, the authors did address the limitations.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper provides an interesting perspective for analyzing the limits of network pruning. \n\n2. The tools from convex geometry are novelly applied to study the problem. The derivations of the lower bound and upper bound are solid.\n\n3. The results provide insights into the problem of pruning neural networks and explain certain behaviors from previous work.\n \n4. The experiments show a certain matching between the theoretical bounds and the actual performance.", "weaknesses": "1. The derived upper bound and lower bound on the pruning ratio depend on the new weights of the pruned networks. This is strange to me, meaning that the limit of the pruning ratio varies when a different weight is used. This also limits the application of the results. \n\n2. The numerical experiments are performed using the L1 regularized loss function. However, this is not considered in the theoretical results. I wonder if the bounds will be different if the loss function is changed.\n\n3. The one-shot magnitude pruning ignores the interaction between the weights, which has been shown to be suboptimal in some recent work. However, the authors claim that it is optimal for the lower and upper bounds. I believe this is because the L1 regularization is used as the loss function, which already takes that into account. This should be clarified.\n\n4. The authors claim that the upper and lower bounds match each other when the proposed L1 regularized loss function is used for training. This might not hold when the original loss is without L1 regularization. This should also be discussed and not overclaimed in general cases.\n\n5. The numerical comparison did not consider many state-of-the-art pruning methods (which are also pruning after training) such as \n[1] R. Benbaki et. al., Fast as CHITA: Neural Network Pruning with Combinatorial Optimization\n[2] L. You et. al., SWAP: Sparse Entropic Wasserstein Regression for Robust Network Pruning\n[3] X. Yu et. al., The combinatorial brain surgeon: Pruning weights that cancel one another in neural networks\n\n6. Relating to the previous comment, the magnitude pruning method used here minimizes the bounds proposed here, which then is used as a support for their usefulness. However, in many cases, the network is not pruned to its limit. \n\n7. The title is overclaimed. While the bounds proposed here are sometimes useful, they are not fundamental limits since there are approximations and relaxation used along the derivations. Moreover, the upper and lower bounds do not match each other in general.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your insightful feedback. Below are our detailed responses to your concerns:\n\n**Weakness 1: The derived upper bound and lower bound on the pruning ratio depend on the new weights of the pruned networks. This is strange to me, meaning that the limit of the pruning ratio varies when a different weight is used. This also limits the application of the results.**\n\nGood question. In fact, this is the key point in pruning bounds. We aim for the performance of the sparse network to closely match that of the dense network. In other words, the performance of the sparse network is bounded by that of the dense network. If the weights of the dense model change, the performance bound of the sparse network also changes, leading to a different pruning ratio bound.\n\n\n\n**Weakness 2: The numerical experiments are performed using the L1 regularized loss function. However, this is not considered in the theoretical results. I wonder if the bounds will be different if the loss function is changed.**\n\nIn fact, we are considering the pruning limit of a well-trained model without special focus on the loss function. Our theoretical results actually apply to all well-trained models, regardless of the loss function.\n\n\n\n**Weakness 3: The one-shot magnitude pruning ignores the interaction between the weights, which has been shown to be suboptimal in some recent work. However, the authors claim that it is optimal for the lower and upper bounds. I believe this is because the L1 regularization is used as the loss function, which already takes that into account. This should be clarified.**\n\nThank you for your reminder, we will add relevant instructions to the paper: In the absence of L1 regularization, although the theoretical lower bound for magnitude pruning is the lowest, the achievable upper bound for magnitude pruning may not be the lowest. In general, if the optimal algorithm is not clear, magnitude pruning can be considered as a viable choice.\n\n**Weakness 4: The authors claim that the upper and lower bounds match each other when the proposed L1 regularized loss function is used for training. This might not hold when the original loss is without L1 regularization. This should also be discussed and not overclaimed in general cases.**\n\nGreat reminder. In fact, we only claimed that the upper and lower bounds match when the proposed L1 regularized loss function is used for training. This might not hold in other cases, and we will make this point more clear  in the revised version.\n\n\n\n**Weakness 5: The numerical comparison did not consider many state-of-the-art pruning methods (which are also pruning after training) such as [1] R. Benbaki et. al., Fast as CHITA: Neural Network Pruning with Combinatorial Optimization [2] L. You et. al., SWAP: Sparse Entropic Wasserstein Regression for Robust Network Pruning [3] X. Yu et. al., The combinatorial brain surgeon: Pruning weights that cancel one another in neural networks.**\n\nIn fact, since we proved that the lower bound of magnitude pruning is smaller than that of other pruning methods, and that the upper bound of magnitude pruning is more likely to match the lower bound, we focused solely on magnitude pruning. We will include a comparison with other algorithms in our revised version.\n\n**Weakness 6: Relating to the previous comment, the magnitude pruning method used here minimizes the bounds proposed here, which then is used as a support for their usefulness. However, in many cases, the network is not pruned to its limit.**\n\nThis is true; in general, the lower bound for magnitude pruning is the lowest among pruning methods. However, not all upper bounds for magnitude pruning match this lower bound. If we consider the lower bound as the limit, many models in practice will not be pruned  to this extent. Nonetheless, our theoretical results highlight two key factors that determine network pruning limit: the flatness of the loss landscape and the magnitude of network weights.\n\n\n\n**Weakness 7: The title is overclaimed. While the bounds proposed here are sometimes useful, they are not fundamental limits since there are approximations and relaxation used along the derivations. Moreover, the upper and lower bounds do not match each other in general.**\n\nThank you for your comments. Although the upper and lower bounds generally do not coincide exactly, their gap is indeed negligibly small. Moreover, our theoretical results identify two key factors that influence network pruning: the flatness of the loss landscape and the magnitude of network weights. By constraining these factors, such as using L1 regularization to control magnitude, the upper and lower bounds are more likely to match. Additionally, despite employing approximations in our derivations, the results we obtain is actually nearly exact asymptotically, which is supported by that our theoretical results closely match the simulation outcomes.", "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": "", "extra_scores": {}}, {"review_id": "CQnTTIPhy3", "reviewer": "Reviewer_hJmV", "summary": "The paper investigates the theoretical limits of how sparse a network can be pruned without sacrificing performance. The authors formulate pruning as a convex geometry problem. By imposing sparsity constraints on the loss function, they show that the pruning ratio can be bounded by the width of the loss landscape and the magnitude of the weights. They also propose an spectrum estimation algorithm for dealing with large Hessian matrices. The empirical results align well with the theoretical findings.", "questions": "* What is novel here in light of prior work showing results connecting Gaussian widths to recovery thresholds [4]?\n* How sensitive are the theoretical bounds to the choice of loss function? Do the results generalize across different loss functions commonly used in deep learning?\n* How computationally expensive is the proposed spectrum estimation algorithm compared to existing methods? Is it practical for very large networks?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* Understanding the fundamental limits of network pruning is an important problem, and the insights provided by this paper (weight magnitude and network flatness as key factors) could potentially influence future research in the area.\n* The authors have provided detailed proofs and derivations for the theoretical results.\n* The experiments conducted are extensive enough to validate the theoretical findings, and there is a strong alignment between the theoretical and empirical results.", "weaknesses": "* Limited technical novelty: applying convex geometry to attain similar results (e.g. bounds dependent on the Gaussian width) has been explored in prior works, some of which are cited in the related work section. However, the paper lacks discussion of how this work differs from or builds upon existing literature.\n* More intuitions on the theoretical results would be helpful. For example, loss flatness is one of the key factors discussed in the paper, and only its formal definition (trace of the Hessian) is given in the paper. Intuitions like smaller flatness (i.e. flatter loss landscape) means the loss function is less sensitive to perturbations in the weights would be helpful.\n* Inconsistencies in notations: For example, from equation (17) onwards, the loss sublevel set notation takes in the weights as the argument. Is this the same loss sublevel set defined in equation (2), which takes in epsilon as the argument? And how is the epsilon parameter chosen for the loss sublevel set?\n* I would define \"pruning ratio\" earlier in the paper. It was not clear until the contributions section that smaller pruning ratios means more pruning of the network.\n* The authors have introduced \"pruned ratio\", which equals to 1 - pruning ratio, for Table 2. This is the only place in the paper where this term is used. This is confusing. Why did the authors not stick to \"pruning ratio\" throughout the paper?\n* Please consider removing adjectives like \"powerful\" when describing convex geometry and approximate kinematics formula, or \"very tight characterization.\" They are subjective and do not add much to the clarity of the paper.\n* Some typos like \"Lottery Tickets Hypolothsis\" (line 77)\n* Some terms like SLQ (line 82) are not defined until later in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive feedback! The concerns and questions in the review are addressed as follows.\n\n**Weakness 1: Limited technical novelty: applying convex geometry to attain similar results (e.g. bounds dependent on the Gaussian width) has been explored in prior works, some of which are cited in the related work section. However, the paper lacks discussion of how this work differs from or builds upon existing literature.**\n\nAlthough previous work has employed convex geometry tools to derive lower bounds for network pruning, these bounds might be far from the actual pruning limit. In contrast, we employ more powerful tools in convex geometry, i.e., the statistical dimension and approximate kinematic formula, thus enabling us to obtain a sharp threshold of pruning. \nMoreover, our research tackles the pruning problem in a more systematic way, and through our theoretical results, we explicitly identify two key factors that determine the pruning limit, i.e., the network flatness and the weight magnitude, which is, in our opinion, valuable to better understand the existing pruning algorithms and design new and more efficient algorithms.\n\n\n\n**Weakness 2: More intuitions on the theoretical results would be helpful. For example, loss flatness is one of the key factors discussed in the paper, and only its formal definition (trace of the Hessian) is given in the paper. Intuitions like smaller flatness (i.e. flatter loss landscape) means the loss function is less sensitive to perturbations in the weights would be helpful.**\n\nThank you for the suggestion. In the revised version, we will include more intuitive explanations to enhance the understanding of the paper.\n\n\n\n**Weakness 3: Inconsistencies in notations: For example, from equation (17) onwards, the loss sublevel set notation takes in the weights as the argument. Is this the same loss sublevel set defined in equation (2), which takes in epsilon as the argument? And how is the epsilon parameter chosen for the loss sublevel set?**\n\nThese are, in fact, two sublevel sets. Consequently, epsilon should be included in the sublevel set notation of Equation 17; we will correct this in the revised version. We compute the standard deviation of the loss across different batches of the training set and use it as epsilon.\n\n\n\n**Weakness 4: I would define \"pruning ratio\" earlier in the paper. It was not clear until the contributions section that smaller pruning ratios means more pruning of the network.**\n\nThanks for your suggestion, we will define pruning ratio earlier in the revised version.\n\n\n\n**Weakness 5: The authors have introduced \"pruned ratio\", which equals to 1 - pruning ratio, for Table 2. This is the only place in the paper where this term is used. This is confusing. Why did the authors not stick to \"pruning ratio\" throughout the paper?**\n\nGood suggestion, we will change it to \"pruning ratio\" in the revised version.\n\n\n\n**Weakness 6: Please consider removing adjectives like \"powerful\" when describing convex geometry and approximate kinematics formula, or \"very tight characterization.\" They are subjective and do not add much to the clarity of the paper.**\n\nWe will correct this in the revised version.\n\n\n\n**Weakness 7: Some typos like \"Lottery Tickets Hypolothsis\" (line 77)**\n\nThanks for pointing out this, we will correct typos in the revised version.\n\n\n\n**Weakness 8: Some terms like SLQ (line 82) are not defined until later in the paper.**\n\nWe will define SLQ before using in the revised version.\n\n**Question 1: What is novel here in light of prior work showing results connecting Gaussian widths to recovery thresholds [4]?**\n\nRef.[4] and our work share the similarity that they take advantage of convex geometry to characterize the threshold of given inference or learning problems. The main difference between them lies in:\n\n1) Our work extends significantly the application of convex geometry from a specific inference problem to a general learning problem: Ref. [4] addresses in specific the recovery threshold of the *linear* inverse problem, which is a classical statistical *inference* problem. On the other hand, our work tackles a statistical *learning* problem which is of general DNN architecture and *arbitrary loss function*. The methods and results in Ref. [4] just cannot be simply translated to the  problem we address in our work.\n\n2) The threshold in our work is normally *sharper* than Ref. [4]: Ref. [4] utilizes the Gaussian width to characterize the recovery threshold, which unfortunately can only provide the lower bound (*necessary condition*) since the key result Ref. [4] relies on, i.e. Gordon's escape through a mesh theorem only provide the necessary condition.  In contrast, our work leverage the statistical dimension framework and the accompanying approximate kinematic formula, whose necessary and sufficient condition almost coincides, thus capable of providing sharp thresholds.\n\n\n**Question 2: How sensitive are the theoretical bounds to the choice of loss function? Do the results generalize across different loss functions commonly used in deep learning?**\n\nOur theory only concerns the pruning limits of well-trained models and does not address the loss function during the training process. In other words, our theoretical results apply to one-step pruning for all well-trained models.\n\n\n\n**Question 3: How computationally expensive is the proposed spectrum estimation algorithm compared to existing methods? Is it practical for very large networks?**\n\nIn fact, our proposed improved algorithm introduces only a modest increase in computational complexity compared to existing methods. For instance, with a fixed sample size of 100, it requires more computation of only 200 derivatives.  These computations do not necessitate the use of the entire dataset and can be performed on a subset. Furthermore, for very large networks, the improved algorithm provides a more accurate estimation of the eigen spectrum.", "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": "", "extra_scores": {}}, {"review_id": "qDPi6DYd1y", "reviewer": "Reviewer_byyM", "summary": "This paper leverages the framework of statistical dimension in convex geometry to characterize the sharp phase transition point, i.e., the fundamental limit of the pruning ratio. Two key factors are found to be important for pruning, weight magnitude and network flatness. The flatter the loss landscape or the smaller the weight magnitude, the smaller pruning ratio. The theoretical analysis also aligns well with the empirical results, demonstrating the effectiveness of the theory proof.", "questions": "Please see the above weaknesses.", "limitations": "Provided.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The powerful approximate kinematics formula in convex geometry is leveraged to provide a very tight characterization of the fundamental limit of the network pruning. \n\n2. It is quite impressive to see the theoretical results perfectly coincide with the experiments. \n\n3. Moreover, the theoretical study can be explored to two common tricks in pruning, gradually pruning and $l_2$ regularization in Rare Gems.\n\n4. Code is provided.", "weaknesses": "1. One thing that sounds strange to me is that one conclusion is that \"The smaller the network flatness (defined as the trace of the Hessian matrix), the more we can prune the network\", which is contrary to the previous common belief, i.e., the flatter the network's landscape, the easier to be pruned. https://arxiv.org/pdf/2205.12694. Could the authors clarify these two counterarguments?\n\n2. While the theoretical proof looks sound, the empirical results in this paper look strange to me.  For instance, it is weird to see that the accuracy maintains the same at a 100% pruning ratio, but drops significantly as it goes below 2%. Does the pruning ratio here stand for a different thing than the common definition, i.e., the ratio of weights that are zero?\n\n3. Can the authors explain why RN50 achieves worse accuracy than RN18 on TinyImageNet? \n\n4. Which pruning algorithm is used for Figure 3? It is surprising to see that we can preserve the original performance at 2% ratio, for RN50 on TinyImageNet.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1: One thing that sounds strange to me is that one conclusion is that \"The smaller the network flatness (defined as the trace of the Hessian matrix), the more we can prune the network\", which is contrary to the previous common belief, i.e., the flatter the network's landscape, the easier to be pruned. https://arxiv.org/pdf/2205.12694. Could the authors clarify these two counterarguments?**\n\nThank you for the insightful question. We should indeed use sharpness (defined as “trace” of the Hessian matrix), where smaller sharpness corresponds to greater pruning. This definition will be adopted in the revised version to avoid confusion.\n\n**Weakness 2: While the theoretical proof looks sound, the empirical results in this paper look strange to me. For instance, it is weird to see that the accuracy maintains the same at a 100% pruning ratio, but drops significantly as it goes below 2%. Does the pruning ratio here stand for a different thing than the common definition, i.e., the ratio of weights that are zero?**\n\nWe define pruning ratio as the proportion of remaining weights, 100% means no pruning is performed.\n\n**Weakness 3: Can the authors explain why RN50 achieves worse accuracy than RN18 on TinyImageNet?**\n\nI am not sure which data the accuracy refers to in this context. If it refers to the test accuracy of the network, then Table 9 shows that the accuracy of RN50 is higher.\n\n**Weakness 4: Which pruning algorithm is used for Figure 3? It is surprising to see that we can preserve the original performance at 2% ratio, for RN50 on TinyImageNet.**\n\nWe first train the RN50 model with L1 regularization on TinyImageNet. Following the training, we prune the network by removing the smaller weights. Details of the hyperparameters used during training are provided in the appendix. Additionally, a comparison of the pruning algorithms is included in the appendix. Since L1 regularization-based magnitude pruning is not new technique and not the primary focus of this paper, we have placed it in the appendix.", "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": "", "extra_scores": {}}, {"review_id": "pjVT21rxsB", "reviewer": "Reviewer_LoL3", "summary": "The authors build on the work of Larsen et. al. [1]  to estimate the fundamental limit of pruning i.e the smallest achievable density of a network by pruning. This is done by estimating the statistical dimension of the neural network and leveraging convex geometry.\nSimilar to Larsen et. al. [1] the authors provide a lower bound on the smallest density i.e. the sparsest parameter set that still generalizes well. They also provide an upper bound of this density, showing that such a dense network exists.\nThe authors provide computational methods to estimate these bounds reasonably for a neural network and empirically validate them. \nOverall, the work provides a theoretical characterization of the pruning limit of a network.", "questions": "See above.", "limitations": "This paper provides a theoretical framework to estimate the pruning limit of a neural network, building on recent work in this direction by Paul et. al. [2] and Larsen et. al. [1] via a convex geometry viewpoint, which can potentially be a useful contribution to the sparsity community.\nI am happy to increase my score further if my concerns are sufficiently addressed.\n\n\n[1] Larsen, Brett W., et al. \"How many degrees of freedom do we need to train deep networks: a loss landscape perspective.\" International Conference on Learning Representations. 2021.\n\n[2] Paul, Mansheej, et al. \"Unmasking the Lottery Ticket Hypothesis: What's Encoded in a Winning Ticket's Mask?.\" The Eleventh International Conference on Learning Representations. 2022.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed bounds validate that flatter networks allow more parameters to be pruned as well as the use of magnitude based parameter pruning which has consistently outperformed other pruning criteria.\n2. Algorithms to compute these bounds are also provided and empirically validated.\n3. Experiments across image classifications tasks are provided which align with the computed limits on pruning.", "weaknesses": "1. The analysis of Figure 4 is unclear to me. I cannot follow the interpretation of the provided plots to infer that iterative pruning can be beneficial. The provided plots suggest that removing a large fraction of parameters i.e. having a small pruning ratio, increases the value of R, which is not desirable according to the theory, for a dense network.\nHowever, does this also hold for a partially sparse network which is iteratively pruned like in the case of IMP, how does pruning iteratively mitigate this trend?\n2. The authors have also not confirmed this insight via experiments with L1 regularization if iterative pruning helps over one-shot pruning. I believe the authors need to give a detailed explanation of Section 7.\n3. In addition, can the authors comment on the connection to the pruning fractions shown in Figure 4 to the observations made by Paul et. al. [2] for IMP (Figure 5 in Paul et. al. makes a similar analysis). Is there an optimal pruning fraction for an iterative method like IMP? \n\nThe use of the terms pruning ratio, pruning threshold and sparsity are interchangeably used without concretely defining them, which makes the paper difficult to follow. I would urge the authors to correct this and clarify that the pruning ratio implies the number of nonzero parameters left in the network after pruning (it seems so from the derivation?).\nThe use of sparsity is incorrect in Table 9, sparsity denotes the number of zero parameters in the network.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading and constructive comments.\n\n**Weakness 1: The analysis of Figure 4 is unclear to me. I cannot follow the interpretation of the provided plots to infer that iterative pruning can be beneficial. The provided plots suggest that removing a large fraction of parameters i.e. having a small pruning ratio, increases the value of R, which is not desirable according to the theory, for a dense network. However, does this also hold for a partially sparse network which is iteratively pruned like in the case of IMP, how does pruning iteratively mitigate this trend?**\n\nIn Fig. 4,  in fact, we do not assert that iterative pruning itself is inherently beneficial. Instead, our aim is to demonstrate that in Iterative Magnitude Pruning (IMP), the lower bound of the pruning ratio increases after each pruning iteration. When the previously set pruning ratio is less than the theoretical limit, the pruning ratio should be adjusted to avoid incorrect pruning. Consequently, fewer weights need to be pruned in subsequent iterations, leading to an adjustment in the pruning ratio. This forms the basis for the pruning ratio adjustment algorithm. \n\n\n\n**Weakness 2: The authors have also not confirmed this insight via experiments with L1 regularization if iterative pruning helps over one-shot pruning. I believe the authors need to give a detailed explanation of Section 7.**\n\nWe did not compare the performance of iterative pruning with one-shot pruning directly. Instead, our objective is to use our theoretical results to elucidate why iterative pruning requires adjustment of the pruning ratio. Additionally, we aim to explain why, in some iterative pruning algorithms, the use of regularization versus no regularization can lead to discrepancies in the final performance of the sparse network.\n\n\n**Weakness 3: In addition, can the authors comment on the connection to the pruning fractions shown in Figure 4 to the observations made by Paul et. al. [2] for IMP (Figure 5 in Paul et. al. makes a similar analysis). Is there an optimal pruning fraction for an iterative method like IMP?**\n\nFigure 4 in our paper and Figure 5 in Paul et al. utilize the same theoretical results to illustrate that in Iterative Magnitude Pruning (IMP), the network cannot be pruned to the target sparsity directly, necessitating iterative pruning. In contrast, our paper shows that after each pruning step, the lower bound of the pruning ratio increases, indicating that the pruning proportion must be adjusted in iterative pruning. The determination of the optimal pruning ratio for iterative methods is an intriguing research question, and we are actively exploring this area.\n\n\n\n**Weankness 4: The use of the terms pruning ratio, pruning threshold and sparsity are interchangeably used without concretely defining them, which makes the paper difficult to follow. I would urge the authors to correct this and clarify that the pruning ratio implies the number of nonzero parameters left in the network after pruning (it seems so from the derivation?). The use of sparsity is incorrect in Table 9, sparsity denotes the number of zero parameters in the network.**\n\nThanks for your suggestion, pruning ratio and sparsity imply the number of nonzero parameters left in the network after pruning and we will correct those in the revised version.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the prunability of a deep neural network using convex geometry. The main technical tool is the Approximate Kinematic Formula, which characterizes the sharp phase transition between the cases when two convex sets intersect with probability 1 or probability 0, given the two sets' statistical dimensions. This phase transition is then used to obtain the upper and lower bounds of prunability. The bounds using statistical dimensions are converted to a computable bound using Gaussian width. The authors used this bound to find two key contributing factors for prunability, including weight magnitude and network flatness. Then, it was shown that the upper and lower bounds are close to each other when networks are trained with L1 regularization and one-shot magnitude pruning.

There are several reasons that motivate most reviewers (including me) to accept this paper. First, using tools from convex geometry to study prunability is novel. Second, the theories provide insights into important factors to improve network pruning, such as flatness. Finally, the bounds are non-vacuous in specific scenarios, and there is a good alignment between theory and experimental results. While reviewers are concerned with the L1 regularization used in the loss function when the upper and lower bounds are close, I believe this just needs to be stated clearly in the paper. I believe the paper can be improved by stating the assumptions more clearly and perhaps downplaying the "fundamental limit" part slightly. The reviewers also provided other useful suggestions to improve the paper, including comparison with reference [4] and stating the "pruning ratio" clearly.
Decision: Accept (poster)