Theoretical Characterization of How Neural Network Pruning Affects its Generalization
Authors: Hongru Yang
Yingbin Liang
Xiaojie Guo
Lingfei Wu
Zhangyang Wang
Venue: Submitted to ICLR 2023 (2023)
Keywords: pruning
neural network
gradient descent
generalization

Abstract: It has been observed in practice that applying pruning-at-initialization methods to neural networks and training the sparsified networks can not only retain the testing performance of the original dense models, but also sometimes even slightly boost the generalization performance. Theoretical understanding for such experimental observations are yet to be developed. This work makes the first attempt to study how different pruning fractions affect the model's gradient descent dynamics and generalization. Specifically, this work considers a classification task for overparameterized two-layer neural networks, where the network is randomly pruned according to different rates at the initialization. It is shown that as long as the pruning fraction is below a certain threshold, gradient descent can drive the training loss toward zero and the network exhibits good generalization performance. More surprisingly, the generalization bound gets better as the pruning fraction gets larger. To complement this positive result, this work further shows a negative result: there exists a large pruning fraction such that while gradient descent is still able to drive the training loss toward zero (by memorizing noise), the generalization performance is no better than random guessing. This further suggests that pruning can change the feature learning process, which leads to the performance drop of the pruned neural network. Up to our knowledge, this is the first generalization result for pruned neural networks, suggesting that pruning can improve the neural network's generalization. 

Under review as a conference paper at ICLR 2023
THEORETICAL CHARACTERIZATION OF How NEURAL NETWORK PRUNING AFFECTS ITS GENERALIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
It has been observed in practice that applying pruning-at-in atiiiin-ttinntiiaaiation methods neural networks and training the sparsified networks can not only retain the test- ing performance of the original dense models, but also sometimes even slightly boost the generalization performance. Theoretical understanding for such exper- imental observations are yet to be developed. This work makes the first attempt to study how different pruning fractions affect the model's gradient descent dy- namics and generalization. Specifically, this work considers a classification task for overparameterized two-layer neural networks, where the network is randomly pruned according to different rates at the initialization. It is shown that as long the pruning fraction is below certain threshold, gradient descent can drive the training loss toward zero and the network exhibits good generalization per- formance. More surprisingly, the generalization bound gets better as the pruning fraction gets larger. To complement this positive result, this work further shows a negative result: there exists a large pruning fraction such that while gradient descent is still able to drive the training loss toward zero (by memorizing noise), the generalization performance is no better than random guessing. This further suggests that pruning can change the feature learning process, which leads to the performance drop of the pruned neural network. Up to our knowledge, this is the first generalization result for pruned neural networks, suggesting that pruning can improve the neural network's 's generalization.
INTRODUCTION
Neural network pruning can be dated back to the early stage of the development of neural networks (LeCun et al. 1989). Since then, many research works have been focusing on using neural network pruning as model compression technique, e.g. (Molchanov et al. 2019:
Wu 2017 Ye al.] 2020 Yang et al. 2021). However, all these work focused on pruning neural networks after training to reduce inference time, and, thus, the efficiency gain from pruning cannot directly transferred to the training phase. It is not until the recent days that Frankle & Carbin (2018) showed a surprising phenomenon: a neural network pruned at the initialization can be trained to achieve competitive performance to the dense model. They called this phenomenon the lottery ticket hypothesis. The lottery ticket hypothesis states that there exists a sparse subnetwork inside a dense network at the random initialization stage such that when trained in isolation, it can match the test accuracy of the original dense network after training for at most the same number of iterations. On the other hand, the algorithm Frankle & Carbin (2018) proposed to find the lottery ticket requires many rounds of pruning and retraining which is computationally expensive. Many subsequent works focused on developing new methods to reduce the cost of finding such network at the initialization (Lee) et al., 2018 Wang et al.] 2019 Tanaka et al. 2020: Liu & Zenke 2020) Chen et al.) 202 A further investigation by Frankle et al. (2020) showed that some of these methods merely discover the layer-wise pruning ratio instead of sparsity pattern.
The discovery of the lottery ticket hypothesis sparkled further interest in understanding this phe- nomenon. Another line of research focused on finding a subnetwork inside a dense network at the random initialization such that the subnetwork can achieve good performance (Zhou et al. 2019 Ramanujan et al., 2020). Shortly after that, Malach et al. (2020) formalized this phenomenon which they called the strong lottery ticket hypothesis: under certain assumption on the weight initialization distribution, sufficiently overparameterized neural network at the initialization contains subnet-

---

Under review as a conference paper at ICLR 2023
work with roughly the same accuracy the target network. Later, Pensia et al. (2020) improved the overparameterization parameters and Sreenivasan et al. (2021) showed that such a type of result it was pointed out by Malach et al. (2020),
holds even if the weight is binary. Unsurprisingly, finding such a subnetwork is computationally hard. Nonetheless, all of the analysis is from a func- tion approximation perspective and none of the aforementioned works have considered the effect of pruning on gradient descent dynamics, let alone the neural networks' generalization.
Interestingly, via empirical experiments, people have found that sparsity can further improve gener- alization in certain scenarios (Chen et al., 2021aa la Ding et al., 202T; He et al. (2022). There have also been empirical works showing that random pruning can be effective (Frankle et al.) 2020; [Su al., 2020 Liu et al. (0211b. However, theoretical understanding of such benefit of pruning of neural networks is still limited. In this work, we take the first step to answer the following important open question from a theoretical perspective:
How does pruning fraction affect the training dynamics and the model's general- ization, the model is pruned the initialization and trained by gradient descent?
We study this question using random pruning. We consider classification task where the input data consists of class- desss-eeenndntt sparse signal and random noise. We analyze the training dynamics of two-layer convolutional neural network pruned the initialization. Specifically, this work makes the following contributions:
Mild pruning. We prove that there indeed exists a range of pruning fraction where the pruning fraction is small and the generalization error bound gets better pruning fraction gets larger. In this case, the signal in the feature is well-preserved and due to the effect of pruning purifying the feature, the effect from noise is reduced. We provide detailed expla- nation in Section 3 Up to our knowledge, this is the first theoretical result on generalization for pruned neural networks, which suggests that pruning can improve generalization under some setting. Further, we conduct experiments to verify our results.
Over pruning. To complement the above positive result, we also show a negative result: the pruning fraction larger than a certain threshold, then the generalization performance is no better than a simple random guessing, although gradient descent is still able to drive the training loss toward zero. This further suggests that the performance drop of the pruned neural network is not solely caused by the pruned network's 's own lack of trainability or expressiveness, but also by the change of gradient descent dynamics due to pruning.
Technically, we develop novel analysis bound pruning effect to weight-noise and weight- signal correlation. Further, in contrast to many previous works that considered only the binary case, our analysis handles multi-class classification with general cross-entropy loss. Here, a key technical development is gradient upper bound for multi-class cross-entropy loss, which might be of independent interest.
Pictorially, our result is summarized in Figure T We point out that the neural network training we consider is in the feature learning regime, where the weight parameters can go far away from their initialization. This is fundamentally different from the popular neural tangent kernel regime, where the neural networks essentially behave similar to its linearization.
1.1 RELATED WORKS
The Lottery Ticket Hypothesis and Sparse Training. The discovery of the lottery ticket hypothe- sis (Frankle & Carbin 2018) has inspired further investigation and applications. One line of research has focused on developing computationally efficient methods to enable sparse training: the static sparse training methods are aiming at identifying a sparse mask at the initialization stage based on different criterion such as SNIP (loss-based) (Lee et al. 2018). GraSP (gradient-based
(Wang et al.) 2019), SynFlow (synaptic strength- -aaee) (Tanaka et al. 22220), neural tangent kernel based method
(Liu & Zenke, 2020) and one-shot pruning (Chen et al. 2021b). Random pruning has also been con-
sidered in static sparse training such as uniform pruning (Mariet & Sral 2013 He et al. 2017] Gale
et al. 2019 Suau et al., 2018), non-uniform pruning (Mocanu al. 2016), expander srraph-relater
techniques (Prabhu et al. 22018) Kepner& & Robinett (019) Trdös-Reny: (Mocanu et al.; (018)) and
Rénlis-Renni--eeeee (Evei et al. 2020). On the other hand, dynamic sparse training allows the
2

---

Under review as a conference paper at ICLR 2023
Probabiltty Density
Mild Pruning
Over Pruning
Full model
Signal Strengtth
Figure I: A pictorial demonstration of our results. The bell-shaped curves model the distribution of the signal in the features, where the mean represents the signal strength and the width of the curve indicates the variance of noise. Our results show that mild pruning preserves the signal strength and reduces the noise variance (and hence yields better generalization), whereas over pruning lowers signal strength albeit reducing noise variance.
sparse mask to be updated (Mocanu et al. 2018 Mostafa & Wang 2019: Evci et al., 2020: Jayaku- mar al.) 2020; Liu et al. 2021cc Peste et al. 2021). The sparsity pattern also be learned by using pruning exhibit double descent phenomenon when the data-set labels corrupted.
regularizer Yang et al. 2020). Recently, He et al. (2022) discovered that
Another line research has focused on studying pruning the neural networks at its random ini- tialization achieve good performance (Zhou et al. 2019 [Ramanujan et al. 2020). In particular, Ramanujan et al. (2020) showed that it is possible to prune a randomly initialized wide ResNet-50 match the performance of a ResNet-33 trained on ImageNet. This phenomenon named the strong lottery ticket hypothesis. Later, Malach et al. (2020) proved that under certain assumption on the initialization distribution, target network of width d and depth can be approximated by pruning randomly initialized network that is of polynomial factor (in d, 1) wider and twice deeper even without any further training. However finding such network is computationally hard, which can be shown by reducing the pruning problem to optimizing neural network. Later, Pensia et al. (2020) improved the widening factor to being logarithmic and (Sreenivasan al. (2021) proved that with polylogarithmic widening factor, such result holds even if the network weight is binary. A follow-up work shows that it is possible to find a subnetwork achieving good performance at the initialization and then fine-tune (Sreenivasan et al.) 2022). Our work, on the other hand, analyzes the gradient descent dynamics a pruned neural network and its generalization after training.
Analyses of Training Neural Networks by Gradient Descent. A series of work (Allen-Zhu al.
2019 Zou et al., 2020; Zou & Gu 2019 Ji & Telgarsky 2019 Chen al. 2020b) (Sogg& & Yang 2019 Oymak & Soltanolkotabi 2020) has proved that if deep neural network is wide enough, then (stochastic) gradient descent provably can drive the training loss toward zero in a fast rate based on neural tangent kernel (NTK) (Jacot et al. 2018). Further, under certain assumption on the data, the learned network is able to generalize (Cao & Gu 2019 Arora et al. 2019) However, as it is pointed out by Chizat et al. (2019). in the NTK regime, the gradient descent dynamics of the neural network essentially behaves similarly to its linearization and the learned weight is not far away from the initialization, which prohibits the network from performing any useful feature learning. In order to go beyond NTK regime, one line of research has focused on the mean field limit (Song et al. 2018 Chizat & Bach 2018 Rotskoff Vanden- Eijnden 2018 Wei et al. 2019 Chen et al. 2020a Sirignano & Spiliopoulos 2020) Fang al. 2021). Recently, people have started to study the neural network training dynamics in the feature learning regime where data from different class is defined by set of class-related signals which are low rank (Allen-Zhu & Li] 2220 2022 Cao et af.) 2022 Shi et al., [022]] Telgarsky (0022). However, all previous works did not consider the effect of pruning. Our work also focuses on the aforementioned feature learning regime, but for the first time characterizes the impact of pruning on the generalization performance of neural networks.
2019 Du et al.) 2019; Lee et al.
PRELIMINARIES AND PROBLEM FORMULATION
In this section, we introduce our notation, data generation process, neural network architecture and the optimization algorithm.
3

---

