How Much Pre-training Is Enough to Discover a Good Subnetwork?
Authors: Cameron R. Wolfe
Fangshuo Liao
Qihan Wang
Junhyung Lyle Kim
Anastasios Kyrillidis
Venue: Accepted by TMLR ()

Abstract: Neural network pruning helps discover efficient, high-performing subnetworks within pre-trained, dense network architectures. More often than not, it involves a three-step process—pre-training, pruning, and re-training—that is computationally expensive, as the dense model must be fully pre-trained. While previous work has revealed through experiments the relationship between the amount of pre-training and the performance of the pruned network, a theoretical characterization of such dependency is still missing. Aiming to mathematically analyze the amount of dense network pre-training needed for a pruned network to perform well, we discover a simple theoretical bound in the number of gradient descent pre-training iterations on a two-layer fully connected network in the NTK regime, beyond which pruning via greedy forward selection \citep{provable_subnetworks} yields a subnetwork that achieves good training error. Interestingly, this threshold is logarithmically dependent upon the size of the dataset, meaning that experiments with larger datasets require more pre-training for subnetworks obtained via pruning to perform well. Lastly, we empirically validate our theoretical results on multi-layer perceptions and residual-based convolutional networks trained on MNIST, CIFAR, and ImageNet datasets.

Published in Transactions on Machine Learning Research (02/2024)
How Much Pre-training Is Enough to Discover a Good Subnetwork?
Cameron R. Wolfe" Deportment of Computer Science Rice University
crw130rice.co
Fangshuo Liao"t
Tanngshuo.LiaoSee Orice. edu
Deportment Computer Science
Rice University
Qihan Wang Department of Computer Science
Chuck. Wang edu
Rice University
Junhyung Lyle Kim
jlylekim Orice. edu
Department of Computer Science Rice University
Anstassos Kyrillidis
mastasios@rrcce.eee
Department of Computer Science Rice University
Reviewed OpenReview: /ttps://openreviite net/ forum? id= UVE7LlpXee
Abstract
Neural network pruning helps discover efficient, high-performing subnetworks within pre- Irained, dense network architectures. More often than not, it involves a three-step process- pre-training, pruning, and re-training that is computationally expensive, as the dense model must be fully pre-trained. While previous work has revealed through exper- iments the relationship between the amount of pre-training and the performance of the pruned network, theoretical characterization of such dependency is still missing. Aiming to mathematically analyze the amount of dense network pre-training needed for pruned network to perform well, we discover a simple theoretical bound in the number gradient descent pre-training iterations on a two-layer fully connected network in the NTK regime, beyond which pruning via greody forward selection (Ye et al., 2020) yiclds a subnetwork that achieves good training error. Interestingly, this threshold is logarithnically dependent upon the size of the dataset, meaning that experiments with larger datasets require more pre-training for subnetworks obtained via pruning to perform well. Lastly, we empirically validate our theoretical results on multi-layer perceptions and residual- based convolutional networks trained on MNIST, CIFAR, and ImageNet datasets.
1 Introduction
Neural network pruning refers to dropping weights in large neural network without significantly degrading the model's performance. It has been widcly applied to model compression (Anwar et al. 2015 Liang al.
2021
2023 Blalock et al.] 2020). Neural network pruming usually involves three steps: i) pre- training, where a large, randomly initialized neural network is trained on a dataset to reach a certain test
Li et al.]
"Equal Contribution *Corresponding Author

---

Published in Transactions on Machine Learning Research (02/2024)
accuracy; di) pruning, where subset of the neural network weights are dropped; and dit) re-training, where the pruned neural network is trained again to maintain the desired accuracy. While some methods perform only a subset of these steps, most existing algorithms include at least the pre-training and pruning phases.
The above three-step procedure mainly originates from the prominent line of work of the Lottery Ticket
Hypothesis (Frankle & Carbin 2018: Chen et al. 2020 Frankle et al. 2019 Gale et al. 2019 Liu et al.
2018 Morcos et a 2019 Zhhu al. 2019 Zhu & Gupta 2017) (or LTHH:: i.e. the idea that a pre-trained model contains "lottery tickets" (i.c., smaller subnetworks) such that if we select those "tickets" cleverly, those submodels do not lose much in accuracy while reducing significantly the size of the model. To circumvent the cost of pre-training, several works explore the possibility of pruning networks directly from initialization (i.e., the "strong lottery ticket hypothesis") (Frankle et al. 2020 Ramanujan et al., 2019 Pensia et al. 2021 Xiong et al., 2022), but subnetwork performance could suffer. Adopting a hybrid approach, good subnetworks can also be obtained from models with minimal pro-training (Chen et al. 2020 You et al. 2019) (i.e., "carly-bird" tickets): i.c., the pre-training stop, though indispensable, needs to be exocuted for only a small extent before the pruning step can find a small model that. performs well (namely the winning ticket). This line of work further promoted the application of pruning algorithms to large neural networks. However, despite its strong support from empirical observation, the relationship between pre-training and pruning has never been examined theoretically, even for simple neural architectures.
This paper aims to fill this gap by bridging the theory of neural networks trained with gradient descent and the greedy forward selection pruming algorithm. Our analysis focuses on a two-layer neural network with initialization and over- parameteriizztinnn in the NTK regime. From this analysis, we discover a simple threshold in the number of pre-training iterations- logarithmically dependent upon the size of the dataset- beyond which subnetworks obtained via greedy forward selection perform well in terms of training error. Such a finding offers a theoretical insight into the carly-bird ticket phenomenon and provides intuition for why discovering high-performing subnetworks is more difficult in large-scale experiments (You et al. 2019 Renda
ct al.
2020 Liu ct al. 2018). In particular, our contributions can be summarized as below:
Based on the analysis of Ye et al. (2020), our Lemma serves as an improvement over the proof in Ye ct al. (2020]: Our proof shows that the greedy forward sclection error depends on both the initial selection
error, the maximun distance of neuron separation, and the loss of the current dense neural network
pruning time. In particular, the greedy forward selection error has O 001 [logk) dependency on the first
two terms, where k is the number of neurons selected.
By analyzing the neural network weight change during training, we find out that the initial selection error and the maximum distance of neuron separation can be bounded by O (VN) throughout training. This implies that the effect of the two terms can be mitigated as long the number of selected neurons satisfies k = Ω VN log VologN).
Lastly, we connect the training loss of the dense neural network at pruming time with the existing theory that characterizes the convergence of neural network training loss. We derive that, to choose k neurons in the greedy forward selection, it is necessary to perform at least O (log pre-training steps to guaranlee improvement during the greedy forward selection. Therefore, our result identifies the connection between the number of pro-training steps required and the target loss after pruning.
2 Background and Problem Setup
Notation. Vectors are represented with bold type (e.g,, x), while scalars are represented by normal type (e.g., x). I/- represents the Ea vector norm. For a function ø : R + R, we use |l x to represent the Hermite norm of & (see Definition 4 of [Song et al. (2021)) ). [N] is used to represent the set of positive integers from to N (i.e., [N] = NJ).
Network Parameterivation. We consider a two-layer neural work with N hidden neurons for simplicity. In particular, given an input vector x E Rd, the activation of the i-th hidden neuron, a (-,0,), is given by:
(x, 0.) = N 1.0+ (aT (aTx).
(1)
2

---

Published in Transactions on Machine Learning Research (02/2024)
Here, 0+ is the activation function. The weights associated with the i-th neuron are concatenated into 0, = (,,a:]] where a, E IR is the first. layer weight, and by E R is the second layer weight. Given input the neural network output f (x, ()) can be viewed as the average of the hidden neuron's activation:
N
Σ o 0.). 0(x = N
1
(2)
where 2 (01.
ON} represents all weights within the two-layer neural network. Two-layer neural networks with the form in (2 have been studied extensively as simple yet representative instance of deep
learning models (uu et al. 2019 Oymak & Soltanolkotabi 2019 Song et al. 2021
In this paper, we shall consider the scheme of neuron pruning. In particular, a pruned network defined by a subset of the hidden neurons S [N] as:
fs (x) = S
Ex(xx0))
(3)
iES
As special case, we note that the whole network can also be written as f(x, 0) [x θ). We make the following assumption about the neural network:
Assumption 1. (Neural Network) There exist 8 > 0 and some 71 R, such that o (0) 0, O S 1. 1o4(() S ö and (-)l S 6, T=h (=1o(aa)] s |o+(Ta)) S T² (o)(1a) for all E I and T (0, 1), and ||o+|l < co for a+ defined in [.. Moreover, before pre-training, the weights of the neural network are initialized according to by ~ N (0,wf) and a, ~ (0,, for some Was wb > O.
Compared with the assumption on the activation function (Song et al. 2021 we added the additional assumption (+)( S An example of the activation function that satisfies Assumption [ is the tanh(.)
function. While ReLU is also used widely in practice, in this paper we focus on the family of bounded
smooth activation functions for the simplicity of the analysis, as in previous works Liu et al. (2021) Song
et al. 20210;
Liu et al. (2023).
Dataset. We assume that our network is modeling a dataset = {(x) "ل)ر"" with m input- pairs, where x, Rd and y R for each j [m] satisfy the following assumption: Assumption 2. (Data) The input and label of the dataset are bounded ||x}|12 for all Σ 1
[m]] and
For a given network fs (x, θ), we consider the b norm regression loss over the dataset:
c [ls( (Js (x,, ) - -1²)²
(4)
At pre-training, we use gradient descent (GD) over c to minimize the whole network loss L[f(, θ)]
O - - Vo O.)].
(5)
During pruning, will track how the subnetwork loss L [fs(, θ)] changes we change the hidden neuron subset S. We will discuss this in more detail in the section below.
3 Pruning with Greedy Forward Selection
In this section, we focus on specific and straightforward algorithm adopted in the pruning stage, namely the Greedy Forward Selection proposed by Ye et al. (2020) (see Algorithm D Since the neural network weights are fixed in the pruning stage, our discussion in this section will assume a set of given weights e. Starting from an emply subnetwork (i.e., S = 0), we aim to discover a subset of neurons S* given by:
S mrg Lifs (:, O)]; |S < N. SC(N]
(6)
3

---

Published in Transactions on Machine Learning Research (02/2024)
Instead of discovering exact solution to this challenging combinatorial optimization problem, Algorithm is used to find an approximate solution. At each iteration k, we select. the neuron that yields the most significant decrease in loss. Since Algorithm [ is an approximation to the optimal solution by its nature, instead of focusing on its optimality, we will investigate the property of f[fs (-, @)] when S is returned by
Algorithm 1
Similar to Ye al. 20200, we shall consider the following interpretation from geometric perspective to provide an
A Algorithm 1 Greedy Forward Selection
analysis of Algorithm We define y [y1, y2...... ym], reprosenting concatenated vector of all labels within the dataset. Similarly, we define Φi.j = o (x,, 0:) as the out- put of neuron for the j-th imput vector in the dataset and construct the vector $;- = 1 is a concatenated vector of output activations for a sin- gle neuron across the entire dataset. The outputs of a pruned network ý = [fs (x1, fs....,ssxx,, fx((m. be viewed as convex combination of i....., ΦN. We use My to denote the convex hull over such activation vectors for all N neurons, and, with slight abuse of notation, use Vert(MM) to denote the set of neuron outputs i, . Notice that Vert(Mx) must cover the vertices of MN:
1: So 0
2: for k = 1.2.... do
3:
# Select a new neuron
4:
4 == arg min & [ss. θ)]
iE[N]
which
5:
# Add neuron to the subnetwork
6:
= U {ix}
7: end for
O]] can then
8: return S
My Conv (0. : [N];: Vert(MN) = (8. [N]]
(7)
Intuitively, My forms marginal polytope of the feature map for all neurons in the two-layer network across every data point. Using the construction MN, the lz loss can be written as follows:
(z) = マ z - yl z MN.
(8)
With this geometric interprelation of the neural network output, we can relax the combinatorial problem in c to mingeMy ((z). Moreover, using this construction, we can write the update rule for Algorithm
as:
(Select new neuron): q arg min e l (Zk-1 + 9))
(9)
(VVert(M..)
(Add neuron to subnetwork): 2s 2 + q
(10)
(Uniform average of neuron outputs): Ug 1/2 Zz.-
(11)
In words, 9 9 include the output of a new neuron, given by qe, within the current subnetwork at cach pruning iteration based on a greedy minimization of the loss E(-). Then, the output of the pruned subnetwork over the dataset at the k-th iteration, given by ug, is computed by taking a uniform average over the activation vectors of the & active neurons in Zk. From this perspective, we have that u, = [fs, (x1, o),... Ss, (Xm: θ) Notably, the procedure in (9) [1 can select the same neuron multiple times during successive pruming iterations. Such selection with replacement can be interpreted as a form of training during pruning multiple selections of the same neuron are equivalent to modifying the neuron's output layer weight b, in ① Nonetheless, we highlight that such "training" does not violate the core purpose of pruning: we still obtain a smaller subnetwork with performance comparable to the dense network from which it was derived.
4 How Much Pre-training Do We Really Need?
As previously stated, no existing thcoretical analysis has quantified the impact of pre-training on the per- formance of a pruned subnetwork. Here, we consider this problem by exlending analysis for pruning via greedy forward selection to determine the relationship between GD pre-training and subnetwork train- ing loss. For the convenience of our analysis, for a fixed set of neural network weights θ, we define DMN maxu,veMy - Our first lemma characterizes the training loss convergence during the pruning phase based a general neural network state.
4

---

Published in Transactions on Machine Learning Research (02/2024)
Lemma 1. Fir the weights O of the two-layer newral network f(: .) defined in generales the sequence {St [Sk)k=1 co
Then, Algorithm
k= satisfying
Llfs. (:. []]
1 Lfs. (s 0)] + 1 log k
D My (lf
k-1
(12)
2k
Proof. The idea is similar to Ye et al. 2020 To start, define q and un follows:
q
arg min (Vl (u u (zx-1
u
Since q is the minimizer of a linear objective in a polytope, we must have that q E Vert (Mx). Therefore, by and 10), and due to the optimality of qe; we must have that:
e {(us) = L ( (z=-1 + qu)) < l ( + = = (('().
We further notice that the objective in is quadratic. Therefore, we have:
l (ux) S El (u/)) = (ux-1) + (Vé (ux-1) u'c - uu=1) + 2 llu u u 112
(13)
8-1 Moreover, 11 implies u': - U k u + x 1/ us-1 = (qk - uk-1). Therefore 13
becomes:
8 (ux) < E (ux-1)+ + k
( (u 9le - - + 2k
l1 u 1
(14)
Again, since the objective in 8 is quadratic, we must have that is convex. Therefore:
min MEMx
8 (u) z min {((u=1)) + (VE(ux))) u - u
uE
z (ux-1) + (Vi (u=-1): 9k u
Since ý [f(x1, θ),.................. ... f(xm θ] = n E $ MN. we must have that:
N
L (,, θ)] = (9) 2
min
(u) 2 E (u=-1) (ve( ---
(15)
uEMy
Plugging
15 into 14 and noticing that |عgh - u 1 S DDN gives:
1
1 l ((uk-1)
8 (ux) - [[f ())
1
k [ (: θ) + 21
DMN L[s (, ())
k
1
1
- L (: 0)]) + DM Lf
(e
k
21
Unrolling the iterates gives:
e - (1) (.)
S
II
1
1)
(e (e - -(f((
D2
MM
k
II
(1-
k.
2
t=1
1=1
j=
k
1
DM
(e(u:) - ([f(,))))
2
k
2
j
j=++
DM 2k
(l(u)) Clf ()))
+ log k DAAN
(e(ur) CIf( 0))) + < k
2k
This shows that:
(u)) < - (uj) + 1 log &
+ k --1
DMy
k
2k
k
Plugging in L [[Ss, [)]] (ux) and L [ss (: 0 (u:) gives the desired result..
5

---

Published in Transactions on Machine Learning Research (02/2024)
Lemma characterizes the pruned network loss using combination of three terms. Notably, the first and second terms decrease the number of greedy forward selection steps k grows. In the limit of k - 0o, the pruned network loss C [fs, (-, ")] decreases to the loss achieved by the dense network & (-. O)] However, to guarantee the sparsity of the pruned network, we need the first and second terms in 12 to decrease to a meaningfully small scale within moderale number of greedy forward selection steps. This requires us to provide an upper bound of both C [fs, (., [)] and DMN-
Remark. Although our proof takes similar strategy in Ye et al. 2020 it should be noted that the proof in Ye et al. 2020 has issue that leads to incorrect result leads to secmingly worse bound compared with Ye ct al. (2020).
Our proof fixes this issue, which
4.1 Bounding Initial Pruning Loss and the Diameter
In this subsection, shall focus on the upper bound of & [fs, (s, [)] and DMY Recall that define DMx = maxu.veMN ||u vll2- Since Mx is defined as the convex hull over I,,..., DN we can show the DMx can be controlled by the maximum difference between two vertices. We formulate this idea in the lemma below.
Lemma 2. Let D' = max |1; B,l12- Then we have D' 2 DMN-
Since this is a standard result for convex polytope, we defer the proof to Appendix A By Lemma 2 to provide an upper bound on DaNs it suffice to bound D'. Applying the triangle inequality, we can upper bound D' by
+ + 112) S 2 max 1 D' max (1 [JE[N]
RE[N]
Recall that + is the hidden neuron output over all input vectors. Therefore, | depends the weight of the neural network. However, to further incorporate the loss dynamic of the pre-training into the analysis, we have to develop a universal upper bound on || for all weights in the trajectory of the gradient descent. With sufficient over- paraamettteiiinnnn, we can bound [ at any time step of the gradient descent pro-training.
Lemma 3. Let Assumplion and Assumption hold with wn o m 4). Lel $ 11,...y &N be the hidden neuron outputs defined over any neural network weights O = o for t = 1,2..... If the number of neurons N = 9 x3
m 2I- (,, 0o))²). then with high probability we have that || S CaNt for some
(f
constant C3 0.
Proof. Let C denote the outputs of neuron i for the whole dataset arbitrary time step during the pre-training. That is, for arbitrary t, consider o = lo Oit) (Xm 02.)]. Then we have that:
1 =
Σ
(x), 0in)
I m max lo (xj, Oi.)l- sE(m]
(16)
Recall that (xy, 0,,)) = Nb (aT,x)).
By choice of a+ in Assumption must have that |o+ (aT,x,) $ 1. Therefore, 116 becomes:
1 S / MN [ial-
(17)
It boils down to bounding [b,el We use the following decomposition:
1b, S |broo + 16,,- - by,ol
Since bi, N (0, wr), with high probability we have that | S Caws for some constant C4. To bound (bi, bool, we use the argument that the weight perturbation small when the over-parameteriiation is
In the proof of Proposition in Ye et al. 2020 on page 16, the equations after Equation (16) use an incorrect unrolling of the iterative upper bound.

---

Published in Transactions on Machine Learning Research (02/2024)
large, as follows. We first need to upper-bound the gradient. To start, the gradient with respect to b, be written as:
Oc [f][ (1)
Σ (x), θ₂ - my)) 0+ (aT,x)).
ab;
By the choice of our activation function, have 0+ (2)xx S 1, and further:
0C (: +.)
m
(x O vu vm y1l2= vmLl/ ( (,)
ab;
==1
This implies that
0C 0C (.
16, boo
16,,+1
6 17
S nv m Σ clf((,
Ōb:
By Theorem
we have that:
M
(1 CinN
T=0
< <.
2 Aa
x CInNA
C (1, 0,)
min
Thus we have:
1i. biool S smmm CinNA Lif 0.)]
2
2/m
LIf (., 0u)
CINA
When N = 2 ((
m² Llf (., (o)))) we have that C.NX man
2
[If(,,o)) C2m - for some constant
C2 > O. Therefore, with high probability, lball can be bounded as:
- s Cym-tN-2 [b,cel S |br,ol + |bs, - b.ool S Caws + Cym fim-& - = +
by letting C3 = C2 + C4. Plugging the bound of [bs,el into 17 we have:
| VmN Cym N c
Since each 6,00 are initialized with zero-mean, we must have that Ee, [f (.. 0o) 0. Therefore, the expected
loss initialization be computed as Ee, [ (., 0o)] Ee. || (X, . Ily Using the inde- pendence between b 's and the boundedness of the activation, we can compute that Es, [[If (X, eo) s
ET E. [b, s 0(1) when Wa s O (mm-4 3) as assumed in Lemma 3 This implies that with a m
high probability [[f (., @o)] = 0(1) and the overparameterization requirement reduces to N With an established bound of || [1 we can provide a bound for both DMx and & [Js, (. (.)]-
x
Theorem 1. Let Assumption 1 and Assumption hold. Let MM be the polytope formed by neuron outputs from the pre-trddeed network with gradient descent. I Ω we have that:
m²
L (., on))²) then with high probabilily,
main
DMN 0 (Nt): ClSs, (s 0.) 50 (VNV

---

Published in Transactions on Machine Learning Research (02/2024)
Proof. To show the upper bound on DM directly apply Lemma B and Lemma to get that:
Pill2 S 2C =0 - (N+).
DMN D 2 max E
To show the upper bound on C [[s, (:, [.)], we let 8" E be given. Then it. holds that:
C [iss, (: 0.)] c y1l2 - (1) [1 ll 11yl22) S -.- + 1lyl
By Assumption 2 have that |yyll2 1. Morcover, by Lemma 3 we have that || 12 SCNi, Therefore,
we have:
C Lfs.. (. (.)) S CVV +1 (C) + 1)vN o (VN).
Under the sctting of Theorem
1 the training loss convergence during the pruning phase Lemma becomes:
1 1 log DMN
k k-1
[[fs, 0]] [fs, (s [)]
+
Llf ())(:))) O)
2k
s h 0 (VN)
1 + log k
0 (Nt)
+ k - (.)
2k
-0(1g
log k
+ k k [[)(:
=0
VN
k
In this scenario, Lemma shows a O (logt) decay of the loss on the pruned neural network, up to the loss achieved by the dense neural network. Additionally, because Algorithm iteration, must have [S&] I k. In order to guarantee that L (s θ)] S c L if []]] for some >> 0, K VN Se to obtain that k= 0 VN Wo (
I selects single neuron during each
enforce log
AN )) where Wo(-) is the Lamber W function.
Further applying that Wo(x) < log gives that the resulting subnetwork satisfies the sparsity constraint [Syl = VN log vN) This shows that greedy forward selection can obtain an error close to L[f O)]
in with small sparsity. In the next soction, we proceed investigate how L [f (.]) evolves during the pre-training phase.
4.2 Connecting with Pre-training Loss Convergence
By leveraging the recently developed result of neural network training convergence (Liu et al. 2021 we can extend Lemma ! with the following upper bound on the dense neural network loss after pre-training To state the result, we first define the network-related quantity Amnn and Amax as follows
Definition 1. Consider the first-layer output matrix at initialization E R Nxm given by Vij = a+ (a.ox;).
We define Amin V mmin (T) and Amax VN max (V)
It is hard to provide a precise lower bound on Amin, but we can estimate its scale using the following reasoning. Since a;,0 ~ N (0, TQ)) are Gaussian random vectors, the pre-activation values aTox; follows a Gaussian distribution. Moreover, the activation function a (-) further "squeezes' the value into the interval [-1,1]. Therefore, when Wa is large enough, a+ (aTo>;) behaves similar to Gaussian distribution with
constant variance. Since E Nxm standard random matrix theory shows that amin (V) =
VN with
high probability when m is fixed. Therefore, we estimate that Amin (1). In Appendix we provide experimental results to verify that Omiu ( -
(VN).
Theorem 2. Let Assumption 1 and Assumption
2 hold with Wowr S O (aN where d is the inpu dimension,
and that a two-layer network of width N = Ω
m 3
L [ (.. (o))2) was pre-trained for ilerations with gradient
8

---

Published in Transactions on Machine Learning Research (02/2024)
Let O denote the weights at initialization. If choose the step then the sequence (Sk generated by applying Algorithm to size 17 O vm [+ +NAama
descent in (5) over dataset D of size
the pre-trained nelwork salisfies:
log k
L (s, 6.) 50
VNJ min
Jor some consland C 0.
Since the proof only involves applying the existing characterization of the training convergence in Song et al. (2021) to the bound in Lemma ! we defer the proof to Appendix B Notice that the loss in Theorem 2 only decreases during successive pruming itcrations if the rightmost term does not dominate the expression, i.c., all other terms decay O training loss deteriorates, thus eliminating any guarantees subnetwork performance. Interestingly, we discover that the tightness of the upper bound in Theorem 2 depends on the number of dense networks pre-training iterations.
logk If this term does not decay with increasing k, the upper bound on subnetwork k
Theorem 3. Adopting identical assumptions and notation as Theorem & assume the dense network is pruned via greedy forward selection for iteralions. The resulling subnelwork is guaranteed to achieve training loss O 0 logk .N) if the number of gradient descent pre-training iterations the dense network- the following condition:
- log k
where C₁ is a positive constant.
(18)
log CinN X
Otherwise, the loss of the pruned network not guaranteed to improve over successive iterations of greedy forward selection.
Proof. From Theorem 3 one can observe that the term O log vN) dominates only when:
("ng+
log
VN 2 (1 Cnn ((f(,
k
Therefore, to guarantee that O
log
N dominates, & must satisfy:
log
VNlogk [2]
log k: log log (s, 0n) =0 log k
t log (1 N X2 X
log (1 N1
log (1 Cin Aa
since C [ff (-, 0o) is independent of k.
Theorem 3 states that threshold erists in the number of GD pre-truining iterations of a dense network, beyond which subnetworks derived with greedy selection are guaranteed to achieve good training loss. Denoting this threshold as t*. Consider the choice v in Theorem When N > m, the step size becomes 7) = This implics that the threshold of the pre-training
- -log ( (NN (N and in this case t" = 0 (og(1-C1-XM..AA_.]) steps depends on Amaz Amtz the condition number V. Since V close to a random Gaussian matrix, Amax increases as the size of the dataset m increases. This implies that larger datasets require more pre-training for discovering nigh-performing subnetworks. Our finding provides theoretical insight regarding i) how much pre-training is sufficient to discover well-performing subnetwork and ii) the difficulty of discovering high- performing subnetworks in large-scale experiments (i.e., large datasets require more pre-training).
Remark. The combination of the initialization scale requirement in Lemma 3 and Theorem 2 puts our training scheme in the so-called NTK regime (Song et al.) 2021), where the first-layer weights change only
2hhis overparameterisation assumption mild comparison previous work Allen-Zhu
2018
2019

---

Published in Transactions on Machine Learning Research (02/2024)
slightly, resulting in training dynamic similar to the random feature model. While the training in this regime prevents the model from learning useful features and thus results in poor generalization, our initialization is crucial to control the convex hull diameter DMy's 's in a reasonable magnitude. However, it should be expocted that this requirement can be relaxed if one assumes additional structure on the training data X: a sulficiently trained neural network should map the input inlo one or multiple clusters with small diameters. Future works can consider performing a more fine-grained analysis of the relationship between the amount of pre-training, the structure of the data, and the diameter of the hidden output of the pre-trained network.
5 Related work
Many variants have been proposed for both structured Han et al. 2016 Li et al. 2016 Liu et al. 2017 Ye
ett al. (020) and unstructured (Evci et al. 2019 2020 Frankle & Carbin 2018 Han et al., 2015) pruming.
Generally, structured pruning, which prunes entire channels or neurons of a network instead of individual weights, is considered more practical, as can achieve speedups without leveraging specialized libraries for
sparse computation. Existing pruning critcrion include the norm of weights [Li et al. 2016 Liu ct al. 2017).
feature reconstruction error (He et al.; 2017 Luo et al.] 2017 Ye et. al. 2020 Yu el al. 2017), or even
gradient-basel sensitivity measures (Baykal et al. 2019 Wang et al., 2020; Zhuang et al. 2018 While most
pruning methodologics perform backward climination of neurons within the network Frankle & Carbin
2018 Frankle et al. 2019 Liu et al. 2017 2018:
Yu et al. 2017 some recent research has focused on
forward selection structured pruning strategies (Ye et al.j 2020; Ye et al. 2020) Zhuang et. al. 2018) We
adopt greedy forward selection within this work, as it has been previously shown to yield superior performance in comparison to greedy backward elimination, and is a simple algorithm to apply.
Empiriaal analysis of pruning techniques has inspired associated theoretical developments. Several works have derived bounds for the performance and size of subnetworks discovered in randomly-initialize networks
(Malach et al. 2020; Orscau et al. 2020: Pensia et al.) 2020). Other theoretical works analyze pruning via
greedy forward selection (Ye et al.) 2020: Ye el al.] 2020 In addition to enabling analysis concerning subnetwork size, pruning via greedy forward selection was shown to work well in practice for large-scale architectures and datasets. Some findings from these works apply to randomly-initiallied networks given proper assumptions (Ye et al. 2020 Malach et al. [2200] Orseau et al., 2020 Pensia et al.) (0000), but, the best of our knowledge, no work yet analyzes how different levels of pre-training impact the performance of pruned networks from theoretical perspective.
Our analysis resembles that of the Frank- Wolfe algorithm (Frank et al. 1956: Jaggi 2013), widely-used and simple technique for constrained, conver optimization. Recent work has shown that training deep networks with Frank- Frank-Wolfe can be feasible in certain cases despite the non-convex nature of neural network training (Bach 2014 Pokutta et. al.) 2020). Instead of training networks from scratch with Frank- Frank-Wolfe, we use a Frank- Wolfe-style approach to greedily select neurons from a pre-trained model. Such a formulation casts structured pruning convex optimization over marginal polytope, which can be analyzod similarly to Frank- Wolfe (Ye et al.) 2020; Ye et al. 2020) and loosely approximates networks trained with standard, gradient-based techniques (Ye et al.] 2020). Several distributed variants of the Frank-Wolfe algorithm have
been analyzed theoretically (Wai et al. 2017 Xian et al.) 2021 Hou et al. 2022), though our analysis most closely resembles that of (Bellet et al. 2015). Alternative analysis methods for greedy selection algorithms
could also be constructed using sub-modular optimization techniques (Nemhauser et al. 1978).
Much work has been done to analyze the convergence properties of neural networks trained with gradient- based techniques (Chang et al.) 2020 Hanin & Nica 2019 Jacot et al.) 2018 Zhang et al., 2019). Such convergence rates were initially explored for wide, two-layer neural networks using mean-field analysis tech-
niques MMei et al.
2019
2018 Similar techniques later extended such analysis to deeper models (Lu ct al., Generally, recent work on neural network training analysis has led to novel analy-
2020 Xiong el al.)
2020
sis techniques (Hanin & Nica. 2019 Jacot et al.) 2018), extensions to alternate optimization methodologies Oymak & Soltanolkotabl 2019), and even generalizations to different architectural
(Jagatap & Hegde 2018
2018 Li & Yuan 2017 Zhang et al., 2019). By adopting such an analysis, we aim to bridge the gap between the theoretical understanding of neural network training and I.TH.
components (Goel et al.
10

---

Published in Transactions on Machine Learning Research (02/2024)
5x 10?
N 10
=0 x 10
1
5
0.95
0.90
0.85
0.80
6 0
5 8
6
(1 10")
Figure 1: Pruned, two-layer models on MNIST. Sub-plots depict dense network sizes, while the and y axes depict the number of pro-training iterations and the sub-dataset size. Color represents training accuracy, and the red line depicts the point at which subnetworks surpass the performance of the best best-pruned model on the full dataset for different sub-dataset sizes. Dashed lines are the theoretical predicted result computed based on the condition number of the random Gaussian matrices.
6 Experimental Results
6.1 Empirical Validation Two-Layer Networks
In this section, empirically validate theoretical results. Pruning via greedy forward selection has alrcady been empirically analyzed in previous work. Therefore, we focus on an in-depth analysis of the scaling properties of greedy forward selection with respect to the size and complerity of the underlying dataset. This experimental setup will better support our thcoretical result in Section 4.2 which predicts that larger datasets require more pre-training for subnetworks obtained via greedy forward selection to perform well. Experiments are run on an internal cluster with two Nvidia RTX 3090 GPUs using the public implementation of greedy forward selection
Ye 2021
We perform structured pruming experiments with two-layer networks on MNIST Deng 2012 by pruning hidden neurons via greedy forward selection. To match the single output neuron setup described in Section we binarize MNIST labels by considering all labels less than five as zero and vice versa. Our model architecture matches the description in Section with a few minor differences. Namely, we adopt a ReLU hidden activation and apply a sigmoid output transformation to enable training with binary cross-entropy loss. Experiments are conducted with several different hidden dimensions (i.e., N (5K, 10K, 20K3).
To study how dataset size affects subnetwork performance, construct sub-datasets of sizes 1K to 50K (i.e., in increments of 5K) from the original MNIST dataset by uniformly sampling examples from the ten original classes. The two-layer network is pre-trained for 8K iterations in total and pruned every 1K iterations to a size of 200 hidden nodes. After pruning, the accuracy of the pruned model over the entire training dataset is recorded (i.e., no fine-tuning is performed), allowing the impact dataset size and pre- pre-training length on subnetwork performance to be observed. Figure I shows the results averaged over three trials.
Discussion. The performance of pruned subnetworks in Figure matches the theoretical analysis provided in Scction for all different sizes of two-layer networks. Namely, as the dataset size increases, so does the amount of pre-trainéng required to produce a high-performing subnetwork. To this, one can track the trajectory of the red line, which traces the point at which the accuracy of the best-performing subnetwork for the entire dataset is surpassed at each sub-dataset size. This trajectory clearly illustrates that pre- training requirements for high-performing subnetworks increase with the size of the dataset. Furthermore, this increase in the required pre-training is seemingly logarithmic, as the trajectory typically plateaus at larger dataset sizes.
Interestingly, despite using small-scale dataset, high-performing subnetworks are never discovered ini- tialization, revealing that minimal pre-training is often required to obtain good subnetwork via greedy
11

---

Published in Transactions on Machine Learning Research (02/2024)
Pruned Accuracy
Model
Dataset Size
Dense Accuracy
20K It.
40K It.
60K It.
80K It.
10K
82.32
86.18
86.11
86.09
83.13
MobileNet V
30K
80.19
87.79
88.38
88.67
87.62
50K
86.71
88.33
91.79
91.77
91.44
10K
75.29
85.47
85.56
85.01
85.23
ResNet34
30K
84.06
91.59
92.31
92.15
92.14
50K
89.79
91.34
94.28
94.23
94.18
Table 1: CIFARIO Lest accuracy for subnetworks derived from dense networks with varying pre-training amounts (i.e., number of training iterations listed in the top row) and sub-dataset sizes. Numbers marked in bold denote the sctting where the pruned network achieves comparable performance to the dense network in the smallest training iterations.
forward selection. Previous work claims that sershperforming subnetworks may exist at initialization in thoory. In contrast, our empirical analysis shows this is not the case even simple experimental scttings.
6.2 Application to Deeper Neural Architectures
We perform structured pruning experiments (i.c., channel-based pruning) using ResNet34 He ct al. 2013 and MobileNedV2 (Sandler et al. 2018) architectures on CIFARIO and ImageNet (Krizhessky et al. 2009; Deng al. 2009). We adopt the same generalization of greedy forward selection pruning deep networks described in YYe et al. 2020 and
to denote our stopping criterion. We follow the threo-stage methodology pre-training, pruming, and fine-tuning- aanninnnnadd modify both the size of the underlying dataset and the amount of pre-training before pruning to examine their impact on subnetwork performance. Standard data augmentation and splits are adopted for both datasets.
CIFAR10. Three CIFAR10 sub-datasets of size 10K, 30K, and 50K (i.e., full dataset) are created using uniform sampling across classes. Pre-training is conducted for 80K iterations using SGD with momentum and a cosine learning rate decay schedule starting at 0.1. We use batch size of 128 and weight decay of 5- 5-10-1p The dense model is independently pruned every 20K iterations, and subnetworks are fine-tuned for 2500 iterations with an initial learning rate of 0.01 before being evaluated. We adopt 0.02 and = 0.05 for MobileNet-V2 and ResNet34, respectivcly, yielding subnetworks with a 40% docrease in FLOPS and 20% decrease in model parameters in comparison to the dense model
The results of these experiments are presented in Table The amount of training required to discover a high- performing subnetwork consistently increases with the size of the dataset. For example, with MobileNet winning ticket is discovered the 10K and 30K sub-datasets in only 40K iterations. In comparison, for the 50K sub-dataset, a winning ticket is not found until 60K iterations of pre-training have been completed. Furthermore, subnetwork performance often surpasses the fully-trained dense network without completing the enlire pre-training procedure.
ImageNet. We perform experiments on the ILSVRC2012, 1000-class dataset (Deng et al. 2009 deter- mine how pre-training requirements change for subnetworks pruned to different FLOP levels We adopt the same experimental and hyperparameter settings as Ye et al. (2020). Models are pre-trained for 150 epochs using SGD with momentum and cosine learning rate decay with an initial value of 0.1. We use a batch size of 128 and weight decay of 5 10-4 The dense network is independently pruned every 50 epochs, and the subnetwork is inn-tuned for 80 epochs using a cosine learning rates schedule with an initial value of 0.01 before being evaluated. We first prune models with 0.02 and = 0.05 for MobileNet and ResNet34,
"Our pre-training settings adopted from popular repository for the CIFAR10 dataset Liu 2017
"These settings are derived using grid scarch values of and the learning with per performance measured over
hold-out validation set; Appendix [ 5 We do not experiment with different sub-dataset sizes on ImageNet due to limited computational resources.
12

---

Published in Transactions on Machine Learning Research (02/2024)
FLOP (Param)
Pruned Accuracy
Model
Dense Accuracy
Ratio
50 Epoch
100 Epoch
150 Epoch
60% (80%)
70.05
71.14
71.53
MobileNet
71.70
40% (65%)
69.23
70.36
71.10
60% (80%)
71.68
72.56
72.65
ResNet34
73.20
40% (65%)
69.87
71.44
71.33
Table 2: Test accuracy on ImageNet of subnetworks with different FLOP levels derived from dense mod- els with varying amounts of pre-training (i.e., training epochs listed in the top row). We report the TT.O/parameter ratio after pruning with respect to the P..PSppaaameeers of the dense model.
respectively, yielding subnetworks with a 40% reduction in FLOPS and 20% reduction in parameters in comparison to the dense model. Pruning also performed with larger value (i.e., = 0.05 and 0.08 for MobileNetV2 and ResNet34, respectively) to yield subnetworks with 60% reduction in FLOPS and 35% reduction in model parameters in comparison to the dense model.
The results are reported in Table 2 Although the dense network is pre-trained for 150 epochs, subnetwork test accuracy reaches a platean after only 100 epochs of pre-training in all cases. Furthermore, subnetworks with only epochs of pre-training still perform well in many cases. For example, the 60% FLOPS ResNet34 subnetwork with epochs of pre-training achicves a testing accuracy within 1% of the pruncd model derived from the fully pre-trained network. Thus, high- perfoperfgrning subnelworks can be discovered with miniiml pre- training even large-scale datasets like ImageNet.
Discussion. These results demonstrate that the number of dense network pro-training iterations needed to reach a plateau in subnetwork performance i) consistently increases with the size of the dataset, and ii) is consistent across different architectures given the same dataset. Discovering a high-performing subnetwork on the ImageNet dataset takes roughly 500K pre-training iterations (i.e., 100 epochs). In comparison, discovering subnetwork that performs well on the MNIST and CIFAR10 datasets takes roughly 8K and 60K iterations, respectively. Thus, the amount of required pre-training iterations increases based the size of dataset even across signéficantly different scales and domains. This indicates that the dependence of pre-training requirements on dataset size may be an underlying property of discovering high-performing subnetworks no matter the experimental setting.
Interestingly, we observe that dense network size does impact subnetwork performance. In Figure [ sub- network performance varies based on dense network width, and subnet derived from narrower dense networks seem to achieve better performance. Similarly, in Tables [ and / subnetworks derived from Mo- bileNetV2 tend to achieve higher relative performance than the dense model. Thus, subnetworks derived from smaller dense networks seem to achieve better relative performance in comparison to those derived from larger dense networks, suggesting that pruning via greedy forward selection may demonstrate different qualities in contrast to more traditional approaches (e.g., iterative magnitude- based pruning (Liu et al. 2018)). ). Despite this observation, however, the amount of pre-training epochs required for the emergence of the best-performing subnetwork is still consistent across architectures and dependent on dataset size.
The experimental result on deep neural networks is consistent with the intuition that our theoretical results may also generalize to deeper architectures. In particular, notice that our theory consists of two components: i). an upper bound the pruning error, and ii).a convergence guarantee that depends on the minimum cigenvalue of the NTK matrix. For i). we should note that, since the algorithm for deep neural nelworks involves a layer-wise pruning Ye el al. (2020), our analysis has the potential to extend to deeper architecture as long as one controls the error in the output of each intermediate layer from pruning weights in the previous layers and treat this output as the input the following layers.
Connection to Theoretical Results.
For ii), the emerging analysis on the convergence property of training deep neural networks Liu et al. 20023
2021 Nguyen (022)) shed light on some theoretical evidence. In particular, it is shown in Nguyen 2021
13

---

Published in Transactions on Machine Learning Research (02/2024)
Nguyen et al. (2022) that the condition number of the NTK of the deep ReLU network also depends on the number of training samples, which may explain why our theory could also generalize to deeper architectures.
7 Conclusion
In this work, we theoretically analyze the impact of dense network pre-training on the performance of a pruned subnetwork obtained via greedy forward selection. By expressing pruned network loss in terms of the number of gradient descent iterations performed on its associated dense network, we discover a threshold in the number of pre-training iterations beyond which pruned subnetwork achieves good training loss. Our theoretical result implies this threshold's dependency on the datasct's size, which offers intuition into the early-bird ticket phenomenon and the difficulty of replicating pruning experiments at scale. We also empirically verify our theoretical findings over several datasets and network architectures, showing that the amount of pre-training required to discover winning ticket is consistently dependent on the size of the underlying dataset. Beyond the materials in the main text, we also included in Appendix a distributed version of the greedy forward selection algorithm and its empirical performance evaluation.
Several problems remain, such as extending our analysis beyond two-layer networks, deriving generalization bounds for subnetworks pruned with greedy forward selection, even using thcoretical results to discover new heuristic methods for identifying early-bird lickets in practice. Moreover, fulure works can consider extending our theory to deeper architectures. In particular, a generalization of Algorithm is given in (Yo (et al. 2020). To apply our analysis to a deeper architecture, future work should consider performing layer- wise analysis on the convergence of the pruning algorithm and upper-bound the propagation of the errors through layers. The pruning algorithm we consider also has the potential extend to other architectures. For example, we provided Algorithm 2 a generalization of Algorithm to CNN.
References
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparamcterized neural networks, going beyond two layers. arXiv preprint arXiv:1811.04918 2018.
Sajid Anwar, Kyuyeon Hwang, and Wonyong Sung. Structured pruning of deep convolutional neural net- works, 2015.
Francis Bach. Breaking the Curse of Dimensionality with Convex Neural Networks. arXiv e-prints, art arXiv:1412.8690, December 2014.
Cenk Baykal, Lucas Liebenwein, Igor Gilitschenski, Dan Feldman, and Danicla. Rus. SiPPing Neural Net- works: Sensitivity-informeed Provable Pruning of Neural Networks. arxiv e-prints, art arXiv:1910.05422. October 2019.
Aurélien Bellet, Yingyu Liang, Alireza Bagheri Garakani, Maria-Florina Balcan, and Fei Sha. A distributed frank-wolfe algorithm for commuication--ffiiiee sparse learning. In Proceedings of the 2015 SIAM inter- national conference on data mining, pp. 478-486. SIAM, 2015.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning?, 2020.
Xiangyu Chang, Yingcong Li, Samet Oymak, and Christos Thrampoulidis. Provable benefits of overpa- rameterization in model compression: From double descent to pruning neural networks. arXio preprint arXiv:2012.0874, 2020.
Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Michael Carbin, and Zhangyang Wang. The lottery tickets hypothesis for supervised and self-supervised pre-training in computer vision models. arXiv preprint arXiv:2012.0600 2020.
Xiaohan Chen, Yu Cheng, Shuohang Wang, Zhe Gan, Zhangyang Wang, and Jingjing Liu. EarlyBERT: Efficient BERT Training via Early-bird Lottery Tickets. arXiv e-prints, art 11X0v02101.00063, December 2020.
14

---

Published in Transactions on Machine Learning Research (02/2024)
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pallern recognilion, pp. Teee, 2009.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 2966:114,,142, 2012.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675-1685. PMLR, 2019.
Utku Evci, Trevor Gale, Jacob Mcnick, Pablo Samuel Castro, and Erich Elsen. Rigging the Lottery: Making All Tickets Winners. arXiv e-prinls, art. arXiv:1911.11134, November 2019.
Utku Evci, Yani A. Ioannou, Cem Keskin, and Yann Dauphin. Gradient Flow in Sparse Neural Networks and How Lottery Tickets Win. arXiv e-prints, art. arXiv:2010.03533, October 2020.
Marguerite Frank, Philip Wolfe, et al. An algorithm for quadratic programming. Noval research logistics quarterly, 3(1-2)955-100 1956.
Jonathan Frankle and Michael Carbin. The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural
Networks. Xiv e-prints, art ArXiv:1803.03633 March 2018.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, and Michael Carbin. Stabilizing the Lottery Ticket Hypothesis. XrXiv e-prints, art. arXiv:1903.011 00011, March 2019.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Pruning neural networks at initialization: Why are we missing the mark? arXie preprint or S5::2009.08776 2020.
Trevor Gale, Erich Elsen, and Sara Hooker. The State of Sparsity in Deep Neural Networks. arxiv e-prints, art arXiv:1902.09574, February 2019.
Surbhi Goel, Adam Klivans, and Raghu Meka. Learning One Convolutional Layer with Overlapping Patches. arXiv e-prints, art. arXiv:1802.02547, February 2018.
Song Han, Huizi Mao, and William J. Dally. Deep Compression:
Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding. arXiv e-prints, art. arXiv:1510.00149 October 2015.
Song Han, Xingyu Liu, Huizi Mao, Jing Pu, Ardavan Pedram, Mark A. Horowitz, and William J. Dally. EIE: Efficient Inference Engine on Compressed Deep Neural Network. arXiv e-prints, art. arXiv:1602.01 February 2016.
Boris Hamin and Mihai Nica. Finite depth and width corrections to the neural tangent kernel. arXiv preprint arXiv:1909.055 05989, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. arXiv e-prints, art 1XXiv:1112.03385 December 2015.
Yihui He, Xiangyu Zhang, and Jian Sun. Channel Pruning for Accelerating Very Deep Neural Networks. arXiv e-prints, art 1rXiv:1707.06168, July 2017.
Jie Hou, Xianlin Zeng, Gang Wang, Jian Sun, and Jie Chen. Distributed momentum-based frank-wolfe algorithm for stochastic optimization. IEEE/CAA Journal of Automatica Sinica, 2022.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arXiv:1806.0755 07577, 2018.
Gauri Jagatap and Chinmay Hegde. Learning relu networks via alternating minimization. arXiv preprint arXiv:1806.0748 170.00733,, 2018.
15

---

Published in Transactions on Machine Learning Research (02/2024)
Martin Jaggi. Revisiting Frank- Wolfe:
Projection-free sparse convex optimization. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 427 435, Atlanta, Georgia, USA, 17 19 Jun 2013. PMLR. URL http://proceedingg http://roooodnna.l....eeepeeeeee mwr. ww..m.....sss..... wwlr.prees/v2//jaara
html
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning Filters for Efficient ConvNets. arXiv e-prints, art. arXiv:1608.08710, August 2016.
Yuanzhi Li and Yang Yuan. Convergence Analysis of Two-layer Neural Networks with ReLU Activation. arXiv e-prints, art. 105.:11705.0986, May 2017.
Zhuo Li, Hengyi Li, and Lin Meng. Model compression for deep neural networks: A survey. Computers, 12 (3), 2023. ISSN 2073-431X. doi: 2..330/commputes//2000000 URL BRLLhhtp:://wwt http://www.mppi....mmmm cttpp//3////0233331111 12/3/50
Tailin Liang, John Glossner, Lei Wang, Shaobo Shi, and Xiaotong Zhang. Pruning and quantization for deep neural network accoleration: A survey, 2021.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameterized non- linear systems and neural networks, 2021.
Chaoyue Liu, Dmitriy Drusvyatskiy, Mikhail Belkin, Damek Davis, and Yi-An Ma. Aiming towards the minimizers: fast convergence of sgd for overparametrized problems, 2023.
Kuang Liu. Pytorch-cifar.
http://www..cauuuuunugaga////rra 2017.
Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang, Learning Effi- cient Convolutional Networks through Network Slimming. arXiv e-prints, art. arXiv:1708.06519, August 2017.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the Value of Network Pruning. arXiv e-prints, art. arXiv:1810.05270, October 2018
Yiping Lu, Chao Ma, Yulong Lu, Jianfeng Lu, and Lexing Ying. A Mean-field Analysis of Deep ResNet and Beyond: Towards Provable Optimization Via Oxerparameterization From Depth. arXiv e-prints, art. arXiv:2003.05508, March 2020.
Jian-Hao Luo, Jianxin Wu, and Weiyao Lin. ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression. arXiv e-prints, art arXiv:1707.06341 July 2017.
Eran Malach, Gilad Yehudai, Shai Shwarr-S and Ohad Shamir. Proving the Lottery Ticket Hypothesis: Pruning is All You Need. arXiv e-prints, art. arXiv:2002.00585, February 2020.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A Mean Field View of the Landscape of Two-Layers Neural Networks. arXiv e-prints, art. arXiv:1804006661, April 2018.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. arXiv e-prints, art. XXXi:1902200015 February 2019.
Ari S Morcos, Haonan Yu, Michela Paganini, and Yuandong Tian. One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers. arXiv preprint arXiv:1906 0206000273 2019.
George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maxi- mizing submodular set functions i. Mathematical progromming, 14(1):265-29) 294, 1978.
Quynh Nguyen. On the proof of global convergence of gradient descent for deep relu networks with linear widths, 2021.
16

---

Published in Transactions on Machine Learning Research (02/2024)
Quynh Nguyen, Marco Mondelli, and Guido Montufar. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks, 2022.
Laurent Orseau, Marcus Hutter, and Omar Rivasplata. Logarithmic Pruning is All You Need, orXiv e-prints, art. arXiv:2006.12156 June 2020.
Samet. Oymak and Mahdi Soltanolkotabi. Towards moderate overparamettrriaatio:: global convergence guarantees for training shallow neural networks. arXiv e-prints, art. arXiv:1902.04674 February 2019.
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Op- timal lottery tickets via subsetsum: Logarithmic over-parancteriation is sufficient. arXiv preprint arXiv:2006.079000 2020.
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailioponlos. Optimal lottery tickets via subsetsum: Logarithmic over-paranettriiation is sulficient, 2021.
Sebastian Pokutta, Christoph Spiegel, and Max Zimmer. Deep Neural Network Training with Wolle. aiviv e-prints, art. arXiv:2010.07243, October 2020.
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari. What's Hidden in a Randomly Weighted Neural Network? arXiv e-prints, art arXiv:1911.13200 Novem- ber 2019.
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing Rewinding and Fine-tuning in Neural Network Pruning. arXiv e-prints, art. mrXiv:2003.0238) March 2020.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginox, and Liang- Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference computer vision and pottern recognition, pp. 4510-4520, 2018.
Chaehwan Song, Ali Ramezani- Thomas Pethick, Armin Eftekhari, and Volkan Cevher. Subquadratic overparameterization for shallow neural networks. Advances in Neural Information Processing Systems, 34, 2021.
Hoi-To Wai, Jean Lafond, Anna Scaglione, and Eric Moulines. Decentralized frank-wolfe algorithm for convex and nonconvex problems. IEEF Transactions on Aulomalic Control, 62(11):5522 5537, 2017.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking Winning Tickets Before Training by Preserving Gradient Flow. arXiv e-prints, art. arXiv:2002.07376, February 2020.
Wenhan Xian, Feihu Huang, and Heng Huang. Communication-efieeen frank-wolfe algorithm for noncon- vex decentralized distributed learning, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10405-10413, 2021.
Ruibin Xiong, Yunchang Yang, Di Hc, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tie-Yan Liu. On Layer Normalization in the Transformer Architecture. arXiv e-prints, art 2:X1v:2002.047455, February 2020.
Zheyang Xiong, Fangshuo Liao, and Anastasios Kyrillidis. perturbation, 2022.
Strong lottery ticket hypothesis with E-
Mao Ye. Baawwok--rrunng-GGGe Seapaag--rrrree--rarrrrr-eeeeaae 2021.
sttps://gittub..co/lllsl
Mao Ye, Chengyue Gong, Lizhen Nie, Denny Zhou, Adam Klivans, and Qiang Liu. Good subnetworks provably exist: Pruning via greedy forward selection. In International Conference on Machine Learning, pp. 10820-10830. PMLR, 2020.
Mao Ye, Lemeng Wu, and Qiang Liu. Greedy Optimization Provably Wins the Lottery: Logarithmic Number of Winning Tickets is Enough. Xiv e-prints, art arXiv:2010.1500 15969, October 2020.
17

---

Published in Transactions on Machine Learning Research (02/2024)
Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Richard G Baraniuk, Zhangyang Wang, and Yingyan Lin. Drawing early-bird tickets: Towards more efficient training of deep networks. arXiv preprint 1rXic:1909.11990 2019.
Ruichi Yu, Ang Li, Chun-Fu Chen, Jui-Hsin Lai, Vlad I. Morariu, Xintong Han, Mingfei Gao, Ching-Yung Lin, and Larry S. Davis. NISP: Pruning Networks using Neuron Importance Score Propagation. arXiv e-prints, art arXiv:1711.09900 November 2017.
Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning onc-hidden-layer relu networks via gradient descent. In The 22nd International Conference Artificial Intelligence and Stalistics, pp- 1524-1534. PMLR, 2019.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask. arXiv e-prints, art. arXiv:1905.0106,, May 2019.
Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression. Xiv e-prints, art arXiv:1710.01878, October 2017.
Zhuangwei Zhuang, Mingkui Tan, Bohan Zhuang, Jing Liu, Yong Guo, Qingyao Wu, Junzhou Huang, and Jinhui Zhu. Discrinination-aware Channel Pruning for Deep Neural Networks. arXiv e-prints, art. arXiv:1810.11800 October 2018
18

---

Published in Transactions on Machine Learning Research (02/2024)
A Proof of Lemma 2
Proof. We will proceed with the proof by induction on the scope of P;'s that u and v are composed of. To be more specific, we will show that ||u v S D' for all u, v E Conv { E [n]] for n 1....,.. For the base case, we consider n = 1. We must have that u = D1 = v. Therefore, ||u- -vl2 = v D'. For the inductive case, suppose that our claim true for n 1,...,10 n'. We shall prove that it is true for n = n' +1. In this case,
+1
n n'+1
7 ; V Σ
11
7/
for some f and f satisfying >xs 7/- = > i= % = and % 2 0. 2 for all i [n' + 1].
+1
+1
Without loss of generality, let N/++1 2 11 If 7n1+1 = 1, then we have
n
u v112 =
Pn'41
1=1
n
7/ (1 n'11 - -,,)
2
n
Y/ || 1 nn+1 2ell2
n
< D'
7
i=1
< D''
Otherwise, we can suppose 2/44 S sn'41 <. In this case, we can write u and v as
n
u 21 Pn141 + (1 - 7nr41)
7
1==++11.m Pn141 + (1 - 71441) u'
Tu'+1
1=1
4/41 pn'41 + (1 11411)
Σ
T/e 2 + -w/4)) v'
2241
for some u', v E Conv ( :iE [n']]. Then by the inductive hypothesis, we have ||u -0'122 S D'. Thus we
have
||u
v112 |1(7/041 k
( (x/+11 v') + (1 --/++1) (u' - v')l2
S (Thrt1 7/1 k1(11)
$ Bn'41 v112 + (1 7n(41) || -vll2
a'
%
S (7h+11 - -h(41)
Σ
(#n'41 - v\
+ +11 7a' D'
R'441
1=1
(hh/41 -hhc4))
Σ
7
| -v112 + (1 72/+1) D'
1=1
n'
%/2
S (7441 - -hhe41)
D'
+ (1 - +1) D'
1/411
1=1
(1 - 11) D' D
This finishes the inductive step and thus finishes the proof.
19

---

Published in Transactions on Machine Learning Research (02/2024)
B Proof of Theorem 2
Our proof utilizes the result from Song et al. 2021 We first revisit the scheme and thcoretical result discussed in [Song et al. 2021 After that, we will interpret their result in the scenario we are consideration.
B.1 Existing Result
Song et al. 2021 considers using gradient descent. minimize the objective h Eo where E: Rdduu - R is the loss function and f Rd + Rout the function of the model defined over m input-output pairs. particular, [Song et al. 2021 makes the following assumption to show that gradient descent converges Assumption 3. (Gradient Descent)
is twice difserentiable, salisfies Pe condition, and is Be-smooth.
is twice differentiable, 3 --smooth.
Building upon Assumption 3 they have the following Theorem
Theorem 4. (Theorem 2 in Song et al. 20211). ). Assume that Assumption holds. Let wo IR satisfy
(Vf (w()))) S Fmax (wo)) s ;
Mj S miin
acu 3i
and h(wo)= =0
Then the sequence {we)r=o generaled by
We+1 = W. - ( 1=
B/ v8 (f (Wo) 11 + + (17
satisfies the following convergence property
h ((w+1) S 2(1 1111 C-Cnnepp)) (we)
for some consland C C>0 0.
To extend this result to the training of shallow neural networks, they consider the following parameterization of the two-layer neural network and the mean-squared error loss
(() Vo (WX);
(v)
1
where X Iddxm is the matrix consisting of the input vectors, Y Rd xm is the matrix consisting of the label vectors, W Nxd is the first layer weights, V E Rd'' the second layer weights, (W. V} is the collection of weights, and a (+) is the entry-wise activation function. Within this setup, they make the following assumption about the neural network
Assumption 4. (Neural Network)
At initialization, the entries of the weight satisfies Wy ~ N (0, and V ~ N -N (0, satisfying w144 O (Vax)
0+ (-) is twice differentiable and satisfies max { (-), 10" (-) <
There cxists T1,72 such that 7 10+ (a)) s lo (ra) < rra 1o+ (a)).
For all it holds that Fmax (Vx) O(1)
6rhhis assumption be eliminated by assuming a larger overparamederization..
20

---

Published in Transactions on Machine Learning Research (02/2024)
With Assumption they proved the following result:
Theorem 5. Suppose that Assumption 4 holds. N = N= =mm²) )nnz), then with high probobility over the initial- ization, we have
20211) ) Pf min (o+ (WX)) S min (
(Lemma 18 in [Song et al.
2021)) Vj := cadomax (X) + max (o+ (WX)) 2 maxx (vf(Oo)) for
(Lemma 18 of some conslant co U.
Song et al.
(Lemma 18 in Song et al.
2021))
} = C1 0 (X) for some constant e > 0.
(Theorem 3 in (Song et al. 2021)) O satisfies h(Op) =
with Hj and Vj defined above.
Combining Theorem and Theorem they obtain training loss convergence for the two-layer neural network.
B.2 Proving Theorem 2
Recall that given input x, neural network is defined
1 2 N
(xx
Σ o (x, 0,) = Ebib0 6,0 (a. (a.xx
Indeed, generalizing to fixed matrix of input vectors X and outputs Y, our neural network can be written
as
f (0) = bTo a_ (AX) E Rxmm C[f(: (1)
Therefore, our neural network setup is the same as Song et al. 2021 by letting the output dimension d' 1. Moreover, by assuming Assumption In this way, we have Wawb d - VaN Thus, interpreting Theorem in our setting, Wp Va we have
1 and 2 Assumption is satisfied with wa m - and
vm
Theorem 6. Suppose that Assumption and Assumplion holds. IfN (m²). then with high probability over the initialization, we have
:= = Ammi S Omin (Q())
vy : co0mm Vm 2 Tmax
(v)( for some constant co >> 0.
8j m for some constant > 0.
ark 3juj
c satisfies C[f (., e.)] 0
with μæ and vs defined above.
Proof. To start, notice that
m Σ
Umax (X) < |
1x,
vm
(19)
For Bullet 1, we recall that Amin is defined as Amin VN mii (AoX) in Definition Combining with the first bullet point in Theorem 5 gives Bullet 1. For Bullet 2, recall that Xmax is defined as Amax V maxx (A₂X) in Definition Combining with the second bullet point in Theorem and plugging in 19
gives the desired result. For Bullet we use the third bullet in Theorem and plug-in 19 Lastly, the fourth bullet directly follows from Theorem 5
21

---

Published in Transactions on Machine Learning Research (02/2024)
With Theorem 6 guarantee the convergence of training loss in our scenario.
Theorem 7. Suppose that Assumption and Assumption
holds. If = (2 and
then with high probability over the initialization, we have [[][[(0W)] )
C (., 041)) - Cyp.N C 9r)
Proof. We wish to apply Theorem | By utilizing Theorem it remains to explicitly check the requirement of the step size rj and compute the convergence rate. Notice that in Theorem 1) is given by
1
1 ==
B3 [/1]Ve + Br (n9 + +13
By our choice of E, we have that [[((oo))) = have
= (. (o)] and Be 1. Moreover, using μy vy, we
( (3
7 ==
=0
(. (.. (:)) + 203
Vm 1+ ( (o)) + N
max
by plugging in the value of By and Vy from Theorem i and omitting the constants. Moreover, for the choice of we have ag = 1. Then, the convergence rate was reduced to
Cnazu CnN min
Notice that a direct consequence of Theorem is that
C (s 0.) (1 Cy L (s, 9o)
(20)
When pruning is performed after t iterations of gradient descent, we can substitute O with θ Lemma get that
C [fs,, (-. 0) < C [fs, (. θ) + 1 log
2k: DMy + k --1 C (-, O.)
k
h
Then, we use k-1 < 1 and simply apply the upper bound of [ (., 0.)] in 20 to get that &
Clss. (s [)] < 1 1 [fs, (s 0)] + 1 log
DMy
CnN LlS (, Oo)
2h
C Numerical Experimental Verification
In Figure we randomly generated matrix in the following way: we first generating a av with a, N 00 Va L.), then, generate XI...,, Xm with X, N La) and normalize each Xj. After that, compute V by Li =yy=o a (aTx,) x,) to simulate the hidden neuron output at initialization. For each N, and m, we generate 10 of such & matrices and record their minimum singular values" mean and standard deviation. Figure plots amin ( for different. N, d, and m. For each d and m, we also plotted the curve to compare with the curve amin (IT). We can observe that the two curves almost overlaps, implying O (N)
that Jmin v indeed scale with (VN).
In Figure we conduct simple experimental verification of the condition number of standard Gaussian random matrices of shape N x m, where the condition number k of a matrix defined as k emax We observe that =1 decreases increases.
Gmin (M)
22

---

Published in Transactions on Machine Learning Research (02/2024)
10
1300
275
176
232
235
(a) 200, m7 = 50
(b) 200, 771 100
(c) d 200,
172 200
330
230
484
12:
(d) d 500, m = 50
(e) 500, m
100
(1) = 500, m
200
Figure 2: Plotting min (v) versus N with different d, m. For reference, we also plotted O(v
0.8
N 1000
0.7
0.6
0.2
0.1
200
300
400
500
800
700
800
Figure 3: Inverse of the condition number of a standard Gaussian random matrix with shape N x m
D CNN Experiments
Algorithm Greedy Forward Selection for Deep CNN
Require: Number of layers numbers of hidden filters (Col training data D; error tolerance e; loss function Le (X,)); CNN weights @ with O (Ot.)setoa) for E [7.]
+ = +
for 1,2 do
3:
==
4:
while Le. (X,y) < e do
5:
X,y ~
j' = arg min |E[C,]
(X,y)
(- (-
end while
end for
10: return e
23

---

Published in Transactions on Machine Learning Research (02/2024)
95
80
92
Accuracy
83
89
MobileNetV2
Res Net34
30-4
1e-3
36-3
0.01
0.03
0.1
3e4
le.3
3e-3
0.01
0.03
Learning Rate
0.01
0.02
0.05
0.1
Figure 4: Subnetwork validation accuracy on the CIFARIO dataset for different settings of e and initial learning rate for fine-tuning. All models are pre-trained identically for 200 epochs. Fine-tuning is performed for SO epochs, and we report validation accuracy for each subnetwork at the end of fine-tuning.
We begin with an in-depth algorithmic description of the greedy forward selection algorithm used for struc- tured, channel-based pruning of multi-layer CNN architectures. This algorithm is identical to the greedy forward selection algorithm adopted in Ye et al. (2020). In this algorithm, we denote the weights of the deep network as O and reference the weights within layer l of the network as O₁ Similarly, we use Oe to denote the weights of all layers following layer l and Or to represent the weights of all layers up to and including layer f. C' denotes a list of hidden sizes within the network, where C₂ indicates the mumber of channels within layer & of the CNN. Again, we use f(O, X') to denote the output of two-layer network with parameters & over the mini-batch X' and fs X') to denote the same output only considering the channel indices included within the set S.
Now, we present more details regarding the hyperparameters utilized large-scale experiments. For Ima- geNet experiments, we adopt the settings of Ye et al. (2020) For CIFAR1O, however, we tune the setting of and the initial learning rate for fine-tuning using a grid search for both MobileNet and ResNet34 architectures. This grid search is performed using validation set CIFAR110, constructed using random 80-20 split on the training dataset. Optimal hyperparameters are sclected based on their performance on the validation set. The results of this grid search are shown in Figure 4 As can be seen, for MobileNet V2, the best results are achieved using a setting of = 0.02, which results a subnetwork with 60% the FLOPS of the dense model. Furthermore, an initial learning rate of 0.01 yields consistent subnetwork performance for MobileNetV2. For ResNet34, a setting of 0.05 yields the best results and subnetwork with 60% of the FLOPS of the dense model. Again, initial learning rate of 0.01 for fine-tuning yields the best results for ResNet34. For the rest of the hyperparameters used within CIFAR10 experiments (i.e., those used during pre-training), we adopt the settings of widely used, open-source repository that achieves good performance on CIFAR10
E
Distributed Greedy Forward Selection
We propose a distributed variant greedy forward selection that can parallelize and accelerate the pruming process across multiple compute sites. Distributed greedy forward selection is shown to achieve identical theoretical guarantees compared the centralized variant and is used to accelerate experiments with greedy forward selection within this work.
We adopt the same experimental settings but decrease the number of fine-tuning epochs from 150 because we find that testing accuracy reaches plateau well before 150 epochs.
24

---

Published in Transactions on Machine Learning Research (02/2024)
For the distributed variant of greedy forward selection, consider local compute nodes V= fo (o which communicate according to undirected connected graph G = (V.E). Here, & is a set of edges, where [&] = E' and ey) E indicates that nodes v and bj can communicate with each other. For simplicity, our analysis assumes synchronous updates, the network has no latency, and each node has an identical copy of the data D.
Algorithm 3 Distributed Greedy Forward Selection for Two-Layer Networks
(5) 0, E [V] 20
2: for : 1.2.... do
3: # Step I: compute local estimate of the next iterate
4:
for vi E do
5:
q = arg min
( (Zk-1 + +)))
qEVert(M
(8) = - + 9k
(i)
6:
2
7:
Broadcast: (() == 2/
(1)
8:
end for
Step II: determine and broadcast the best local iterate
10: for U V do
i arg min [(O) <E[V]
11:
12:
if i then
13:
Broadcast: Zд : Z
(6)
14:
end if end for
15:
16:
# Step III: update the current, global iterate
17: for v E V do
18: u2 = 2
19: end for
20:
end for
21: Stopping Criterion: {(u)) Se
Recall that the set of neurons considered by greedy forward selection given by Vert(MN) ( : [N]] In the distributed setting, assume that the weights associated with each neuron are uniformly and disjointly partitioned across compute sites. More formally, for J E [V], we define A(t) as the indices of neurons by and (6)) = {0, : A as the neuron weights contained on vy. Going further, we consider
( E A and denote the convex hull over this subset of neuron activations as M We assume that = Ø for j + k and that U 401) [N].
A0) (M)
3 aims to solve the main objective in this work, but in the distributed setting. We maintain a global set of active neurons throughout pruning that is shared across compute nodes, denoted as Sy at pruning itcration k. At each pruning iteration k, we perform local search over the neurons on each 2) E V, then aggregate the results of these local searches and add a single neuron (iee., the best option found by any local search) into the global set. Intuitively, Algorithm 3 adopts the same greedy forward selection process from Algorithm [ but parallelizes it across compute nodes.
Al Algorithm
Empirical validation of the distributed implementation. The centralized and distributed variants of greedy forward selection achieve identical convergence rates with respect to the number of pruning iterations. Despite its impressive empirical results, one of the significant drawbacks of greedy forward selection is that it slow and computationally expensive compared to heuristic tochniques. Distributed greody forward selection mitigates this problem by parallelizing the pruning process across multiple compute nodes with minimal communication overhead.
25

---

Published in Transactions on Machine Learning Research (02/2024)
Centralized
12
Distributed Nodes!
Distributed Nodes)
15
ResNet34 Block Index
Figure Pruning time for centralized and distributed greedy forward selection applied to different blocks of ResNet34 architecture on ImageNet.
To practically examine the acceleration provided by distributed greedy forward selection, we prune ResNet34 architecture (He et al. 2015) the ImageNet dataset and measure the pruning time for each layer with different greedy forward selection variants. In particular, we select four blocks from the ResNet34 architecture with different spatial and channel dimensions. The time taken to prune each these blocks is shown in Figure 5 All experiments are run on an internal cluster with two Nvidia RIX 3090 GPUs using the public implementation of greedy forward selection YY 2021
Distributed greedy forward selection (using either process for nearly all blocks within the ResNet. Notably, speedup is observed for the second block because earlier ResNet layers have fewer channels to be considered by greedy forward selection. As the channel dimension increases in later layers, distributed greedy forward selection yields significant speedup in the pruning process. Given that the convergence guarantees of distributed greedy forward selection are identical to those of the centralized variant, we adopt the distributed algorithm to improve efficiency in most of our large-scale pruning experiments.
four GPUs) significantly accelerates the pruning
26


Reviews:
[{"review_id": "DS2VzO2o5D", "reviewer": "Reviewer_KEDf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nThis work provide new theoretical results regarding the greedy forward selection algorithm.\n\nWeakness:\n(i) This work considers a relatively large scale of initialization, i.e.,  \\omega_b and \\omega_a is fixed as N\\to \\infty. This initialization leads to an initial loss  of O(\\sqrt(N)) dependent on the number of neurons N. However, in Lemma 3 and later results, N is further assumed to be dependent on the initial loss.  In the revision, this inconsistence need to be addressed and the authors should discuss the scale of initialization and its impact on initial loss.\n\n(ii) The theoretical results seems to rely heavily on a NTK-type regime with linear convergence. However, the NTK regime in general generalize poorly. If the theoretical results are only relevant to the NTK-type regime, then it is not so relevant to the training in practice. I suggest the authors to discuss this issue in the revision.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a modified greedy forward selection algorithm for pruning and studies its theoretical properties. Specifically, this work provides a theoretical bound of the number of gradient descent pre-training iterations for two-layer fully connected networks with proper activation. It also provides empirical results demonstrating the data size dependency of the pruning performance consistant with the theoretical results.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Weakness above", "broader_impact_concerns": "N.A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "uS7yLqk3aC", "reviewer": "Reviewer_NNqK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper is written clearly and is easy to follow and understand.\n- As far as I know, this is the first paper to theoretically show that more pre-training is needed to get a good sub-network when pruning. The topic itself is interesting to the community, and theoretical evidence, even on a simplified model such as two-layered over parameterized networks, is important.\n\nWeaknesses:\n\n- The empirical validation is a weak point of the paper. The theoretical analysis heavily relies on specific assumptions, such as a 2-layer network, a very wide hidden layer, a non-commonly used loss function, and certain assumptions about the data and labels. While these assumptions are standard in the analysis of 2-layered networks, they deviate significantly from the norms in deep networks, raising concerns about the generalizability of the findings. Particularly important is the fact that the paper did not show an iff result: the analysis shows that after many training iterations, all pruning yields good subnetworks. However, it does not show that after fewer training iterations, pruning would result in poor subnetworks -- therefore, in practice, it may be the case that the results do not hold, and extensive empirical validation is required. Such validation should include experimentation with both 2-layered networks and deep neural networks, across various datasets and data sizes, which is crucial for establishing practical applications. Although the main paper features binary MNIST, the inclusion of experiments on CIFAR-10 and ImageNet (which are hinted at in the abstract and discussion but not in the main paper), currently relegated to the appendix, would substantially strengthen the paper and warrant further elaboration on their results.\n\n- The paper would benefit from a discussion of the theory's limitations and advantages within a broader context. For instance, addressing how other factors that might influence the required pre-training are related to or overlooked by the analysis. Potential factors for discussion include the impact of complex data, wider networks requiring more training until convergence, and the diminishing returns effect on data size. This discussion could be seamlessly incorporated at the end of section 4, offering insights into the broader implications of the theory without necessitating additional analysis. I think that many of these points could be easily addressed by the authors (for example, I would think that data complexity could be encoded in the distance of the underlying convex hull), and could strengthen the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the theoretical aspects of pruning in two-layer overparameterized neural networks. It establishes a link between the amount of pre-training needed for this model and the size of the training data. Essentially, larger training datasets necessitate more iterations to ensure that the greedy forward selection algorithm results in a small pruned sub-network with comparable performance. The paper supports these findings with empirical experiments, demonstrating similar patterns in 2-layered binary MNIST trained on image datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Extend the empirical section to include the experiments in Appendix E, and elaborate on them to show that in practice bigger datasets require more pre-training outside of 2-layered network scenarios. This point is critical to secure my recommendation for acceptance.\n\n- Include a discussion in Section 4 that addresses the limitations and advantages of the proposed theory within a broader context. This point would strengthen the work in my view, but is not critical to securing a recommendation for acceptance.\n\n\nminor formatting errors:\n- page 23, at the footnote, change Appendix ?? to the real cross-reference\n- The title of the paper is broken into 2 lines in a weird place, consider fixing it", "broader_impact_concerns": "Not relevant for this paper", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8cT6iIHWFh", "reviewer": "Reviewer_KcNq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n* The paper is generally well-written and easy to understand despite its technical depth.\n* Theoretical analysis is comprehensive; most of the paper's technical content is devoted to this. The assumptions made are well justified.\n* Coverage of related work is strong.\n\n\n**Weaknesses**\n\n* The theoretical analysis is limited to two-layer networks, which is understandable. Further discussion on this point would be valuable: how could these results be extended to other architectures?\n* It's unclear how the empirical result in Figure 1 corresponds to Theorem 3; it would be good to include a theoretical prediction line in the Figure as well.\n* The empirical results are mostly contained in the appendix while the paper mostly focuses on the theoretical results. This is understandable for a theoretical paper; however, I would suggest moving a bit of the theory to the appendix to leave room for a bit more experimental results and analysis in the main text.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers theoretical bounds on the performance of two-layer fully connected neural networks pruned via greedy forward selection. The paper finds improved bounds on selection error and demonstrates that a minimum amount of pre-training is required for a pruned network to perform well, with this amount depending on dataset size. Experiments on multiple datasets and architectures validate this trend.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Critical**\n* Include a theoretical prediction line in Figure 1\n\n\n**Would improve**\n* Adding error bars or some indication of variability over multiple trials in Figure 1 and the other empirical results\n* Further discuss how the results could be extended to other architectures\n* Add more experimental results and analysis to the main text from the appendix", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper should be accepted, given that it meets the criteria of presenting supported claims with clear evidence. The theoretical contribution add to the understanding of neural network pruning in the studied very limited NTK regime. The empirical study extends this regime to slightly more general case. Although the evidence support claims, the impact and significance of the paper is rather limited due to the overly constrained setting. This limitations prevents me from suggestion certification and journal to conference recommendation.
Decision: Accept (poster)