Under review as a conference paper at ICLR 2023
Notations. We use lower case letters denote scalars and boldface letters and symbols (e.g. x) to denote vectors and matrices. We use @ to denote element-wise product. For an integer n, we use [n] to denote the set of integers .1. there exists a constant C such that I Cy, x 2 Cy. x = Cy respectively. We use Ô, Q and Ô to hide polylogarithii factor in these notations. Finally, we use poly(u) if (v))) for some positive constant C, and x poly log y if x = poly(logyy)
We use O x Oy x ( to denote that
2.1 SETTINGS
Definition 2.1 (Data distribution of K classes). Consider we are given the set of signal vectors J { where I > 0 denotes the strength of the signal, and e; denotes the i-th standard basis vector with its i-th entry being 1 and all other coordinates being O. Each data point (x, y) with x = x E Rdd and E [K] is generated from the following distribution D:
1. The label y is generated from uniform distribution over [K].
2. A noise vector & is generated from the Gaussian distribution (0,
3. With probability 1/2, assign X1 Myy Py: X1 = & where My = pey-
X2 -: with probability 1/2, assign X²
The sparse signal model is motivated by the empirical observation that during the process of training neural networks, the output of each layer of ReLU is usually sparse instead dense. This is partially due the fact that in practice the bias term in the linear layer is used (Song et al., 2021). For samples from different classes, usually a different set of neurons fire. Our study can be seen as a formal analysis
pruning the second last layer of a deep neural network in the layer-peeled model as in Zhu et al. (022T); Zhou et al. (2022). We also point out that our assumption on the sparsity of the signal is necessary for analysis. If don't have this sparsity assumption and only make assumption on the & norm of the signal, then in the extreme case, the signal is uniformly distributed across all coordinate and the effect of pruning to the signal and the noise will be essentially the same: their l norm will both be reduced by a factor of vp.
Network architecture and random pruning. We consider two-layer convolutional neural net- work model with polynomial ReLU activation (22) = (max(0, 0, 2 >});, where we focus on the case when q = 3 T The network pruned at the initialization by mask M where each entry in the mask M is generated i.i.d. from Bernoull(p). Let mj,, denotes the r-th row of Mj. Given the data (x, v), the output the neural network can be written as F(W O M, x) = (Fi (W, O M x), F2 W2 M2, x), x)...., (W& & O Mr, x)) where the j-th output is given by
W O M,, = Σ (a((w, @ mj.,, x1)) + o(Wwrr @ mj, x2)]
1=1
m
Σ (lo(WW @ mj.r 14) ((w,r myr, E)-
The mask M is only sampled once at the initialization and remains fixed through the entire training process. From now on, we use tilde over a symbol to denote its masked version, e.g., W W O M and j Wjr m
Since μy @ mj = 0 with probability 1 p. some neurons will not receive the corresponding signal at all and will only learn noise. Therefore, for each class j E [k], we split the neurons into two sets based on whether it receives its corresponding signal or not:
S Sigmat (r [m] μy ② mj. 0).
S (r [mn] My mj.r = 0}.
Gradient descent algorithm. We consider the network is trained by cross-entropy loss with soft- 20000)
max. We denote by logit,(F,x) = EJEny doo and the cross-entropy loss can be written as
'e point out that as many previous works (Allen Zhu Li 2020 Zou et al 2021 Cao et al 2022
polynomial ReLU activation can help simplify the analysis of gradient descent, because polynomial ReLU activation can give much larger separation of signal and noise (thus, cleaner analysis) than ReL.U. Our analysis he generalized to ReL.U activation by using the arguments in (Allen-Zhu & []] 2022
4

---

Under review as a conference paper at ICLR 2023
((F(x.y) = - log logit,, x). The convolutional neural network is trained by minimizing the empirical cruss-entropy loss given by
Ls(W)= =
(F(W & M. = (W & M.).,;)),,
where S = ((xx;; Ui) M== is the training data set. Similarly, we define the generalization loss as
Lp = ((((W @ M;x,
The model weights are initialized from a i.d.d Gaussian (0, of). The gradient of the cross-entropy loss is given by f',, = (" w:) logit, (F, x.) I[j -y:). Since
Vw5,. L W C M)= = V Vw W Om, Ls( O M) @ my V VWg.. Ls W) @ mj.r:
we can write the full-batch gradient descent update of the weights as
(++1)
w (1) jrr
V
Ls W) @ mmjr
dr
(1) 3.
( ((w0)7.5))
o'
Ej.,
Σ (()) 3s
(. py 3 mjjs
for [K] and r E [ml, where Ej.r, = O m
Condition 2.2. We consider the parameter regime described as follows: (1) Number of classes
K O(log d). (2) Total number of training samples = poly log (3) Dimension d 2 Ca for some sufficiently large conslant Ca- (4) Relationship between signal strength and noise strength: 22(poly log d). (6) (7) Learning rate: 2111 poly(d) s n S (1)222).
= O(a, Vog d) = ((1). (5) The number of neurons in the network
Initialization variance: on Om "nn""nn" "n='"="), (7) (8) Target training loss: = (1/ poly(d)).
Conditions (1) and (2) ensure that there are enough samples in each class with high probability. Condition (3) ensures that our setting in high-dimensional regime. Condition (4) ensures that the full model can be trained to exhibit good generalization. Condition (5), (6) and (7) ensures that the neural network is sufficiently overparameterized and can be optimized efficiently by gradient descent. Condition (7) and (8) further ensures that training time is polynomial in d. We further discuss the practical consideration of y) and to justify their condition in Remark D.9
3
MILD PRUNING
3.1 MAIN RESULT
The first main result shows that there exists a threshold on the pruning fraction p such that pruning helps the neural network's generalization.
Theorem 3.1 (Main Theorem for Mild Pruning, Informal). Under Condition 2.2 if E [C1 log 1] for some constant Cr then with probability at least O(d-1) over the randomness in the data, 2-9 "= 1 K²m 1 -te such
network initialization and pruning, there exists T Ö(Kn 0g that
The training loss below e: Ls( (W()) S.e
2. The generalization loss can be bounded by LD(W(T) & O(Ke) + exp(-n2
Theorem 3.1 indicates that there exists threshold in the order of θ (on such that if is above this threshold (i.e., the fraction of the prumed weights is small), gradient descent able to drive the training loss towards zero (as item claims) and the overparameterized network achieves good testing performance (as item claims). In the next subsection, we explain why pruning can help generalization via outline of proof, and defer all the detailed proofs in Appendix D
5

---

Under review as a conference paper at ICLR 2023
3.2 PROOF OUTLINE
Our proof contains the establishment of the following two properties:
First we show that after mild pruning the network is still able to learn the signal, and the magnitude of the signal in the feature is preserved.
Then we show that given new sample, pruning reduces the noise effect in the feature which leads to the improvement of generalization.
We first show the above properties for three stages of gradient descent: initialization, feature growing phase, and converging phase, and then establish the generalization property.
Initialization. First of all, readers might wonder why pruning can even preserve signal at all. Intu- itively, a network will achieve good performance its weights are highly correlated with the signal (i.e., their inner product is large). Two intuitive but misleading heuristics are given by the following:
Consider fixed neuron weight. At the random initialization, in expectation, the signal correlation with the weights is given by Ew,m! (w @ m, n1) 1] S prof and the noise cor- relation with the weights is given by w... (w @ m. 3 [] S v /...m. ((w ( m, E)
Juon pd by Jemsen's 's inequality. Based on this argument, taking a sum over all the neu- rons, pruning will hurt weight-signal correlation more than weight-noise correlation.
Since we are pruning with Bernouli(p), a given neuron will not receive signal all with probability 1 - p. Thus, there is roughly p fraction of the neurons receiving the signal and the rest p fraction will be purely learning from noise. Even though for every neuron, roughly v/p portion of & mass from the noise is reduced, at the same time, pruning also creates p fraction of neurons which do not receive signals at all and will purely output noise after training. Summing up the contributions from every neuron, the signal strength is reduced by a factor of p while the noise strength is reduced by a factor of vp. We again reach the conclusion of pruning under any rate will hurt the signal more than noise.
The above analysis shows that under any pruning rate, it seems pruning can only hurt the signal more than noise at the initialization. Such analysis would be indicative if the network training is under the neural tangent kernel regime, where the weight of each neuron does not travel far from its initialization so that the above analysis can still hold approximately after training. However, when the neural network training is in the feature learning regime, this average type analysis becomes misleading. Namely, in such regime, the weights with large correlation with the signal at the initialization will quickly evolve into singleton neurons and those weights with small correlation will remain small. In our proof, we focus the featuring learning regime, and analyze how the network weights change and what are the effect of pruning during various stages of gradient descent.
We now analyze the effect of pruning on weight-signal correlation and weight noise correlation at the initialization. Our first lemma leverages the sparsity of our signal and shows that if the pruning is mild, then it will not hurt the maximum weight-signal correlation much at the initialization. On the other hand, the maximum weight-nois noise correlation is reduced by a factor of vp.
Lemma 3.2 (Initialization). With probability at least 1 - 2/d, for all i [n].
000n Vpd S max (w))) E, s 22 K Kmd)ooo v pd. Further, suppose pm 2 ((log(Kd)) (dd). with probability 2/d, for all j E [K].
oo |1llll2 S max (w!0) s..... S / lo2lo0pmmkk
||
rES)
Given this lemma, now prove that there exists at least neuron that is heavily aligned with the signal after training. Similarly to previous works (Allen-Zhu & Li 2020 Zou et al. 2021 Cao et al. 2022), the analysis is divided into two phases: feature growing phase and converging phase.
Feature Growing Phase. In this phase, the gradient of the cross-entropy is large and the weight- signal correlation grows much more quickly than weight-noise correlation thanks to the polynomial ReLU. We show that the signal strength is relatively unaffected by pruning while the noise level is reduced by factor of vp.

---

Under review as a conference paper at ICLR 2023
Lemma 3.3 (Feature Growing Phase, Informal), Under Condition 2.2 there exists time T1 such that
1. The max wiight-signal correlation is large: max,
Jor
(Tt) Ma)
2 m m-1/// for [K]
2. The weight-noise and cross-class weight-signal correlations are small: if j + yi, then maxjor
E. & O(agon./p)) and maxj,r.
{ w (Ti) J.r H4 O(oop).
Converging Phase. We show that gradient descent can drive the training loss toward zero while the signal in the feature still large. An important intermediate step our argument the development of the following gradient upper bound for multi-class cross-entropy loss which introduces an extra factor of K in the gradient upper bound.
Lemma 3.4 (Gradient Upper Bound, Informal). Under Condition
2.2
we have
V @ M
(W()).
Proof Sketch. To prove this upper bound, note that for given input (x,, Vi). (()) V (xx) should make major contribution to
V
W; x; m)|l= Further note that (2()) sc.i = logit (F; x.) =
Eien, 2200)) Exsy, e0000)
Now, apply the property that (x,) is small for j * y: (which we prove in the appendix). the numerator will contribute factor of K. To bound the rest, we utilize the special property of multi-class cross-entropy loss: |C((0) |6(0) e! However, naive application of this inequality will result in factor of K3 instead K in our bound. The trick is to further use the fact that Ejzy. 1970 we.al
E,e500 I
Using the above gradient upper bound, we can show that the objective can be minimized.
Lemma 3.5 (Converging Phase, Informal). Under Condition 2.2 there exists T2 such that for some time E TT,,Ty we have
1. The results from the feature growing phase (Lemma 3.3 hold up to constant factors.
2. The training loss is small Ls(W (W())) <.
Notice that the weight-noise correlation still remains reduced by a factor of vp after training. Lemma 3.5 proves the statement of the training loss in Theorem 3.1
Generalization Analysis. Finally, we show that pruning can purify the feature by reducing the variance of the noise by factor of p when new sample is given. The lemma below shows that the variance weight-noit noise correlation for the trained weights is reduced by a factor p.
Lemma 3.6. The neural network weight W after training satisfies that
(2m) 4/4 (-1 (To(oo
max E) (2m)- 2/q < 2Kmexp
(w
& drr
Using this lemma, we can show that pruning yields better generalization bound (i.e., the bound on the generalization loss) claimed in Theorem 3.1
4 OVER PRUNING
Our second result shows that there exists a relatively large pruning fraction (i.e., small p) such that the learned model yields poor generalization, although gradient descent is still able to drive the training error toward zero. The full proof is defered to Appendix E
Theorem 4.1 (Main Theorem for Over Pruning, Informal). Under Condition 2.2 O Km log
then with probability at least 1-1/ poly log over the randomness in the data, network initialization and pruming, there exists T 0mn--'aa 20 (pd)- 9/2 -1 1mmm nonnna,," (pd)-1) such that
7

---

Under review as a conference paper at ICLR 2023
1. The training loss is below Ls( (TT) Sc. 2. The generalization loss is large: Lp (W() K)
Remark 4.2. The above theorem indicates that in the over-pruning case, the training loss can still go to zero. However, the generalization loss our neural network behaves no much better than random guessing, because given any sample, random guessing will assign each class with probability 1/K, which yields a generalization loss of log K. The readers might wonder why the condition for this to happen is O Km log a) instead of O Rmmlog Indeed, the generalization will still be bad if p too small. However, now the neural network not only unable learn the signal but also cannot efficiently memorize the noise via gradient descent.
Proof Outline. Now we analyze the over-pruning case. We first show that there a good chance that the model will not receive any signal after pruning due the sparse signal assumption and mild overparameterization of the neural network. Then, leveraging such property, we bound the signal and weight-noise properties for the feature growing and converging phases of gradient descent, as stated in the following two lemmas, respectively. Our result indicates that the training loss can still be driven toward zero by letting the neural network memorize the noise, the proof of which further exploits the fact that high dimensional Gaussian noise are nearly orthogonal.
Lemma 4.3 (Feature Growing Phase, Informal). Under Condition
2.2 there exists T1 such that
Some weights has large correlation with noise: max,
W E: -m-1/9 for all foralli
e [n].
The cross-class weight-noise and weight-signal correlations are small: if j + ys. then
(Ti)
(TT) Ö(0oo ppd) and maxj,r. jrr pmx Ö(op)).
maxjoni
2.2 there exists time T2 such that St [TiTh, To), the results from phase still holds (up to constant factors) and (s(W()) S.
Lemma 4.4 (Converging Phase, Informal). Under Condition
Finally, since the above lemmas show that the network is purely memorizing the noise, we further show that such a network yields poor generalization performance as stated in Theorem 4.1
5
EXPERIMENTS
5.1
SIMULATIONS TO VERIFY OUR RESULTS
In this section, conduct simulations verify our results. We conduct our experiment using binary classification task and show that our result holds for ReLU networks. Our experiment settings are the follows: we choose input to be x [x] x2] [yee, {] E 880 and x1, X2 E R-00 where & is sampled from a Gaussian distribution. The class labels are (+1). We use 100 training examples and 100 testing examples. The network has width 150 and is initialized with random Gaussian distribution with variance 0.01. Then, p fraction of the weights are randomly pruned. We use the learning rate of 0.001 and train the network over 1000 iterations by gradient descent.
The observations are summarized as follows. In Figure 2a when the noise level is an 0.5. the pruned network usually can perform the similar level with the full model when p S 0.5 and noticably better when p 0.3. When p > 0.5, the test eиror increases dramatically while the training accuracy still remains perfect. On the other hand, when the noise level becomes large on (Figure 2b), the full model can no longer achieve good testing performance but mild pruning can improve the model's generalization. Note that the training accuracy in this case is still perfect (omitted in the figure). We observe that in both settings when the model test error is large, the variance is also large. However, in Figure [bb despite the large variance, the mean curve is already smooth. In particular, Figure 2c plots the testing eиror over the training iterations under p 0.5 pruning rate. This suggests that pruning can be beneficial even when the input noise is large.
5.2 ON THE REAL WORLD DATASET
To further demonstrate the mild/over pruning phenomenon, we conduct experiments on MNIST (Deng 2012) and CIFAR-10 (Krizhevsky al. 2009) datasets. We consider neural network
8

---

Under review as a conference paper at ICLR 2023
Trahi Brer over Pruning Rotes Teaing Traniig ere
Tradin Brorover Rates
Testing erro
0.50
6.15
1.20
600
0.25
130
puuning 0.6
Pruning
(b)
(C)
Figure 2: Figure (a) shows the relationship between pruning rates and training/testing error under noise variance On 0.5. Figure (b) shows the relationship between pruning rates p and testing error under noise variance nn = 1. The training error is omitted since it stays effectively at zero across all pruning rates. Figure (c) shows a particular training curve under pruning rate p 50% and noise variance o, = 1. Each data point is created by taking an average over 10 independent runs.
NLP WhJST
VSG 15 CIAA-20 Accumsty
97.5
18tan Thard
Aaccan Itare
97.3
2C 350 010000
(a)
(b)
Figure 3: Figure (a) shows the result between pruning rates p and accuracy MIPP-1024-1024
MNIST. Figure (b) shows the result on VGG-16 on CIFAR-10, Each data point is created by taking an average over independent runs.
chitectures including MLP with 2 hidden layers of width 1024, VGG, ResNets (He et al. 2016) and wide ResNet (Zagoruyko Komodakis 2016). In addition random pruning, we also add pruning Frankle & Carbin (2018) into our experiments. Both pruning methods are prune-at-initializatio methods. Our implementation based on Chen et al. (2021c).
Under the real world setting, we do not expect our theorem to hold exactly. Instead, our theorem implies that (1) there exists threshold such that the testing performance (or sometimes may slightly better than) its dense counter part; and (2) the training error decreases later than the testing error decreases. Our experiments on MLP (Figure 3a) and VGG-16 (Figure (b) show that this is the case: for MLP the test accuracy is steady competitive its dense counterpart when the sparsity less than 79% and 36% for VGG-16. We further provide experiments on ResNet in the appendix for validation of our theoretical results.
no much worse than
DISCUSSION AND FUTURE DIRECTION
In this work, we provide theory on the generalization performance of pruned neural networks trained by gradient descent under different pruning rates. Our results characterize the effect of pruning under different pruning rates: the mild pruning case, the signal in the feature is well cell-preserved and the noise level is reduced which leads to improvement in the trained network's generalization; on the other hand, over pruning significantly destroys signal strength despite of reducing noise variance. One open problem on this topic still appears challenging. In this paper, characterize two cases of pruning: in mild pruning the signal is preserved and over pruning the signal is completely is not cell-understood. Further,
destroyed. However, the transition between these two would be interesting to consider more general data distribution, and understand how pruning affects training multi-layer neural networks. We leave these interesting directions as future works.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. arXiv preprint arXiv:2012.09816 2020.
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 977-988. IEEE, 2022.
Zeyuan Aluen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, pp. 242 252. PMLR, 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op-
timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems, 32, 2019.
Yuan Cao, Zixiang Chen, Mikhail Belkin, and Quanquan Gu. Benign overfitting in two-layer con- volutional neural networks. arXiv preprint 220.002200.06626, 2022.
Tianlong Chen, Zhenyu Zhang, Santosh Balachandra, Haoyu Ma, Zehao Wang, Zhangyang Wang. et al. Sparsity winning twice: Better robust generalization from more efficient training. In Inter- national Conference on Learning Representations, 2021a.
Tianyi Chen, Bo Ji, Tianyu Ding, Biyi Fang, Guanyi Wang. Zhihui Zhu, Luming Liang, Yixin Shi, Sheng Yi, and Xiao Tu. Only train once: A one-shot neural network training and pruning framework, Advances in Neural Information Processing Systems, 34, 2021b.
Xiaohan Chen, Yu Cheng, Shuohang Wang, Zhe Gan, Jingjing Liu, and Zhangyang Wang. The elastic lottery ticket hypothesis. Github Repository, MIT License, 2021c
Zixiang Chen, Yuan Cao, Quanquan Gu, and Tong Zhang. A generalized neural tangent kernel analysis for two-layer neural networks. Advances Neural Information Processing Systems, 33: 13363-13373, 2020a.
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much ver-paraaeeterization is suf- ficient to learn deep relu networks? In International Conference Learning Representations, 2020b.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. Advances in neural information processing sys- fems, 31, 2018
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems, 32, 2019.
Li Deng. The mnist database of handwritten digit images for machine learning research [best of the web]. IEEE signal processing magazine, 29(6): 141-142, 2012.
Shaojin Ding, Tianlong Chen, and Zhangyang Wang. Audio lottery: Speech recognition made light--igttt,iigt,, noise-robust, and transferable. In International Conference on Learning Repre- sentations, 2021.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference machine learning, pp. 1675- 1685. PMLR. 2019.
Utku Evei, Trevor Gale. Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pp. 2943-2952. PMLR, 2020.
10

---

Under review as a conference paper at ICLR 2023
Cong Fang, Jason Lee, Pengkun Yang, and Tong Zhang. Modeling from features: mean-field framework for werrparameterized deep neural networks. Conference on learning theory, pp- 1887-1936. PMLR, 2021.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representutions, 2018.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Pruning neural net- works at initialization: Why are we missing the mark? In International Conference on Learning Representations, 2020.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv 2019.
preprint
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural net- works. In Proceedings of the IEEE international conference computer vision, pp. 1389-1397, 2017.
Zheng He, Zeke Xie, Quanzhi Zhu, and Zengchang Qin. Sparse double descent: Where network pruning aggravates overfitting. In International Conference on Machine Learming, pp. 8635- 8659. PMLR, 2022.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, 31, 2018.
Siddhant Jayakumar, Razvan Pascanu, Jack Rae, Simon Osindero, and Erich Elsen. Top-kast: Top-k always sparse training. Advances in Neural Information Processing Systems, 33:20744-20754, 2020.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve ar- bitrarily small test error with shallow relu networks. In International Conference on Learning Representations, 2019.
Jeremy Kepner and Ryan Robinett. Radix-net: Structured sparse matrices for deep neural net- works. In 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 268-274. IEEE, 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. Snip: Single-shot network pruning based on connection sensitivity. In International Conference on Leurning Representatiinss 2018.
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Zahra Atashgahi, Lu Yin, Huanyu Kou, Li Shen, Mykola Pechenizkiy, Zhangyang Wang, and Decebal Constantin Mocanu. Sparse training via boosting pruning plasticity with neuroregeneration. Advances in Neural Information Processing Systems, 34, 202
Shiwei Liu, Tianlong Chen. Xiaohan Chen, Li Shen, Decebal Constantin Mocanu, Zhangyang Wang, and Mykola Pechenizkiy. The unreasonable effectiveness of random pruning: Return of the most naive baseline for sparse training. In International Conference on Learning Representations, 2021b.
11

---

Under review as a conference paper at ICLR 2023
Shiwei Liu, Decebal Constantin Mocanu, Amarsagar Reddy Ramapuram Matavalam, Yulong Pei, and Mykola Pechenizkiy. Sparse evolutionary deep learning with over one million artificial neu- rons commodity hardware. Neural Computing and Applications, 33(7):2589-2666 2021c.
Shiwei Liu, Lu Yin, Decebal Constantin Mocanu, and Mykola Pechenizkiy. Do actually need dense overrparamettrrizatonn?? in-time over-paramettrrizaioo in sparse training. In International Conference on Machine Learning, pp. 6989-7000. PMLR, 2021d.
Tianlin Liu and Friedemann Zenke. Finding trainable sparse networks through neural tangent trans- fer. In International Conference on Machine Learning, pp. 6336-6347. PMLR, 2020.
Jian-Hao Luo and Jianxin Wu. An entropy-based pruning method for cnn compression. arXiv
preprint arXiv: 700.00591, 2017.
Eran Malach, Gilad Yehudai, Shai Shalar-Schwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In International Conference on Machine Learning, pp. 6682- 6691. PMLR, 2020.
Zelda Mariet and Suvrit Sra. Diversity networks: Neural network compression using determinantal point processes. arXiv preprini urXiv: 2015.
Decebal Constantin Mocanu, Elena Mocanu, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta. A topological insight into restricted boltzmann machines. Machine Learning, 104(2): 243 2016.
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connec- tivity inspired by network science. Nature communications, 9(I):1-12, 2018.
Molchanov, S Tyree, T Karras, T Aila, and Kautz. Pruning convolutional neural networks for resource efficient inference. In 5th International Conference on Learning Representations, ICLR 2017-Conference Track Proceedings, 2019.
Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In International Conference Machine Learning, pp- 4646-4655. PMLR, 2019.
Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparaneterrizaton:: Global con- vergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory. 1(1):84-105, 2020.
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Optimal lottery tickets via subset sum: Logarithmic over peer-paramtteiizattonn is sufficient. Advances in Neural Information Processing Systems, 33:2599-2610, 2020.
Alexandra Peste, Eugenia lofinova, Adrian Vladu, and Dan Alistarh. Acide: Alternating com- pressed/decomppessedd training of deep neural networks. Advances in Neural Information Pro- cessing Systems, 34, 2021.
Ameya Prabhu, Girish Varma, and Anoop Namboodiri. Deep expander networks: Efficient deep networks from graph theory. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 20-35, 2018.
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Raste- gari. What's hidden in a randomly weighted neural network? In Proceedings of the IEEE CVF Conference Computer Vision and Pattern Recognition, pp. 11893-11902, 2020.
Grant M Rotskoff and Eric Vanden-Eijnden. Neural networks as interacting particle systems: Asymptotic convexity of the loss landscape and universal scaling of the approximation error. stat, 1050:22. 2018.
Zhenmei Shi, Junyi Wei, and Yingyu Liang. A theoretical analysis feature learning in neural networks: Emergence from inputs and advantage over fixed features. In International Conference Learning Representations, 2021.
12

---

Under review as a conference paper at ICLR 2023
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A law of large numbers. SIAM Journal on Applied Mathematics, 80(2):725 2020.
Mei Song, Andrea Montanari, and P Nguyen. A mean field view of the landscape two-layers neural networks. Proceedings of the National Academy of Sciences,
2018.
Zhao Song and Xin Yang. Quadratic suffices for parammetttttiiinoonnn via matrix chernoff bound. arXiv preprint arXiv:1906.03593, 2019.
Zhao Song, Shuo Yang, and Ruizhe Zhang. Does preprocessing help training weer-parameterized
neural networks? Advances in Neural Information Processing Systems, 34, 2021.
Kartik Sreenivasan, Shashank Rajput, Jy-yong Sohn, and Dimitris Papailiopoulos. Finding every- thing within random binary networks. arXiv preprint arXiv:21 10.00999, 2021.
Kartik Sreenivasan, Jy-yong Sohn, Liu Yang, Matthew Grinde, Alliot Nagle, Hongyi Wang, Kang- wook Lee, and Dimitris Papailiopoulos. Rare gems: Finding lottery tickets at initialization. arXiv preprint arXiv:2202. 12002, 2022.
Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang, and Jason Lee. Shnity-c pruning methods: Random tickets can win the jackpot. Advances in Neural Information Processing Systems, 33:20390-20401, 2020.
Xavier Suau, Luca Zappella, and Nicholas Apostoloff. Network compression using correlation analysis of layer responses. 2018.
Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. Advances in Neural Information Pro- cessing Systems, 13:6377-6387 2020.
Matus Telgarsky. Feature selection with gradient descent two-layer networks in low-rotation regimes. arXiv preprint 0227092208.02789, 2022.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference Learning Representations, 2019.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. Advances in Neural Information Processing Systems, 32, 2019.
Huanrui Yang, Wei Wen, and Hai Li. Deephoyer: Learning sparser neural network with differen- tiable scale-invariant sparsity measures. In International Conference on Learning Representa- tions, 2020. URL
net www.:/eeeneettooottiddddree.....
Qing Yang. Jiachen Mao. Zuoguan Wang, and "Helen" Li Hai. Dynamic regularization activation sparsity for neural network efficiency improvement. ACM Journal on Emerging Technologies in Computing Systems (JETC), 17(4):1-16, 2021.
Mao Ye, Chengyue Gong, Lizhen Nie, Denny Zhou, Adam Klivans, and Qiang Liu. Good sub- networks provably exist: Pruning via greedy forward selection. In International Conference on Machine Learning, pp. 10820-10830. PMLR, 2020.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In British Machine Vision Conference 2016. British Machine Vision Association, 2016.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. Advances in neural information processing systems, 32, 2019.
Jinxin Zhou, Xiao Li, Tianyu Ding, Chong You, Qing Qu, and Zhihui Zhu. On the optimization landscape of neural collapse under mse loss: Global optimality with unconstrained features. arXiv preprint a2Xi::2003.0 20..0/23....... 2022.
Zhihui Zhu, Tianyu Ding, Jinxin Zhou, Xiao Li. Chong You, Jeremias Sulam, and Qing Qu. A ge- ometric analysis of neural collapse with unconstrained features. Advances in Neural Information Processing Systems, 34, 2021.
13

---

Under review as a conference paper at ICLR 2023
Difan Zou and Quanquan Gu. An improved analysis of training over- par--ataamttezed deep neural networks. Advances in neural information processing systems, 32, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine Learning, 109())4467-99,, 2020.
Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu. Understanding the generalization of adam in learning neural networks with proper regularization. arXiv preprint arXiv:2108. 2021.
14

---

Under review as a conference paper at ICLR 2023
A EXPERIMENT DETAILS
The experiments of MLP, VGG and ResNet-32 ResNet-20-12 is run on 4 NIVIDIA V100s. We list the hyperparameters we used in training. All of our models are trained with SGD and the detailed settings are summarized below.
NVIDIA A5000 and ResNet-50 and
Table 1: Summary of architectures, dataset and training hyperparameters
MODEL
DATA
EPOCH
BATCH SIZE
LR
MOMENTUM
LR DECAY, EPOCH
WEIGHT DECAY
LENET
MNIST
120
128
0.1
0
VGG RESNETS
CIFAR-10
160
128
0.1
0.9
0.1 X [80, 120
0,0001
CIFAR-10
160
128
0.1
0.9
0.1 [80, 120]
0.0001
B FURTHER EXPERIMENT RESULTS
We plot the experiment result of ResNet-20- 128 in Figure 4 This figure further verifies our results that there exists pruning rate threshold such that the testing performance of the pruned network is on par with the testing performance of the dense model while the training accuracy remains perfect.
Smmhet-20-12 CPAR-SC
00
Aunky most
BY (Tee)
Figure 4: The figure shows the experiment results of ResNet-20-125 under various sparsity by ran- dom pruning and IMP. Each data point is averaged over runs.
C PRELIMINARY FOR ANALYSIS
In this section, we introduce the following signal-noise decomposition of each neuron weight from Cao et al. (2022). and some useful properties for the terms in such decomposition, which are useful in our analysis.
Definition C.1 (signal-noise decomposition). For each neuron weight j [K], e [m], there exist (t) ((t) (t)
coefficients kj.rk Sjr,, jar
W such that
W (0)
K
j.r.k
| 11
14 O mj.
+
(t) jurd
Egrre
2
Exri +
w
(t) Jorss
Eirrs
|| 2
1=1
im
where (1)
Fz.r. 2 0, 7
(1)
5 50,
S),r. > (!)
(1))
50 0.
15

---

Under review as a conference paper at ICLR 2023
It is straightforward to the following:
(0)
Yrink Sj,r, j.r, O,
(++1) (t)
11(r E S
(11) 33
-o' (( (y: l1 11uiil22 1121(1: [lu - =j);
Vin "jrs
signal
1=1
(1+1) (1)
I((m),)) = 1)
(())
o' ((
(w jirt Hy. pe 112 (/1 = k), vj # h.
Birkk 1jnnk
1.3
12
(1+1) (0)
(1)
o' ((w))r
Iíj yi),
n
(1+1) W.rr
! (()) o' (( . || I(j # vi).
71
12 {w (.r,tli are decreasing where (0 (ijnjii=1 (j [=1 are increasing sequences and (2 (
12'
sequences, because 1/ 2 0 when j = ys. and - -e(t) S when j * ye- By Lemma D.4 we have pd n K, and hence the of vectors {Ms K U i= is linearly independent with probability measure over the Gaussian distribution for each j [K],r [m]. Therefore the decomposition unique.
D PROOF OF THEOREM 3.1
We first formally restate Theorem 3.1
Theorem D.1 (Formal Restatement of Theorem 3.1 Under Condition 2.2 choose initialization variance do = Om *n "n=11p-)) 11=1) and learning rate r S Ó(1/2²). For 0. ifp 2 C1 logd for some sufficiently large constant C1. then with probability at least 0(d over the randommess in the data, network initialization and pruning, there exists T = Ö (1 1 2-9 9000--1-00 "p=9 K2m ---------- -1c c-1)
such that the following holds:
1. The training loss is below e: Ls( Ls(W(T) S.
(T) 2. The weights of the CNN highly correlate with its corresponding class signal: max, Ford >
90 (mmm1/9) ) for all j E [K].
3. The weights of the CNN doesn't have high correlation with the signal from different classes:
max (T) Ö(Top).
(T) 4. None of the weights is highly correlated with the noise: maXj.r. Sj.r. Ölagan vdd,, maxj,ra ( = Ö(avo, vpd).
Moreover, the testing loss is upper-bounded by
(D(W(T)) S exp()>22
The proof of Theorem 3.1 consists of the analysis of the pruning the signal and noise for three stages of gradient descent: initialization, feature growing phase, and converging phase, and the establishment of the generalization property. We present these analysis in detail in the following subsections. A special note is that the constant C' showing up in the following proof of each sub- sequent Lemmas is defined locally instead of globally, which means the constant C within each Lemma is the same but may be different across different Lemma.
D.1 INITIALIZATION
We analyze the effect of pruning on weight-signal correlation and weight- correlation at the initialization. We first present few supporting lemmas, and finally provide main result of
16

---

Under review as a conference paper at ICLR 2023
Lemma D.7 which shows that if the pruning is mild, then it will not hurt the max weight- correlation much at the initialization. On the other hand, the max weight-noist correlation is reduced by factor of vp.
Lemma D.2. Assume Q(K2 log Kd). Then, with probability at least 1 1/d.
Ki E [n] = j}l = (m//K) Vj E [K].
Proof. By Hoeffding's inequality, with probability least 1 6/2K, for fixed j [K], we have
1 Tu: j) K
log( (4K/5)
S
2n
Therefore, as long as n 2 2 log( 4K/5), we have
Σ Ily = j)
2K
Taking union bound over [K] and making 1/d yield the result.
Lemma D.3. Assume pm = (2og d) and m -poly log d. Then, with probability 1 - /d, for all
j E [K], & E [K], have (m,,)) = (pm)), which implies that (S) Signall (pm)) for all
j E [K].
Proof. When pm = (lllggd d), by multiplicative Chernoff's bound, for given A: [K]. we have
(m).)x pm 2 0.5pm
< 2exp (pm))
Take a union bound over j [K], [K]. have
P
Σ
(mjr): ) pm 2 0.5pm, Vj E [K], E [K]
I 2K2 exp (-p0-0(pm))) S 1/d.
Lemma D.4. Assume p 1/ poly log d. Then with probability at least 1 1/d, for all [K]. r E [m], E (m,,r) = ((dd).
Proof. By multiplicative Chernoff's bound, we have for a given j,
P
(m,,r)s pdl 2 0.5pd
< 2exp((-R(dd)
Take a union bound over j, r, we have
P Σ (m pd > 0.5pd, Vj E [K], [m] < 2K 22 < 1/d,
where the last inequality follows from our choices of p, K, m, d.
Lemma D.5. Suppose p (11 poly log d), and m, logylogd.
With probability at least
1 1/d, we have
O(oāpd)
(Einiser) Ex²
5 0000% po
K (Mss Exmre)
S s14 Ei) 0(o,N'/oog
for all j (-1,1), r [m], i E [n] and V.
17

---

Under review as a conference paper at ICLR 2023
Proof. From Lemma D.4 we have with probability at least 1 - 1/d,
(m, - (pd)) Vj [K], r [mm]
For a set of Gaussian random variable :
NO0, o²), by Bernstein's inequality, with
probability least 1 - 6, we have
Σ 9 N
S o²
Nlog 6"
N
Thus, by union bound over r, with probability at least 1/d, have
[Aanl] I|= P(o)
For i * i', again by Bernstein's 's bound, we have with probability at least 1 - 8,
(Simote)) s so (0
Kmm
pd log 8
for all j, r, Plugging in å = 1/d gives the result. The proof for (t,, E,) is similar.
Lemma D.6. Suppose we have independent Gaussian random variables 91, 92, ....... Jm. (0, Then with probability 1 - 5,
m
max 9i 2 log log 1/6"
Proof. By the standard tail bound of Gaussian random variable, we have for every x > 0,
( x3
x² /202
x² /20²
Pg x]
2
2t
We want to pick a xx such that
P max S x² = (P 1g: S x²1) (1 - [g: 2 x²1) S -m-mplo:2x1 26
Plg: 2 x=)= = (100((1/)
log(1/5)
m
= O(o Volooolo(mm (log///0l log m))).
Lemma D.7 (Formal Restatement of Lemma 3.2
With probability at least 1 2/d for all i E [n],
Joon Vpd < max (~(0)) j.r E: s (2llo((Kd))or)) v pd.
Further, suppose pm ((log(Kd)) Then with probubility 1 2/d, all [K].
on |1lll122 S max (w!)) (irrHH)) S <22log(SpmKd)on ||
rest Sigsal
Proof. We first give a proof for the second inequality. From Lemma D.3 we know that |S] |S) O(pm). The upper bound can be obtained by taking union bound over E Signat j [K]. To prove the lower bound, applying Lemma D.6 with probability at least - 8/ K, we have for a given j E [K]
pm
max rEst Renal
W jir Mb) 2 au ||
log
log K/6"
Now, notice that we can control the constant in pm (by controlling the constant in the lower bound Thus, taking union bound over j E [K] and setting 8 1/d
of p) such that pm/logg (K)( yield the result.
The proof of the first inequality is similar.
18

---

Under review as a conference paper at ICLR 2023
D.2 SUPPORTING PROPERTIES FOR ENTIRE TRAINING PROCESS
This subsection establishes a few properties (summarized in Proposition D.10 that will be used in the analysis feature growing phase and converging phase of gradient descent presented in the next two subsections. Define T n poly(L/e,, p,, d. Fx .00 n, m, d). Denote
(log (T*)) B 2 maxi.j.k holds for our subsequent analysis.
{|( ( jir: MA
E:
We need the following bound
4m 4m/ 1/9 max Jard
(0) brr Cna
pvlog d anpd
(0) Ei
3Cnay
log pd
Remark D.8. To see why Equation (1) can hold under Condition 2.2 we converteverytthingg in terms of d. First recall from Condition 2.2 that m, poly d) and μ O(a,, vd = ( In both mild pruning and over pruning we require p 2 (2(1/pol) log d). Since = ((log\/((T)) if we assume T I (ppoly(d) for moment (which we are going to justify in the next paragraph), (log+/((d)) Then if we set d to be large enough, we have 4m H/logd aapd < 1. Finally for the quantity 4m max 3.rr (w( E.)), by Lemma 3.2
then
poly log d
vd
our assumption of K O(log d) in Condition 2.2 and our choice dg = @mm-An p-)) in Theorem 3.3 (or Theorem we easily see that this quantity can also be made smaller than 1.
Now, to justify that < (poly(dd), we only need to justify that the quantities T depend on polynomial in d. First of all. based on Condition 2.2 n. m poly log(d) and μ = ( d d) = (1) further implies o,-² = Ool d). Since Theorem 3.1 only requires on = 6 fon--"n- 1-),, this implics 0 < Oppoly log d). Hence 0 in n = Oppoly log d). Together with our assumption have justified that all terms involved T are at most order poly(d). Hence T = poly(d).
that n 2 pol))() (which implies 1/e, 1/n s O(poly(d)).
Remark D.9. Here we make remark on our assumption on and 1) in Condition 2.2
For our assumption on e, since the cross-entropy loss is (1) not strongly-convex and (2) achieves its infimum at infinity. In practice, the cross-entropy loss is minimized to a constant level, say 0.001. We make this assumption to avoid the pathological case where is exponentially small in d (say c= 2) which is unrealistic. Thus, for realistic setting, we assume e 2 2(1/ ((l//))l((d) or 1/c S (ppoly(d)).
To deal with the only restriction we have is = 0(1/n²) in Theorem 3.1 and Theorem 4.1 However, in practice, we don't use learning rate that is exponentially small, say rj 2-4 Thus, like dealing with e, assume (211 poly(d) or 1/n Oppoly d).
We make the above assumption to simplify analysis when analyzing the magnitude of (x) for j * y given sample (X.y).
Proposition D.10. Under Condition 2.2 during the training time < T*, we have
(t) (1) 1. Janj Sjn a.
2. w jrnt 2 -3 -
(1)
6Cnna V
log d pd
3. jirk 2 -3 2Cna uy/logd
(t)
o.pd
Notice that the lower bound has absolute value smaller than the upper bound.
Proof of Proposition D.10 use induction to prove Proposition D.10
Induction Hypothesis: Suppose Proposition 1.10hhlds for all L < T T
We next show that this also holds for T via the following few lemmas.
19

---

Under review as a conference paper at ICLR 2023
Lemma D.11.
Under Condition 2.2. for t < T, there exists constant C such that
((())
Jir
(0)
m4:
j.nk = Cna
(8)
uVoog d anpd
1((m),)) = 1),
log d
w
w j,r( E,)
Sj.r.3 + =3Cnay
5.
pd
(0) Jir E,)
jint + 3Cnay
log
pd
Proof. From Lemma D.5
there exists a constant C such that with probability at least 1/d.
ESrTa Ex
log d pd
S
Sirra 112
S)rre MA6
UVoo
I C
anii
(peN, Ex)
C on Vlog
| 12
Using the signal-noise decomposition and assuming (m, )2- = 1, we have
(w (1)
(0)
(0)
Σ
(Eimss HAs
Winn ( (Eantt
(0)
5ir W j.r
-iirrk
fins
c HVlog d and
(t)
Sand
+
anpa
jing
1=1
< 20 H/gg/ooo d anpd
where the second last inequality is by Lemma D.5 and the last inequality is by induction hypothesis. To prove the second equality, for j = yb:
(EamerE)
(w(() (1)
Jir
jir
E:)
(1)
Σg
j.nck
(1)
(pn Ei)
| 12
+
(t) Sinii
n
2 S
2
2
< 0 nn v P
log d
K
C
log d
Σ 1500
+ CV.
log
1
pd
pd
k=1
==
= =
on 2n SenVogg log d
logd pdl
Ka + 2Cnay
P
logd
< 33Cog
pd
where the last inequality is by n > K and μ O(a,, Vd d). The proof for the case of j + y: is similar.
20

---

Under review as a conference paper at ICLR 2023
Lemma D.12 (Off-diagonal Correlation Upper Bound). Under Condition 2.2 we have that
for t < T, j # yo.
!0) j.r: Myy, > + Cna HVlog d anpd
w J.r H.r.
-
log d pd
wl jir: 61)
w jir: E:) + 3Cnaay
FW x4) 1
Proof. j + ys. then (1)
Fjack S and we have that
(w)))
J.r+ Myr + (15 +
uyVog
Hys
Cna
I((m)rr) = 1)
anpd
C'a "Vlogd
w (0) j.r+ (mn)
anpd
Further, we can obtain
W (1) J.r E,) S (0000 j.r,E) + WWf + 3Cnay
log d pd
logd pd
So + +3Cnay
Then, we have the following bound:
112
FW x1)
Σ (o j.m pyy)) + a ((W E/1]
UV (w/0) (w]0r wir. 3Cnay
log d pd
S mm2+1 max J.r,t
w Wirt My,
Cna
anpd
$1.
where the first inequality is by Equation Lemma D.13 (Diagonal Correlation Upper Bound). Under Condition 2.2 for t < T, j = yi we have
W jir (//0-11)) s (w()) (0)
(o0 11, + +73,n Cna
(t)
Mv log d anpd
W j.r: E, S <
(wm/00 E:) + S/r + 33Cna
log d pd
If maxx( (inns ( S m 1-19, we we further have that ( x.) S 011.
Proof. The two inequalities are immediate consequences of Lemma D.11 If max max birrs Slf S
m 1/9 we have
m
FJ xi) =
(( jor H4)) + ((W E.))
Pirr Strae (w m4 >.. (w0000 -.0.E.))))) &,/| ,Cna HVlog d
(0) (1)
log d pd
2 3dd m max j,t,
,3Cna
a,pd
< O(1.
21

---

Under review as a conference paper at ICLR 2023
Lemma D.14. Under Condition 2.2. for t S T, we have that
jinn 2 -3--6600 -36- logd. pd
2. (1) firk 2 -5 -2Cna onpd
mllog
Proof. When j = Vi. we have w j.n.
O. We only need to consider the case of j # ye. When
lond (T-1) I -0.53 3Cna /
pd by Lemma D.11 we have
w (1--1) jr E: S
( E:
(T-1)
3Cnay
log dl pel
0.
Thus,
( = - dinit
(T- o' (w (effT=")Ess)) E 1
I + vi)
(T-1)
J.r.
logd pd
B V
When w (T-1) jin.
2 -0.53 3Cna
we have v
logd pdl
w (T)
12-1)
(T- d'
(( (
Wij ..i)) [ I(i # vi)
w
jirzé
-0.33 3Cnag
logd d pd n
" " 00.58 1088+3anaa
(log dl pd
( 12
log
2 3 - 6Cnory
pd
where the last inequality is by setting S nq-1 (0.58 + 3Cna
logd d
2-9
(C20
"and C2 is
pd
the constant such that E...s | < P d for all j, Lemma D.5
For Fj.r. the proof is similar. Consider I((m})))) When Jrrnk S -0.5.3 -'a -CnoHyllod by
(t)
Hy/ood aupi
Lemma D.II we have
s.r M4s - (w(0) (M + + + Cna #vlog
anpd $ 0.
Hence,
(T-1)
[T o' ((
(T-1) 14x )) p2l(es k)
2onk
Pjank
i=1
11- Mjrn
2 -B 2Ona Mvlog d a,pd
22

---

Under review as a conference paper at ICLR 2023
When (6)
Jr., 2 -0.53
Cna
My My/oo anpd
have
(3)
(T-1)
((-
0' (( (W
(T'-1) ,u:) 1 1rll k)
jjrrc
2irck
n1
t=1
uVlog d anpd
of (0.58+ Cna Cna Hlvlog d anpal
-0.53 Cna
12
2Cna Pvlog d onpd
2 B
where the first inequality follows from the fact that there are e x samples such that T(ys = k)), and the last inequality follows from picking 7 S K0055 + Cna ey )2 -u Cr
anpd
L
Lemma D.15. Under Condition 2.2 for t S T, we have (1) (t)
jinjj Sj.z. S S a.
Proof. For + j or & S signal Ying Sj,r,5 = 0 S
(1)
(1)
yt = j. then by Lemma D.12 we have
Einzef((x) el(()) Ke
10)
logit, lFgit,(P;X))
(F:X)
D efi(X) 3
Recall that
(++1) (8)
[l(r E S
Sigmat)
Σ
((t) jit
o'
11ag,112 1(y1 = 5),
3ind Pjnn
(t+1) J.n.
j.rt
" (t)
d
2 Eins
1(j = vi).
We first bound C.rn Let T be the last time I that ((1) S 0.5c. Then we have
(Tira)
1 (TThin))) o' (( (( (.) T(u: =]) E5..
Sira
41
ATTsmn of ((with s.)) I(vi = 5) ||
fit
We bound 41, 1a separately. We first bound 1 as follows.
11 S 9d
(P...) + 0.53 + 3Cna,
log d pd
C2o S 92nn 929nn~nannn-- -n < 0.25a.
where the first inequality follows from Lemma D.13 the second inequality follows because <
0.1a and 3Cnar
logd
< 0., and the last inequality follows because -
pd
For Tiraa < < T. by Lemma D.11 we have that
(w W. E:) 2 0.5a 0.53 3Cna V
log d
>
pdd
0.25a and ( (w (
<a 0.5. + 3Cmoy
log pd < 2a.
23

---

Under review as a conference paper at ICLR 2023
Now we bound 12 as follows
12 S Σ
(Kecxp(-F)(X) ( I(ys - 1) ||5
Σ
Keeepp --o (( ( E, {:))3 o' (( ((w522))))) Ilve =) (5rss] 12
(
qKen22-'1 T
exp(-a (a/0-//9/))" /4 o pn
n
< 0.257 exp(- a
/49)a=22
S 0.25a,
where the first inequality follows from Equation equation 2 the second inequality follows because (2(X)
(( (w(r
E: ) the fourth inequality follows by choosing 1/ S n/(gKe29t1 o.,), and
the last inequality follows by choosing
((log"/((T)))
Plugging the bounds on I, /2 finishes the proof for Sj,r,
(T)
To prove (inn S a, we pick n S 1/(ge29t2 and the rest of the proof is similar.
Lemma D.14 and Lemma D.15 imply Proposition D.10holds for all S T.
Induction Ends
D.3 FEATURE GROWING PHASE
In this subsection, first present supporting lemma, and then provide main result of Lemma [.17]] which shows that the signal strength relatively unaffected by pruning while the noise level is reduced by factor of vp.
During the feature growing phase of training, the output of F₃(X) = 0(1) for all j E [K]. There- fore, logit, (F, = x and logit, (F, = O(1) until (() jir ue, reaches m m1/4
mg - C.og "(avvrd) Ca(2C,) [log 11// the
Lemma D.16. Under the same assumption as Theorem D.I for T = following results hold:
S O(1eon all e [K], r e [m], i e [m] and S T.
Jraal O( vpd) for all j E [K], E [m], i E [m]] and 1 < T.
Proof. Define vn(t) = max in Si (0 J. Then we have
((+1)
Ennee E:)
(1) + max i.n
! (()) n 1/
1100
(w/(0) .''
E.) (w.))))))
(0)
(ek, Ei}
Σ (+)
|
Yank
|| 1
E 1|3
1=
(0) + "
log doyon pd) K log 1/1 T pon Vlog d
Olokpd) + no(o v Vpd
9-1 vp(1)
Olo)pd)
42
(oRRpd)
< 100 + ! (o(vlog do pd) + ((1))))) O(oāpd)
where the second inequality follows by (5((0 and applying the bounds from Lemma last inequality follows by choosing 2K Tog
D.5 and the
Õ(1VV)) & do- Let C₁ C2, C3 be the con-
a.d.p
stants for the upper bound to hold in the big O notation. For any T xy (an C,(2C,)" dlo 1//2
24

---

Under review as a conference paper at ICLR 2023
) m1y 100-- " ( pdl [log d| (v 1372
), we use induction to show that
((() 1 Ciooon pdd pd, Vt E [T].
(3)
Suppose that Equation equation
holds for E (Ty for T' ST -. Then
1(T'+1) 1 ((T))
+ " (Civlogdooon V pd + C2Csooon Vpd pd
9-1
- ((T))
+ 7 201 VCl do v pd)
9-1
- (T' 1)" 220 v Vlogoooo v pd) 9-1
C3
n
$ T (20 log dooon V pd)
4-1
Czonpd
s C.000n
where the last inequality follows by picking T Therefore, by induction, we have (T) I Ciouon v pd for all t E [T].
Ca(2C1) yz [log 1/2 = (mm0
nn C - (andpdd"
mon o 0000000000 "0 (pd)) [log d (2111//22 13/2
Lemma D.17 (Formal Restatement of Lemma 3.3 Under the same assumption as Theorem D.
there exists time Ti log(I+0( Ju90g
log 2m 1/4
(Ki) oo " log 2m 2mm11/9) such that
(Ti) 1. max, Bird 2 m m-11/ for j E [K].
2. Iyrd So.d S O( for all E [K], r E [m], E [n] and S T₁.
3. 1790,A1 < O(oo poly log d) for all j. k E [K], j + k, r E [m]] and < Ti.
Proof. Consider fixed class j E [K].
Ti to be the last time for Dz(2C)) "log dfr 1773 satisfying max, 7j S m m-1//. Then for Ti
Denote
t. E
0. an "440) vpd)
(1)
maxjind Sjorss jinal < O(aoopypd) S O(m-2/2) and maxj,r Yinns Thus, by Lemma D.13
(1)
(0)
obtain that F3 (W(1), x:) s 011, Vy j. Thus, ((t) O(1). For j E signal we have
(c+1)
(Ennsi 11
(1) = =gind
o' (w:0) (wr +
Firn
(t)
+
Sind
1|2
Eirrs 1|3
-)
i=1
8=1
1
2
(1)
11
(1)
+ 7,r.. Onaoaapd Ondy 14/ ((w50)
(w/ (
/logd loged
T(y = j).
Let Iinn = -iiin= +
(1)
(8)
W
(0)
fire 14) )1r
Onagon v pd TuulyTo aap
and ( max,
((t) Tand Note that by
our choice of n. we have apy/oodd = o(1). Since max, (w) J.r M4) 2 Monu) by Lemma D.7 anpd
max, (w(0)) Wi 14)) 2 M(001)) - O(nogn antony Angloo adnd
= 2(oo)t). Then we have
11+1)
> A00 !
Σ 1=1
(
o' (A pp = j) JA
2 1 + 0 K
1000-11
(1+ 0 K 1 (1
2 01+0 _ 2 (0)
25

---

Under review as a conference paper at ICLR 2023
Therefore, the sequence Att will exponentially grow and will reach 2m 1//
1/9 within
2m 1/v
O(Kn 0 "0
"p= log 2m 1/9) S
"o "[an vpa)
Thus,
log(1+0( Φ 1 3) (6)
log dfto 13/2
max, 7jr A maxj,r jor Mi) 2 2m 1/9 (
2 2 m 1/9 -1/9.
Now we prove that under the same assumption as Theorem D.1 for = O(K - 9 9), we
have hig. I O((oppppoy poly log d) for all [m], j. E [K]; and - T.
We show that there exists time T > T such that for all s T', maxj.r, 1j.r,k 5 O log d). Let T = O(K3 1 00
2-4 8 logd).
Define ((1)
max,ejm), j.k[[K] ju 1h (2) 1r Since we assume T < O
lan Maaypl pd) - by
log 11/2
Lemma D.16 we have Gonn Ww - O(000n vpd).
g (t++1)
n Ily = 10
(m/0) 1ir (w.
n +
12
< (())) + max J,rkk,
7
(t) Shnpe
(()))
112
Jorie"
||g
1==1
{(1(0 + 11
(Oloop d) + nO v pd)
Toll Soffylog aapd
9-1
422
K K
(()) + (o(oop//ogd)) 9-1 2
qn
K2
where the first inequality follows because jin, < 0, the second inequality follows because there are (n/K) samples from a given class is and j.1 = O / ), and the last inequality follows because = o v d log d. Now, let C be the constant such that the above holds with big O. Then, we use induction show that ((t) C2 for all < T. We proceed as follows.
((++1) 410)
9n
(Coop//oog/ 9-1 u²
K2
9-1
T
(Coop/logd)
112
K2
C20 log d,
C2 - 1000----- Vogg C9-1
where the last inequality follows by picking
T
O(K2n 1 o0 0 9 log d).
D.4 CONVERGING PHASE
In this subsection, we show that gradient descent can drive the training loss toward zero while the signal in the feature is still large. An important intermediate step in argument is the development of the following gradient upper bound for multi-class cross-entropy loss.
In this phase, going to show that
max, Ding 2 m 1/2 for all j E [K].
max 1 S 8g where 31 = Ō(To)).
max (t) ( p fa where B2 O(a00n vpd)
Define W follows:
W j. = w jor (mmlog((/))) H4
26

---

Under review as a conference paper at ICLR 2023
Lemma D.18. Based the result from the feature growing phase, W(T) - w. (mm))--13 S
O(Km² log (1/c)/=²).
Proof.
We first compute
W ?
W
2
K m
(Tt)
My m
(Ti)
pa m
(TL)
Eiir
(Ta)
Erri
212
jirch
422
2
J.r.
2
/=
(S,rol
rj
2
2
1
2
ΣΣ
(Ti) 1
(Ti) 1
+
(Ti)
1
+
Σ
(
gir,le
Sin
Esiru
2
ΣE (ōr-) + KŌ(Go) + no(co))
2
0 +
mmmm 12
Km
where the first incquality follows from triangle inequality, the second inequality follows from Lemma D.17 and the last inequality follows from our choice of ag. On the other hand,
W
W
2
Σ 3.
m² log" (1e) 1 = O(Kmm log (1/c) 1
422
Thus, we obtain
W W+ S 4
2
W(T)) wiool +
w-| - < O(Kmm log (1/c) 1 pe))
Lemma D.19 (Gradient Upper Bound). Under Condition 2.2 for S T there exists constant
C' ===0( =0(Km2ie 2/2 max pdd)) such that
V W(0) o M
&CLs(W(O))
Proof.
We need to prove that (())
VF x.) O Ml/ S C. Assume y/ X j. Then we obtain
(B)
< >> o' (( (( ( Mhy + o' (( (w (... ) E
F
S Σ d' (( ((w/1) |H + o' (( (w/10 /orf & )) |
(9-1)/9 max(H, Co V
S 2/4 xx)
5m 1/4 max Ca V
where the first and second inequality follow from triangle inequality, the third inequality follows from Hölder's inequality, and the last inequality follows from Lemma D.12 Similarly, on the other hand, if y4 = j. then
S 5m2/g FF (W yer xi) (g-1)/9
VE W O M
max Co, Vdd.
27

---

Under review as a conference paper at ICLR 2023
Therefore,
Σ 3
1
VFy W xi) (,) M,
( 2/ (max(( popd))
1
ge Im O (m o.
and
((())
Fy, W Uc x;) ④ My. y4
F
2(4-1)/9 1)/9 O(max{p²,o
I Keexp(- F.. (x,) m 2/9
y.. (W u. xi)
where the inequality follows from Equation equation 2
Thus,
VF,
Mj
K
((())
VF,
x,) o M,
- - y, (x,) m 2/ 40 10mxx (u² ondd (Fr xi) (0-1)/9
+ +1)
yid O(Km 2/4 max( pdpd))
(4)
where the first inequality follows because | S 1. and the last inequality uses the fact that expf-x}(( + 2 12/1) (() for all 0.
The gradient norm can be bounded by
V (L( .200 2
|Ls(
11
[ ( ,x))/
4 2
VF(W
2
(((t)) O(Km2/ o
O(KmP1 maxtu? ,,,
((0)
O(Km2l 2/9 max Ls
where the first inequality uses triangle inequality, the second inequality follows because 14,9
(00 the third inequality uses the bound equation 4 the fourth inequality uses Jensen's 's inequality and the last inequality follows because ( g:")
Lemma D.20. For Ti < t < T*, we have for all j + ys.
(V xx), W;) 2 9 log 2qK
VF
( U.
xx), W 11 -
28

---

Under review as a conference paper at ICLR 2023
Proof of Lemma D.20 The proof of this lemma depends on the next two lemmas.
Lemma D.21. For Ti SLST T and j = we have (V x.), W;) > O(m²/2 log(1/e)).
Proof. By Lemma D.17 we have
Esiii M4
(Snre 14))
max {( ( ( max
(0) Jrr M4: + *
(1)
(1) Sind
Σ
(e) Jon'
Siirs ||2
2 m 1/0 Owwoooooooooooooooo - (nooon vd Hy Avllooo
Jnpd
(m 1/2),
where the last inequality follows by picking do S 0m 1(mm-nn" In 1n-11p 1-= *logg d)-1/2). On the other hand,
log d pd
a) O( ( MVVlog d andd a) S 0(1),
(t) <:
E: + W + ( + O(ng/ j.m
(0)
(5)
where the first incquality follows from Lemma D.11 and the second inequality follows from Equa- tion ① and Proposition D.10 Therefore,
x:), Wj) Σ o' (( m1)) (He, Whr) Eo' (( ((w)h--E)) (E,, wir)
Σ o' ((w/)) j.r m4j ) @(m log(1//)/)) E O(anon V onVlog
mlog(1//)) (1/c)
0(m (og((1))) Ommo v pdlo + on Vnglo
m log(1/e))
(m 1/2 log (1))))
where the last inequality follows because mooo,, Vpdlogd o(1) and Ta m² o(1) by our
choices of μ. Øv-
Lemma D.22. For Ti S t < T and j # ye, have (VE x:),
xx),, W;) 0(1)
Proof. First we have
Eg Hg
Esrris Hy
= jam My.
(w) Wrr: My. +
Pirron
(t)
Sj.ra
(t)
w
j.n
(t)
Ej.rs
100on//oogg log + onw poly log d tomoo v pd o Un MoA.yloog d aapd
<0()),
where the first inequality follows from Lemma D.7 Lemma D.5 and Lemma inequality follows from our choices of do. p. Then, we have
D.17 and the last
(W x2), W;)
(Ei, wi.)) $ mm(loop/lood + m0(ano, / /dlog d + m log(1/e) on VnVlogd 0(1),
Σ o' ((w))) (t. (Mys W Σ o' (ww/1)E))
29

---

Under review as a conference paper at ICLR 2023
where the second inequality follows from Equation equation 6 and Equation equation 5 and the last inequality follows from our choices μl, dv.
Applying the lower bound and upper bound from Lemma D.21 and Lemma D.22 we have
V Fy With yi
x;), W
VF x.), W
(m 1/9 log (1/c)) 0(1)
24
2 log
Lemma D.23. Under the same assumption as Theorem D.1 we have
W
W F
W (++)))_
w
2
2 5m 5n/ss(W(t)) - -7E.
Proof. To simplify our notation, we define (x) = (VF, x;). x:):W;) W:).
We use the fact that the network g-tewooois-ghooooagggeo g-homogeneous.
Wh(+ W I
W W
2n
Vs (1)
M. w( W+) 7/² VLs OM]
2n
xi, (W)) x:), wi)] - 1 VLs(W(()) M
qF
n
i=1
K
20
Σ
log(1 Σ FFr) log(1 Σ clf,- clfi-Ru)/0) 12 VL3 VL. ( OM
n
2qm7
Σ
(( ((); X,, Ui) - -log(1 + Ke log log(2) - 77² VLs ((1)) ④ M
n
2qm ((WI)) XA, vi) 2q.
n² VVLL(W(0)) @ M
n1
CnLs(W(()) T/C
where the first inequality follows from the convexity of the cross-entropy loss with softmax, the second inequality follows from Lemma D.20 the third inequality follows because log(1 + x) S x. and the last inequality follows from Lemma D.19 for some constant C.
Lemma D.24 (Formal Restatement of Lemma 3.5 Under the same assumption as Theorem
WW"'" = Ti + Ō(Km² (1/())/))) Then for any time
D.I choose T2 = Ti +
2nc (0)
t during this stage, we have max, 7and 2 m//9 for all j [K], maxj.r. (15.).s((())) (15 (e 1 S
23, max) (11. < 282 and
W(T)) W
Ls
F
Ti
Cn(t Ti)
C
Proof. From Lemma
D.17 we have mar,? 2 1/4 and since (t) is an increasing sequence (8)
(T1)
over 1, we have max,? jinj
2 14 for all E [Ti, T2). We have
W - w 1 > Cnns(W(()) npc.
W
30

---

Under review as a conference paper at ICLR 2023
Taking telescopic sum from T1 to t yields
W W
n)((t -T))
L W (
F
On
T
Combining Lemma D.18
we have
w(T)) - w-|l ( O(n
Ls
Km' (1/c)/=))
(7)
Define V = m (1)) Gonge 5.rll and ((() = max; o [mmm 17 and B2 = ((up)). Now
we use induction to prove (t) < 23, and ((0) < 2,32. Suppose the result holds for time t S t'. Then
(Ensers)) E.) Saree 1|
(((1)) < (1(
max 3.r
1 ((0
100 'o'
(
+
Dink
(1e Ei) |
11 S
k=1
2
p'=1
0( OlViog doooononp)/pp + K Klog 1/0 //1 H1 Vlg d
(p())
q max prco
n
9-1
pl))pd) + v d)
vi(t)
((
(ohpd)
(O(v log doyon v pdd 0(((1))) 7-1 O(o)pdd)
(1))
where the second inequality follows by (000 S ( and applying the bounds from Lemma D.5.
and the last inequality follows by choosing log 1/9 Ō (aa) < ogon vpd. Unrolling the recursion by taking a sum from Ti to t' we have
Vi
((++1) (1)
(T))
Old" log d)
n
(0)
(T))
"
Oo 1
n
= (T) " 0 pd poly log d) Σ Lo (w())
(w6)
1 (Ti)
+ O 11 2 ed log d)
(iz)
1 81+ Ō(Km3)
333 23,,
where (i) follows from induction hypothesis (T()) < 23,, (ii) follows from the property of cross-
entropy loss with softmax 14',ll S 1.,.al 6, (iii) follows from Equation equation 7 (iv) follows from our choice of μ, n, K, and (v) follows because Ō(Km²) a-2 < O(Km"ooo 1.
Therefore, by induction (1) 2,3 holds for time 1 1' +
31

---

Under review as a conference paper at ICLR 2023
On the other hand, Φ (('++1)
Ily 1 (
(Ennes ses 122
(
max R,
( Hek )
Σ
Sinde
(1)
(t)
Sir.er
(emar 112
)
72
(16)
(1)) 0
17
max Jit
1
((oonv/ogd) + nO(onn v Vpd)
Jn Onlllogd.
9-1 112
K
oapd
(18)
1 ((T)) + 0
! 12
Σ
( (oloou//oge)) 8-1
B2 +=0mmm))3
(r)
M 2,32,
where (i) follows because Yi.n S 0, (ii) follows from Lemma D.7 and Lemma D.5
(1)
(iii) follows
because m 1 < max, (((0) S max; cl") S ~E e (iv) follows from Equation equation 7 9e.t and (v) follows because (mm²) ),8 < O(m)oaj) $ 1.
D.5 GENERALIZATION ANALYSIS
In this subsection, we show that pruning can purify the feature by reducing the variance of the noise by a factor of p when new sample is given.
Now the network has parameter
(1)
K
Pk O mi
Ej.ri
Ej Es.ril
3.r
112
Sjrrd
2
+
W
forst
Am
1=1
i=1
2
2
We have || 112 = OGoovpd + p- p-- log (T(*) + Koo poly log + nooon v pd
O (doo.
Lemma
D.25 (Formal
Restatement of Lemma 3.6
With probability at least 1
(2m) 4/u
2Kmexp
Ologotadi
max J.r
( E) S (2m) 2/9
Proof.
Since (W fi {) follows a Gaussian distribution with variance O(oooppd) have
(- (2m)-4/4
IP [ j.r. <) 2 (2m) (2m) 2/0
< exp
(~O(aoo)pd))
Applying a union bound over j [K], E [m] gives the result.
Theorem D.26 (Formal Restatement of Generalization Part of Theorem 3.1 Under the same as- sumptions as Theorem D.1 within Ö(Kn 100 - K K2m 4 2n le iterations, we can find W such that
Ls(WW) Sc
. LDD + exp(-n'
Proof. Let E be the event that Lemma D.25 holds. Then, we can divide Lp (W*) into two parts:
E[((F(W". x))] (EE))(((( x))] + E(I(E")((F (W" x))]
4
1
32

---

Under review as a conference paper at ICLR 2023
Since Ls(W) (W*) for each class j [K] there must exist training sample (x,, ys) S
with yi = J such that ( (W*, xx)) I Ke S by pigeonhole principle. This implies that En exp (x.) - (xx)) S 2K'. Conditioning on the event &, by Lemma D.25 we have
[P, F/WW', x:)1 S Σ Co( 6i)) + Σ (((W),r E))
- (2m) -1 (2
1
Thus, we have exp(Fy Ff(x)) & 2Ke = O(Ke). Next we bound the term Iz.
((F(W* x)) log
1+ Σ
exp((F Fi 12)(x))
j'
log
1 Σ exp(FF,(x)))
j'
log(1 1 + exp((F (x)))
J'
K
Fy(xx)
j't1
K
Σ (oWWW + o (((),,))))))
8'#y
< K Km(OOoom d -
- (m vdjy)
2K |
(8)
where the first inequality follows because (x) 2 0, the second and third inequalities fol- low from the property of log function, and the last inequality follows from our choice of I Õ(m 'n 1 on 1/22)). We further have
I2 S v VETT(E)ly Ele(F(W* x))
$ VP(E*)
4K² + E 21E//0 1 2
$ S expl-n22/1 (p))))/p)
2/90, on 2pp'p'' -Id + log(d))
where the first inequality follows from Cauchy-Schward inequality, the second inequality follows from Equation equation the third inequality follows from Lemma D.25] and the last inequality
follows because dp (m 1m on 1d11/)
E PROOF OF THEOREM 4.1
In this section, we show that there exists a relatively large pruning fraction (i.c., small p) such that while gradient descent still able to drive the training error toward zero, the learned model yields poor generalization. We first provide a formal restatement of Theorem 4.1
Theorem E.1 (Formal Restatement of Theorem H.Ip. Under Condition
2.2 choose initialization
variance do 0(m 4 "n pp- and learning rate v S ((1/2²). For > 0, if O (m log then with probability least 1 1/loog log(d), there exists T O nog- 2 o,, (pd) 9/2 +
n ''m"no,,"" (md)) (pd)-1) such that the following holds:
1. The training loss is below L.g T.s (W(T) S.
33

---

Under review as a conference paper at ICLR 2023
2. The model weight doesn't learn any of its corresponding signal all: (8) Pir.j for all
[K], r E [m].
3. The model weights is highly correlated with the noise: maxre|m] Gind 2 O(m (11)) if j.
Moreover, the testing loss is large:
LD ((T)) Aloo K)-
The proof of Theorem consists of the analysis of the over-pruning for three stages of gradient descent: initialization, feature growing phase, and converging phase, and the establishment of the generalization property. We present these analysis in detail in the following subsections.
E.1 INITIALIZATION
Lemma E.2. When = poly log d and p = O (mmloga) with probability 1 O(1 log d), for all
class E [K] we have |S signall O.
Proof. First, the probability that given class j receives signal is (1 (1-p)". We use the inequality that
1 t 2 exp (O(t)) At E (-1/4,1//4
Then the probability that |S signall
= 0, Vj E [K] is given by
(1 (1-p) Km
> exp { (-0 (pKmm) 2 - 0
log
E.2 FEATURE GROWING PHASE
Lemma E.3 (Formal Restatement of Lemma
4.3
Under the same assumption as Theorem E.1 n (pd) 9/22) and we have
there exists Ti < T such that Ti = O(1 n
max, Suira 2 m 1/4 for all i E [n]]
(t) j.r. = Ö(ova vdd).
maxjani
maxjank h S Ō(oo)).
Proof.
First of all, recall that from Definition C.1
we have for j f/i
(1)
[kk Eirrs
EiroP E Ejrm''
-(w(0)) ( 6.) +
(1)
Σ
(1)
(4)
(0) 5..
+
Tirck
112
Eami
kgj
Z'
2
Let
B = max vi
(1)
gintt + (w)
Jor S:)
-O(n log 1/9 T
log
O(noga v pd
log d pd
pd
Since max
(//0 E.) Dlovon /pd), we have
log pd
log d pd
( 2 0(0oonn V O(n log 1/0 1/9
O v pely
2 M(poo pd).
34

---

Under review as a conference paper at ICLR 2023
Let Ti be the last time that jr,,t
(t)
S
1/4, m-1/9 We can compute the growth of ((()
B(++1)
B O
()
[B(0)1--1
n2
2 B
+ O
|Bi 1B..00-2B130 B3!0)
n
1
non
o 2///2200/2 nag-2
B
n
Therefore, B,") will reach 2m 2mm11/9
1/9 within O111-no0 9-2 0 (pd) 4/2) iterations.
Inog
On the other hand, by Proposition D.10 we have |w S 5B+6Cnoy
logg d
O(1onn vpd log d).
E.3 CONVERGING PHASE
From the first stage we know that
(T))
(0)
Me mjj
(71)
Sjor
(Ti)
Bink
112
Sj
2
w jir
Eg.r:s
St.r,
Now we define W as follows:
Exrri
w Wir + @(mlog(1//))
Σ I(j v1)
S
W(T)- W- s
Lemma E.4. Based on the result from feature growing phase,
O(m2n log(1 (1/e),, (pd) 1/23.
Proof. We derive the following bound:
w(n) W
W(Th)
(())
W (0)
W.
Σ
(e) pk
(Ti)
Exara
Σ
(T))
Eimn
Omm² 2n2 1/2 log(1/e)o 2/2))
J.r.h 112
j.r.
3.r
E Eg.r
i=1
Earr
22
Kmm00m0/KKoaa Koo) + 0 (pd)
-1 11/2 log 1/9"))) - Ö(m² 2n2
1/2
( (pd)
Omm2n' 1/2 log( (gg_)))=""(dd))>
where the first inequality follows from triangle inequality, the second inequality follows from the expression of ((T)), W and the third inequality follows from Lemma D.5 0 if and only if j yi-
and and the fact that Gjrr, >
(t)
Lemma E.S. For Ti < ST we have
2qK y x;). W U. (W,, W;) 2 glo
c
Lemma E.6. For Ti <t<T T and j = Yt. we have
x.). w;) > O(m 1/2 log(1/e)).
35

---

Under review as a conference paper at ICLR 2023
Proof. By Lemma D.5 we have (Er.rd Wz.r) = e (mlog(1/e)) and by Lemma E.3 for j = yis max, (1) (W E, max, Sprrt max, (w)rr E.) Onl/
log
1/9). d a) 2 O(m 1/9). Then have
m
VF x.), W;)
Σ o' ( (:)) (Eimas r=1
0m // log(1 log(1/)))
Lemma E.7. For Ti SIST T and j + yi, we have
VF, ,1), Wj) w)),:(s00 50().
Proof. We first compute (wj... E.) = ( (w/00 E:) 1mm Ei=1 Iíj = y1)
(E
|E
O lod d). Further,
(0(0 jir: E:)
(ek: Esrss)
Exr,s E
E Es Ej.r.
= (w jrr E:
(1) Vorkk K
(t) Sjmn
122
Sj.r,
==1
s O(ogon log d),
where the inequality follows from Lemma D.5 and Lemma D.15 Thus, have
m
VF x.), W;)
Σ o (1 (Eimis
m0
(aoσn v pd
log d
0(),
where the last inequality follows from choice of op 0mm-1/9 1).
Lemma E.8. Under the same assumption as Theorem E.1
we have
W w.
w(++))
w
2 2 Cnns(W(()) TJC.
F
36

---

Under review as a conference paper at ICLR 2023
Proof. To simplify our notation, we define
F(1) (x,) = (VE, ,x)),
x.). W3).
The proof is exactly
the same as the proof of Lemma D.23
W w 2
W (1)
W W n/² VL. (W(() ④ M ?
20/ VLs
M,
2n
n
(W)
91) (W xx), w;)l - 7 VLs(((()) M
n
k
K
2q17
Σ
log(1 1 +
Σ 3=1
e v - -log(1 1 + Σ
(f Pu)l)
n7² VLL (()) @M
2q
((W(()) X,, (i) -log(1 Ke loo(2 -1² AL (W()) Ml
n
20
c (WW() X xx,, Ui)
-n² VLs(W(1) ( M| 2q.
n
2 CnLL( v
where the first inequality follows from the convexity of the cross-entropy loss with softmax, the second inequality follows from Lemma D.20 the third inequality follows because log(1 + 2) x. and the last inequality follows from Lemma D.19 for some constant C' > 0.
Lemma E.9 (Formal Restatement of Lemma
Under the same assumption as Theorem E.
W W
choose T2 Ti +
Ti + Ö(n 'e ee' mmn Then for any time t
2n
during this stage we have maxj,r W.// O(000 and
W(T)) W
Ls (s()))))
Ti
Cn(t- Ti) C
Proof. We have
W
w - 2 CnLs(W(()) me.
w-|
Taking a telescopic sum from Ti yields
W(T) - W 2
ne(t -Ti)
Ls W()))
On
Combining Lemma E.4 we have
w [] = Ö(1 'mm "m'no, ? -1) )
Ls S0
WTT) W
E.4 GENERALIZATION ANALYSIS
Theorem E.10 (Formal Restatement of the Generalization Part of Theorem 4. Under the same as-
sumption as Theorem E.1 within O(1) -nn o, (pd) -g/2 + -1 m no, 2 (pd)-1) iterations, can find WT) such that L.g( (T)) & e, and T W(9) n(log K).
37

---

Under review as a conference paper at ICLR 2023
Proof. First of all, from Lemma E.9 Then, we can bound
we know there exists t E [Ti] such that Ls! (W(T) 1
(0)
(0)
(1)
Syra
Errr
Jir
5.r
112
j.
kデj
i=1
w
(0) Jir
10)
1
(1)
(w
2
14
Esnss
O(ooVd) + Ono (pd) 1/2).
Consider new example (x, v). Taking a union bound over v, with probability at least 1 -d1, we have
(w() (w()..))
Ö(ovo, vd n((pd) 1/2).
for r [m]] Then,
m
(x) Σ
(1) Wirt My )) + ((
(w(()) 3. 1
maxx
mo(o + +n (pd)
where the last inequality follows because do S 0(m-1/0p and d 2 A(m2lan)). Thus, with probability at least 1 - 1/d,
((F(W(() 2 log(1 + (K - 1)e-
38


Reviews:
[{"review_id": "dHfA6j1wb7T", "reviewer": "Reviewer_oTTX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": " This paper studies the key problem in deep learning: why pruning can help generalization. They consider a one-layer (I will explain why I call it one layer) neural network with ReLU activation, and assume certain structure of input data and labels. They model the pruning operator as the element wised multiplication between weight matrices and masking matrices. They show that, when pruning ratio is lower than some threshold, it helps generalization; while if the ratio is higher than some threshold, it will hurt generalization. Their proof technique is to study the correlations between model weights and input data noise. If the pruning ratio is lower than some threshold, the pruning will reduce the variance of the noise and hence improve the generalization. When the ratio is higher than some threshold, it will constrain the model capacity such that the prediction will be bounded (less than 1), and hence the generalization is lower bounded by a constant as well.\n", "summary_of_the_review": "In general, this is an interesting paper towards understanding how GD+pruning helps generalization, and it could inspire a line of follow-up works. However, as I mentioned in weakness part, the setup is way toy, even among the theory papers. \n", "strength_and_weaknesses": "This is the first work towards understanding the generalization of pruned neural networks trained by gradient descent. Their results are interesting: there is a phase transition of pruning ratio. When pruning ratio is lower than some threshold, it helps generalization; while if the ratio is higher than some threshold, it will hurt generalization, which matches our intuition. Their proof is based on assuming sparse data with Gaussian noise, and controlling the correlations between Gaussian random initialized weights and noise. A small pruning ratio provides some regularization-like benefits by reducing the variance of the noise, while the more aggressive pruning will limit the prediction of the network below 1, i.e., $F(\\tilde{\\mathbf{W}},\\mathbf{x}) < 1$, so the generalization will never be smaller than a threshold. The proof idea is interesting to me, and the results are also novel. \n\nSome issues:\n\n1. The assumption on input data is way strong: the authors assume the input data is composed by basis vector concatenated with Gaussian noise, i.e., $\\mathbf{x} = [\\mathbf{e}_i, \\boldsymbol{\\xi}]$. I guess this data assumption follows recent work:\n\\emph{ Cao, Yuan, et al. \"Benign Overfitting in Two-layer Convolutional Neural Networks.\" arXiv preprint arXiv:2202.06526 (2022).} However, Cao et al do not assume the deterministic part of the data is basis vector. \n\n2. The neural network structure is bit toy. Usually, for two layer ReLU network, we assume $f(\\mathbf{x}) = \\mathbf{a}^T \\sigma (\\mathbf{W}\\mathbf{x})$, while in this paper's setting, the top layer is removed. Hence I cannot even call this model a ``two layer neural network''. Perhaps linear model with rectified output is more accurate. It is also surprising that here we only achieve $O(1/\\epsilon)$ convergence of training loss, while it is well-known that even for deep neural network, the convergence rate is $O(\\log (1/\\epsilon))$ in overparameterized setting, or even under only mild overparameterization regime:\n\n\\emph{ Nguyen, Quynh. \"On the proof of global convergence of gradient descent for deep relu networks with linear widths.\" International Conference on Machine Learning. PMLR, 2021.}\n\n\n3. Technical question: in Lemma D.25, the key Lemma to prove generalization, the authors said that the correlation between output model and Gaussian noise: $\\langle \\tilde{\\mathbf{w}}^*, \\boldsymbol{\\xi} \\rangle$ satisfy Gaussian distribution. If $\\tilde{\\mathbf{w}}^*$ is a constant, it definitely holds. However, if my understanding is correct, output weight $\\tilde{\\mathbf{w}}^*$ is also a random variable, and the product of two Gaussian RVs is not necessarily Gaussian. So I am curious how the authors eliminate the randomness of $\\tilde{\\mathbf{w}}^*$? Or do we need to take expectation over $\\tilde{\\mathbf{w}}^*$ to make it constant?\n \n\n4. Perhaps not extremely relevant but I think the following paper about Dropout should be cited:\nArora, Raman, et al. \"Dropout: Explicit forms and capacity control.\" International Conference on Machine Learning. PMLR, 2021.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9FObGkbHYY-", "reviewer": "Reviewer_qT6W", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the effect of random pruning at initialization on the generalization of a neural network. The author theoretically shows that pruning of some two-layer convolutional neural networks under small initialization could improve their generalization if the probability of dropping a neural is mildly large, and could deteriorate the generalization if it is too large.", "summary_of_the_review": "Strength: well-written, results are interesting and new;\nWeakness: Restrictive assumptions without justification on their practical relevance.", "strength_and_weaknesses": "Strength: The paper is mostly clear and the results are novel. The analysis of the convergence and generalization of training a pruned-at-initialization network is interesting and new. The analysis studies the neural network training under the so-called \"active regime\", which is more practically relevant.\n\nWeakness: I think the theoretical results in the paper are great but I have some concerns about the way this paper is presenting it:\n\nThe assumption on the data distribution and the network structure is fairly restrictive. This paper studies the two-layer convolutional network but requires the size of the convolutional kernel to be exactly half of the input dimension and so is the stride so that the convolution layer outputs a 2d binary vector, and the two binary outputs can be viewed as the binary predictions of a linear classifier on the first half and the second of the data vector. Then the data distribution is carefully designed so that each data vector has either the first half as pure signal and the second half as noise or the other way around. Lastly, the weight for the output layer is sparse, binary, and fixed during training. \n\nI understand many of these assumptions are useful for the analysis (and I really think they are cleverly made) but most of them are impractical, making the theoretical results less relevant in interpreting the performance of a practical neural network trained under a real dataset, and this is shown in the numerical section that experiments on the real dataset cannot be well explained by the theorems in this paper.\n\nTherefore, I think a more detailed explanation of why some assumptions are made about the data and network, together with remarks on how the theoretical results can be (or can be made in future work) relevant to practice is necessary for this paper, otherwise, the theoretical results can be misleading.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "4LrXqOWy9m", "reviewer": "Reviewer_Rwrk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper analyzes pruning for overparameterized two-layer neural networks. The setting is \"pruning the second last layer\" of a deep neural network, so they assume the input has the form of (x1, x2) \\in R^{2d}, where x1 and x2 are either ue_i, or a random vector. In other words, the input has a specical form of \"half one-hot, half random noise\" form. Moreover, they assume the network structure has the form sigma(<w, x1>)+sigma(<w, x2>), which means the weight w is applied to both x1 and x2 simultaneously. There are a bunch of other assumptions described in condition 2.2, including number of classes, training samples, etc. \n\nUnder these assumptions, the authors were able to prove interesting results on pruning the network. Specifically, they show that, after mild pruning, the generalization performance is increasing; after over pruning, the generalization performance is not better than random guess, but the training loss goes to 0. The nice thing about their analysis is, it is based on feature learning, instead of NTK analysis. In other words, they show the network learns the feature vector after mild pruning, and the network fails to learn the feature vector after over pruning. \n", "summary_of_the_review": "This is an interesting theory paper of pruning for overparameterized two layer networks, with special assumptions on the input and network structure. The analysis is based on feature learning, which says with mild pruning, the network will still learn the feature signal but the noise signal will be reduced; with over pruning, the network is essentially learning the noise. ", "strength_and_weaknesses": "Strength: \nThis is a well organized and well written paper. I did not have enough time to read all the details in the appendix, but I did go through the theorem statement in the main paper, which looks reasonable to me. \nPruning is pretty effective empirically, but as the authors mentioned in Section 3.2, if one only applies the \"NTK analysis\", it seems that pruning will only hurt. The nice thing about this paper is it uses the new technique called feature learning, and based on this technique, they can indeed show the effectiveness of pruning. \nEmpirically, feature learning is a much more realistic setting, so I think such analysis is interesting, and can be seen as a nice theoretical support for pruning methods. \n\nWeakness:\nThe weakness of this paper, as well as many neural network theory papers, is the strong assumptions on the model. The assumptions on the input data and for the network structure look especially strange to me. However, given this is the first analysis for pruning, I guess that might be OK. It can be the first starting point for analyzing pruning methods. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2uSRV1-MNq", "reviewer": "Reviewer_bjfM", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considered a classification task for overparameterized two-layer neural networks, where the network is randomly pruned according to different rates at the initialization and studied how different pruning fractions affect the model’s gradient descent dynamics and generalization. \n", "summary_of_the_review": "The paper theoretically showed that there exists a threshold on the pruning fraction such that pruning helps the neural network’s generalization and also there exists a relatively large pruning fraction such that the learned model yields poor generalization. Even though these results sound interesting it is not clear how their experimental results support such a theory. ", "strength_and_weaknesses": "Strength: \nThe paper considered a classification task for overparameterized two-layer neural networks, where the network is randomly pruned according to different rates at the initialization. In this specific scenario, they theoretically prove that there exists a threshold on the pruning fraction such that pruning helps the neural network’s generalization. the generalization bound gets better as the pruning fraction gets larger.  Also for the overpruning there exists a relatively large pruning fraction such that the learned model yields poor generalization\n\n\nWeakness:\n1- Even though the theoretical result of the paper sounds interesting, they considered a very specific scenario and it is not clear this can be generalized to more complex models with different weight distributions.  \n\n2-The experimental results are very limited and they do not fully support the theoretical results. It is not clear how the results in figure 2 mapped to the bound proposed in theory. The paper should show the simulation results vs the theoretical result to make it more clear.\n\n\n3- Also the experimental result of the real dataset is not clear. How come the accuracy in y axis is 100%? They only show as the pruning ratio increases the accuracy drops. How do these figures show the claims and arguments made by theory?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject