Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Sparse Neural Networks
Authors: Shuai Zhang
Meng Wang
Sijia Liu
Pin-Yu Chen
Jinjun Xiong
Venue: NeurIPS 2021 Poster (2021)
Keywords: Sparse Neural Network
Network Pruning
Optimization
Theoretical Analysis
Generalization Guarantee
Sample Complexity Analysis
Lottery Ticket Hypothesis

Abstract: The lottery ticket hypothesis (LTH) states that learning on a properly pruned network (the winning ticket) has improved test accuracy over the original unpruned network. Although LTH has been justified empirically in a broad range of deep neural network (DNN) involved applications like computer vision and natural language processing, the theoretical validation of the improved generalization of a winning ticket remains elusive. To the best of our knowledge, our work, for the first time, characterizes the performance of training a pruned neural network by analyzing the geometric structure of the objective function and the sample complexity to achieve zero generalization error. We show that the convex region near a desirable model with guaranteed generalization enlarges as the neural network model is pruned, indicating the structural importance of a winning ticket. Moreover, as the algorithm for training a pruned neural network is specified as an (accelerated) stochastic gradient descent algorithm, we theoretically show that the number of samples required for achieving zero generalization error is proportional to the number of the non-pruned weights in the hidden layer. With a fixed number of samples, training a pruned neural network enjoys a faster convergence rate to the desired model than training the original unpruned one, providing a formal justification of the improved generalization of the winning ticket. Our theoretical results are acquired from learning a pruned neural network of one hidden layer, while experimental results are further provided to justify the implications in pruning multi-layer neural networks.

Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Pruned Neural Networks
Shuai Zhang
Meng Wang Rensselaer Polytechnic Institute Troy, NY, USA 12180 wangm7 .eduu edu
Rensselaer Polytechnic Institute Troy, NY. USA 12180
changs21@rpi .dd
Sijia Liu
Pin- Yin-Yu Chen
Michigan State University East Lansing, MI, USA 48824
IBM Research
Yorktown Heights, NY, USA 10562
MIT-IBM Watson AI Lab, IBM Research liusi fesijji5o ji5mmsu. edu
Pin-Yu Chwn@hen@nee bm com
Jinjun Xiong
University at Buffalo Buffalo NY, USA 14260 jinjun@buffalo. edu
Abstract
The lottery ticket hypothesis (LTH) 20 states that learning on properly pruned network (the winning tickef) improves test accuracy over the original unpruned net- work. Although LTH has been justified empirically network (DNN) involved applications like computer vision and natural language processing, the theoretical validation the improved generalization of a winning ticket remains clusive. To the best of our knowledge, characterizes the performance of training a pruned neural network by analyzing the geometric structure of the objective function and the sample complexity achieve zero generalization error. We show that the convex region near a desirable model with guaranteed generalization enlarges the neural network model is pruned, indicating the structural importance of a winning ticket. Moreover, when the algorithm for training pruned neural network is specified an (accelerated) stochastic gradient descent algorithm, we theoretically show that the number of samples required for achieving zero generalization error proportional the number of the non-pruned weights in the hidden layer. With a fixed number of samples, training pruned neural network enjoys faster convergence rate the desired model than training the original unpruned one, providing formal justifica- tion of the improved generalization of the winning ticket. Our theoretical results are acquired from learning a pruned neural network of one hidden layer, while experimental results are further provided to justify the implications in pruning multi-layer neural networks.
broad range of deep neural
work, for the first time,
Introduction
Neural network pruning can reduce the computational cost of model training and inference signif-
icantly and potentially lessen the chance of overfitting [33 26 15 25
58
41.. The recent
Lottery Ticket Hypothesis (LTH) (00] claims that a randomly initialized dense neural network al-
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

ways contains a so-called "winning ticket," which is a sub-network bundled with the corresponding initialization, such that when trained in isolation, this winning ticket can achieve at least the same testing accuracy as that of the original network by running at most the same amount of training time. This so-called "improved generalization of winning tickets" is verified empirically in [20]. LTTH has attracted a significant amount of recent research interests 45 70 39)
Despite the empirical success
the theoretical justification of winning tickets remains clusive except for a few recent provides the first theoretical evidence that within randomly initialized neural network, there exists good sub-network that can achieve the same test performance as the original network. Meanwhile, recent work 42 trains neural network by adding the & regularization term to obtain relatively sparse neural network, which has a better performance numerically.
[9 63 11.
works. 39
However, the theoretical foundation of network pruning is limited. The existing theoretical works usually focus on finding a sub-network that achieves a tolerable loss in either expressive power or training accuracy, compared with the original dense network 71 61 45 3
35
S
59
To the
best of our knowledge, there exists no theoretical support for the improved generalization achieved by winning tickets, i.e., pruned networks with faster convergence and better test accuracy.
Contributions:
This paper provides the first systematic analysis of learning pruned neural networks with a finite number of training samples in the oracle-leamerr setup, where the training data are generated by a unknown neural network, the oracle, and another network, the learner, trained on the dataset. Our analytical results also provide a justification of the LTH from the perspective of the sample complexity. In particular, we provide the first theoretical justification of the improved generalization of winning tickets. Specific contributions include:
1. Pruned neural network learning via accelerated gradient descent (AGD): We propose an AGD algorithm with tensor initialization to learn the pruned model from training samples. Our algorithm converges to the oracle model linearly, which has guaranteed generalization.
2. First sample complexity analysis for pruned networks: We characterize the required number of samples for successful convergence, termed as the sample complexity. Our sample complexity bound depends lincarly on the number of the non- non-pruned weights and is a significant reduction from directly applying conventional complexity bounds in
669 66 67].
Characterization the benign optimization landscape of pruned networks: We show analyt- ically that the empirical risk function has an enlarged convex region for a pruned network, justifying the importance of a good sub-network (i.e., the winning ticket).
4. Characterization of the improved generalization of winning tickets: We show that gradient- descent methods converge faster to the oracle model when the neural network is properly pruned, or equivalently, learning on pruned network returns a model closer to the oracle model with the same number of iterations, indicating the improved generalization of winning tickets.
Notations. Vectors are bold lowercase, matrices and tensors are bold uppercase. Scalars are in normal font, and sets are in calligraphy and blackboard bold font. I denote the identity matrix. N and R. denote the sets of nature number and real number, respectively. ||=|| denotes the forn of a r and| | Z so denote the spectral norm, Frobenius norm and the maximum value of matrix Z. respectively. [2] stands for the set of 21, .... 2} for any number Z E N. In addition, [r)
vector z, and || Z 2| || |Z|r=
M(g(r)) ) if < C g (or f C g ) for some constant C >>> O when r is large enough. f(r) = O(g(r) if both ((r) = ((((r)) and f(r) Kgg(r) holds,
(g((r) ( or f(r)
where c g ʃ < C. g for some constant 0 e C when is large enough.
1.1 Related Work
Network pruning. Network pruning methods seek compressed model while maintaining the expressive power. Numerical experiments have shown that over 90% of the parameters can be pruned without significant performance loss [1O]. Examples of pruning methods include irregular weight
pruning (25, structured weight pruning [57] neuron-based pruning 28 and projecting the weights
to low-rank subspace [13].
Winning tickets. 20 employs an Iterative Magnitude Pruning (IMP) algorithm to obtain the proper sub-network and initialization. IMP and its variations 22 46 succeed in deeper networks like Residual Networks (Resnet)-50 and Bidirectional Encoder Representations from Transformers [21 shows that IMP succeeds in finding the "winning ticket" if the ticket is
(BERT) network
[T].

---

stable to stochastic gradient descent noise. In parallel, [3) shows numerically that the "winning ticket" initialization does not improve over random initialization once the correct sub-networks are found, suggesting that the benefit of "winning ticket" mainly comes from the sub-network structures. 18 analyzes the sample complexity of IMP from the perspective of recovering sparse vector in a linear model rather than learning neural networks.
Feature sparsity. High-dimensional data often contains redundant features, and only a subset of the features is used in training 6 27
60 688. Conventional approaches like wrapper and filter methods score the importance of each feature in a certain way and select the ones with highest scores [24]. Optimization- -aadd methods add variants of the tu norm as a regularization to promote feature sparsity [68]. Different from network pruning where the feature dimension still remains high during training, the feature dimension is significantly reduced in training when promoting feature sparsity.
Over-paramettrized model. When the number of weights in neural network is much larger than the number of training samples, the landscape of the objective function of the learning problem has no spurious local minima, and first-order algorithms converge to one of the global optima 37 44 64 50 9 49 38). However, the global optima is not guaranteed to generalize well on testing data 64
Generalization analyses. The existing generalization analyses mostly fall within three categories. One line of research employs the Mean Field approach to model the training process by a differential equation assuming infinite network width and infinitesimal training step size [12 40 56]. Another approach is the neural tangent kernel (NTK) 3D,, which requires strong and probably unpractical over-pan wver-parameterivation such that the nonlinear neural network model behaves as its linearization The third line of works follow the pracle-learner setup, where the data are generated by an unknown oracle model, and the learning objective is to estimate the oracle model, which has a generalization guarantee on testing data. However, the objective function has intractably many spurious local minima even for one-hidden-layer neural networks [48] 47 64).
around the initialization [1 17 72
Assuming an infinite number of training samples, 8 16 52) develop learning methods estimate the oracle model. [23] 69 66 67] extend to the practical case of a finite number of samples and characterize the sample complexity for recovering the oracle model. Because the analysis complexity explodes when the number of hidden layers increases, all the analytical results about estimating the oracle model are limited to one- me-hidden-layer neural networks, and the input distribution often assumed to be the standard Gaussian distribution.
2 Problem Formulation
In an oracle-leamer model, given any input x E Rd the corresponding output y is generated by a pruned one- me-hidden-layer neural network, called oracle. as shown in Figure | The oracle network is equipped with neurons where the j-th neuron is connected to any arbitrary rj (rj S d) input features. Let W = [wi.... : w E RdxK denotes all the weights (pruned ones are represented by zero). The number of non-zero entries in wn is at most rj. The oracle network is not unique because permuting neurons together with the corresponding weights does not change the output. Therefore, the output label y obtained by the oracle network satisfies |
Σ
T o(w" x) + g<; W W
(1)
K
where & is arbitrary unknown additive noise bounded by some constant [6 o is the rectified linear unit (ReLU) activation function with d(z) = max(z, 0). and P E {0, 11_K xK is any permutation matrix. M is mask matrix for the oracle network, such that Mj, equals to 1 if the weight w5,, is not pruned, and 0 otherwise. Then, M is indicator matrix for the non-zero entries of W with M W W* where @ is entry-wise multiplication.
{I,,, Vn W generated by the oracle, we train on learner network equipped with the same number of neurons in the oracle network. However, the j-th neuron in the learner network is connected to ry input features rather than rÿ. Let Tmin Tmax and Tave denote the minimum, maximum, and average value of {ry)/=,, respectively. Let M denote the
Based on N pairs of training samples D =
It is extendable to binary classification, and the output is generated by Prob(yn 1|xx) g( W*).
3

---

Ene-hidden-layer
Pruned Neural Network
W
Noise
X
(xx
y
Imput
Output
Hidden layer with
Figure I: Illustration of the model
mask matrix with respect the learner network, and wj is the j-th column of W. The empirical risk function is defined as
fo(W) 2N
d(w x.,) yn))
K
When the mask M is given, the learning objective is to estimate proper weight matrix W for the learner network from the training samples 'D via solving
nRRW (D(
s.t. MOW= = W.
(3)
M is called an accurate mask if the support of M covers the support of permutation of M', i.c., there exists a permutation matrix P such that (M' P) @ M M When M is accurate, and E 0, there exists a permutation matrix P such that W is global optimizer to (3). Hence, W can be estimated by solving 3 one can learn the oracle network accurately, which has guaranteed generalization performance on the testing data.
We assume w,, is independent and identically distributed from the standard Gaussian distribution (O,, Idxa). The Gaussian assumption is motivated by the data whitening [34] and batch normaliza- tion techniques (29] that are commonly used in practice improve learning performance. Moreover, training mee-hidden-layer neural network with multiple neurons has intractable many fake minima 47 without any input distribution assumption. In addition, the theoretical results in Section 3 assume an accurate mask, and inaccurate mask is evaluated empirically in Section 4
The questions that this paper addresses include: 1. what algorithm to solve (3) 2. what is the sample complexity for the accurate estimate of the weights in the oracle network? 3. what is the impact of the network pruning the difficulty of the learning problem and the performance of the learned model?
3 Algorithm and Theoretical Results
Section 3.1 studies the geometric structure (3), and the main results are in Section 3.2 briefly introduces the proof sketch and technical novelty, and the limitations are in Section 3.4
Section 3.3
3.1 Local Geometric Structure
Theorem characterizes the local convexity of fo in (3) It has two important implications.
1. Strietly locally convex near ground truth: fo is strictly convex near W* P for some permutation matrix P. and the radius of the convex ball is negatively correlated with VF, where 7 is in the order of Fave- Thus, the convex ball enlarges as any ry decreases.
2. Importance of the winning ticket architecture: directly, training on a properly pruned sub-network has larger local convex region near W P. which may lead to easier estimation of W P. To some extent, this result can be viewed theoretical validation of the importance of the winning architecture (a good sub-network) 20] Formally, have
Compared with training on the dense network

---

Theorem (Local Convexity). Assume the mask M of the learner network is accurate. Suppose constants Eo. E E (0, 1) and the number of samples satisfies
= -=
(4)
for some large constant q > O, where
&jxx)) + ra)t))
7=
(5)
8K*
5g is 1 if the indices of non-pruned weights in the j-th and k-th neurons overlap and 0 otherwise. Then, there exists permutation matrix P such that for any W that satisfies
Pl = -((A)) and M O W W.
(6)
its Hessian of fT. with probability at least
K q Fmiia, is bounded as:
1 Eu
1 I v fo (W) 0
θ
K2
K
Remark 1.1 (Parameter 7): Clearly F is monotonically increasing function of any from (
Moreover, one can check that 8 Tave S < Tave. Hence, F is in the order of Tave-
Remark 1.2 (Local landscape): Theorem 1 shows that with enough samples as shown in ( in local region of W P as shown in (6) all the eigenvalues of the Hessian matrix of the empirical risk
function are lower and upper bounded by two positive constants. This property is useful in designing
efficient algorithms to recover W* P. as shown in Section 3.2
Remark 1.3 (Size of the convex region): When the number of samples N is fixed and changes, E1 can be O /F/N) while 4 is still met. Eo in ( can be arbitrarily close to but smaller than 1 El so that the Hessian matrix still positive definite. Then from (6. the radius of the convex ball is ((1) - O /F/N,, indicating an enlarged region when decreases. The enlarged convex region serves as an important component in proving the faster convergence rate, summarized in Theorem Besides this, as Figure I shown in [20]. the authors claim that the learning is stable the linear interpolation of the learned models with SGD noises still remain similar in performance, which is summarized as the concept "linearly connected region." Intuitively, we conjecture that the winning ticket shows a better performance in the stability analysis because it has larger convex region. In the other words, a larger convex region indicates that the learning is more likely to be stable in the linearly connected region.
3.2 Convergence Analysis with Accelerated Gradient Descent
We propose to solve the non-convex problem 3 via the accelerated gradient descent (AGD) algorithm, summarized in Algorithm [ Compared with the vanilla gradient descent (GD) algorithm, AGD has additional momentum term, denoted by ((W(1) W(+))), in each iteration. AGD enjoys faster convergence rate than vanilla GD in solving optimization problems, including learning neural networks (65). Vanilla GD can be viewed special case of AGD by letting 0. The initial point
(o) can obtained through tensor method, and the details are provided in Appendix B
Algorithm 1 Accelerated Gradient Descent (AGD) Algorithm
1: Input: training data D {I )n))) } gradient step size n, momentum parameter B, and an initialization ( by the tensor initialization method;
2: Partition DD into T = log (1/E) disjoint subsets, denoted as (Dr)T=i:
3: for t-= 2,
do
(((11) (1) 17 M Vín (W(") 3(W10 w((-1))
4:
5: end for
6: Return: (T)
The theoretical analyses of our algorithm are summarized in Theorem (convergence) and Lemma] T (Initialization). The significance of these results can be interpreted from the following aspects.
5

---

1. Linear convergence to the oracle model: Theorem 2 implies that if initialized in the local convex region, the iterates generated by AGD converge linearly to W P for some P when noiseless. When there is noise, they converge to point (('), The distance between W and W P is proportional to the noise level and scales in terms of O( /F[N). Moreover, when is fixed, the convergence rate of AGD is @ ((v )T Recall that Algorithm for the vanilla GD algorithm here is O ((FF/K) K") by setting 3 by Theorem 2 indicating slower convergence than AGD. Lemma shows the tensor initialization method indeed returns an initial point in the convex region.
| reduces to the vanilla GD by setting / 0. The rate
2. Sample complexity for accurate estimation: We show that the required number of samples for successful estimation of the oracle model is @ q log(1/s)) for some large constant and estimation accuracy E. Our sample complexity is much less than the conventional bound of (dd g log()/s)) for one-hidden-lat characterization of learning a pruned network from the perspective of sample complexity.
networks [69] 66 67]. This is the first theoretical
3. Improved generalization of winning tickets: We prove that with a fixed number of training samples, training on a properly pruned sub-network converges faster to W P than training on the original dense network. Our theoretical analysis justifies that training on the winning ticket can meet or exceed the same test accuracy within the same number of iterations. To the best of our knowledge, our result here provides the first theoretical justification for this intriguing empirical finding of "improved generalization of winning tickets" by (20].
Theorem (Convergence). Assume the mask M of the learner network is accurate. Suppose ( satisfies (6) and the number of samples satisfies K ( q log(1/=))
N S2
(8)
for some Eo E 10,1/2). Let n K/14 in Algorithm 1. Then, the iterates (W())
]t=1 returned by
Algorithm I converges linearly to W* up to the noise level with probability at least 1 K2T Time
[w - W F (v(3) W (0) - W PI F + (E
log
-16,,
(9)
N
and [[ (T) - W W*Pl S: 0
Ty
log 9
[4).
(10)
N
for a fixed permutation matrix P. where v(3) is the rate of convergence that depends on B with v(3*)= = 1-66 @ (LE0) for some non-zero 3r and v00 =1- (
Lemma 1 (Initialization). Assume the noise Igl S | and the number of samples N = 2(Er2K"T rmr log 4) for Ep > O and large constant 9. the tensor initialization method outputs
w()) such that 66 holds, i... || W == O [ookk) with probability at least 1- q Tmmax
Remark 2.1 (Faster convergence on pruned network): With a fixed number of samples, when F decreases, Eo can increase as ((VF) while ( still met. Then v(0) o @(vF/K) K) and v(8*)
O ((Vr/K). Therefore, when decreases, both the stochastic and accelerated gradient descent converge faster. Note that as long as (0)) is initialized in the local convex region, not necessarily by the tensor method, Theorem 2 guarantees the accurate recovery. [66 67
analyze AGD on
convolutional neural networks, while this paper focuses on network pruning.
Remark 2.2 (Sample complexity of initialization): From Lemma the required number of samples for a proper initialization is 0(==" 333 max log q). Because Tmax < Krae and 7 = M(rave), this number is no greater than the sample complexity in (8). Thus, provided that (8) is met, Algorithm I can estimate the oracle network model accurately.
Remark 2.3 (Inaccurate mask): The above analyses are based on the assumption that the mask of the learner network is accurate. In practice, a mask can be obtained by an iterative pruning method such as (20 or a she-shot pruning method such as [55]. In Appendix [E] we prove that the magnitude pruning method can obtain an accurate mask with enough training samples. Moreover, empirical experiments in Section 4.2 and and
suggest that even the mask is not accurate, the three properties (linear convergence, sample complexity with respect to the network size, and improved generalization of winning tickets) can still hold. Therefore, our theoretical results provide some insight into the empirical success of network pruning.

---

3.3 The Sketch of Proofs and Technical Novelty
Our proof outline is inspired by 669 on fully connected neural networks, however, major technical changes are made in this paper to generalize the analysis to an arbitrarily pruned network. To characterize the local convex region of fo (Theorem 1), the idea is to bound the Hessian matrix of the population risk function, which is the expectation of the empirical risk function, locally and then characterize the distance between the empirical and population risk functions through the concentration bounds. Then, the convergence of AGD (Theorem 2) is established based on the desired local curvature, which in turn determines the sample complexity. Finally, to initialize in the local convex region (Lemma 1), we construct tensors that contain the weights information and apply decomposition method to estimate the weights.
Our technical novelties are as follows. First, direct application of the results in 669 leads to a sample complexity bound that is linear in the feature dimension d. We develop new techniques to tighten the sample complexity bound to be linear in F, which can be significantly smaller than d for a sufficiently pruned network. Specifically,, we develop new concentration bounds (Lemmas 4 and 5 in Appendix) to bound the distance between the population and empirical risk functions rather than using the bound in [69]. Second, instead of restricting the acitivation to be smooth for convergence analysis, we study the case of ReLU function which is non-smooth. Third, new tensors are constructed for pruned networks (see (2T)-(23) in Appendix) in computing the initialization, and our new concentration bounds are employed to reduce the required number of samples for proper initialization. Last, Algorithm I employs AGD and proved to converge faster than the GD) algorithm in [69]
3.4 Limitations
Like most theoretical works based on the oracle-learner setup, limitations of this work include (1) one hidden layer only; and (2) the input follows the Gaussian distribution. Extension to multi-layer might be possible if the following technical challenges are addressed. First, when characterizing the local convex region, one needs to show that the Hessian matrix is positive definite. In multi-layer networks, the Hessian matrix is more complicated to compute. Second, new concentration bounds need be developed because the input feature distributions the second and third layers depend on the weights in previous layers. Third, the initialization approach needs to be revised. The team also investigating the other input distributions such as Gaussian mixture models.
4 Numerical Experiments
The theoretical results first verified on synthetic data, and we then analyze the pruning perfor- mance on both synthetic and real datasets. In Section 4.1, Algorithm
[ is implemented with minor
modification, such that, the initial point is randomly selected as ( W'
|//l/ W 'Il < X for
some À >> 0 to reduce the computation. Algorithm terminates Algorithmm/ermmnnates when W ( ||/ (" is smaller than 10 or reaching 10000 iterations. In Sections 4.2 and 4.3 the Gradient Signal Preser- vation (GraSP) algorithm (55) and IMP algorithm [10] 20 are implemented prune the neural networks. As many works like [T] 10 20] have already verified the faster convergence and better generalization accuracy of the winning tickets empirically, we only include the results of some representative experiments, such as training MNIST and CIFAR-10 on Lenet-5 (32 and Resnet-50 27 networks, to verify our theoretical findings.
The synthetic data are generated using a oracle model in Figure I The input Vr 's are randomly generated from Gaussian distribution N Laxa) independently, and indices of non-pruned weights of the j-th neuron are obtained by randomly selecting T3 numbers without replacement from (d], For the convenience of generating specific F, the indices of non-pruned weights are almost overlapped E, E. > 0.95K3) except for Figure ( In Figures 2 and |4| ry is selected uniformly from [0.97, 17] for a given F. and ry are the same in value for all j in other figures. Each non-zero entry of W is randomly selected from [-0 0.5, 0.5) independently. The noise & 's are i.i.d. from (0, o²), and the noise level is measured by a/ / Ey., where E, is the root mean square of the noiseless outputs.
2 'The source codes used are downloaded from https//giithbb.cmm/iiAAAAGo LLTpCCCV_H_HHH____ L Pre- Pre-training.
7

---

4.1 Evaluation of theoretical findings on synthetic data
Local convexity near W We set the number of neurons K 10, the dimension of the data = 500 and the sample size N = 5000. Figure e iillustrates the success rate of Algorithm when F changes. The y-axis is the relative distance of the initialization W to the ground-truth. For each pair of and the initial distance, 100 trails are constructed with the network weights, training data and the initialization ( are all generated independently in each trail. Each trail is called successful the relative error of the solution W returned by Algorithm | measured by | W IF W W/ I[ less than 10-1 A black block means Algorithm fails in estimatinn W in all trails while a white block indicates all success, As Algorithm | succeeds if (0) is in the local convex region near W we can see that the radius of convex region is indeed linear in -73, as predicted by Theorem
Convergence rate. Figure shows the convergence rate of Algorithm [ when 7 changes. N 5000, = 300, K = 10, exponentially the number of iterations increases, indicating the linear convergence of Algorithm As shown in Figure Bjb), the results are averaged over 20 trials with different initial points, and the areas in low transparency represent the standard deviation errors. We see that the convergence rate is almost linear in vF, as predicted by Theorem 2 We also compare with GD by setting One can see that AGD has a smaller convergence rate than GD, indicating faster convergence.
0.5, and 3 = 0.2. Figure 3 shows that the relative error decreases
10%
34
Convergence rale
30
Relative error
0.99
22
100
190
0.985
10:5
10
0.90
X-GD (8 -
175x
0.975
0.2)
10
12
14
16
18
20
1000
1500
2000
10
Number of Iterations
Figure 2: The radius of the lo- cal convex region against F
(a)
(b)
Figure 3: Convergence rate when 7 changes
Sample complexity. Figures and fixed as 100. In Figure 4 we construct 100 independent trails for each pair of N and r, where the
andd show the success rate of Algorithm when varying N and F.
ground-truth model and training data generated independently in each trail. One can see that the
required number of samples for successful estimation is linear T, as predicted by (8). In Figure 5 r, is fixed 20 for all neurons, but different network architectures after pruning are considered. One can see that although the number of remaining weights is the same, F can be different in different architectures, and the sample complexity increases increases, as predicted
Number of Samples (N)
10
550
Relative ervor
0.8
Relative enter
10:3
450
0.6
350
250
0.4
10-5
150
0.2
10-5
10
50
200
250
300
50
70
6/A, 10
Number of samples (N)
Figure 4: Sample complexity
Figure 5: Relative error against
Figure 6: Relative error against
when F changes
7 at different noise level
Performance in noisy case. Figure shows the relative error of the learned model by Algorithm from noisy measurements when changes. N 1000, K 10, and d 300. The results averaged over 100 independent trials, and standard deviation is around 2% to 8% of the corresponding
relative errors. The relative error is linear in 7å, as predicted by (9) Moreover, the relative error is proportional the noise level [[].
4.2 Performance with inaccurate mask synthetic data
The performance of Algorithm iis evaluated when the mask M of the learner network is inaccurate.
The number of neurons K is 5. The dimension of inputs d is 100. rī of the oracle model is 20 for

---

all j E [K]. GraSP algorithm [55] is employed to find masks based only on early-trained weights in 20 iterations of AGD. The mask accuracy is measured by
|| M / M where M is the mask of the oracle model. The pruning ratio is defined as
llo.
Tave/d x 100%. The number of training samples N is 200. The model returned by Algorithm is evaluated on Niea = 10 samples,
and the test error measured by vEn 1y Dn /Nies. where In. is the output of the learned model with the input En, and (I,, Vr.) is the n-th testing sample generated by the oracle network.
Improved generalization by GraSP. Figure shows the test error with different pruning ratios. For each pruning ratio, we randomly generate 1000 independent trials. Because the mask of the learner network in each trail is generated independently, we compute the average test error of the learned models in all the trails with same mask accuracy. If there are less than 10 trails for certain mask accuracy, the result of that mask accuracy not reported it is statistically meaningless. The test error decreases as the mask accuracy increases. More importantly, at fixed mask accuracy, the test error decreases as the pruning ratio increases. That means the generalization performance improves when F deceases, even if the mask is not accurate.
Number of iterations
1500
10"
10
+ Pruning cate 10% Pruning moto 50% -Prunin cate
Pruning rati- 10%
Test ento
1000
Pruning cate
Tist eeTor
Pruning rioo- 50%
Pruning ratlo 30%
10
Pruning ratio 40%
Pruning milo = 70%
Pruning ratio = 50%
500
10
Pruning retio = 60%
Pruning ratio = 70%
10.6
0.7
0.8
0.9
10
100
10
10.5
10.b
50
100
150
200
250
Mask accuracy
Test emrrr
Number of samples (N)
Figure 7: Test error against mask accuracy with different pruning ratios
Figure 8: Convergence
Figure 9: Test error against the number of samples with mask accuracy in [0.85, 0.9]
rate with mask accuracy in [0.85, 0.9]
Linear convergence. Figure g shows the convergence rate of Algorithm with different pruning ratios. We show the smallest number of iterations required to achieve certain test error of the learned model, and the results are averaged over the independent trials with mask accuracy between 0.85 and 0.90. Even with inaccurate mask, the test error converges linearly. Moreover, as the pruning ratio increases, Algorithm]] [ converges faster.
Sample complexity with respect to the pruning ratio. Figure 9 shows the test error when the number of training samples N changes. All the other parameters except N remain the same. The results are averaged over the trials with mask accuracy between 0.85 and 0.90. We can see the test error decreases when N increases. More importantly, as the pruning ratio increases, the required number of samples to achieve the same test error (no less than 10-3 decreases dramatically. That means the sample complexity decreases as F decreases even if the mask inaccurate.
4.3 Performance of IMP synthetic, MNIST and CIFAR-10 datasets
We implement the IMP algorithm to obtain pruned networks on synthetic, MNIST and CIFAR-10 datasets. Figure TO shows the test performance of pruned network on synthetic data with different sample sizes. Here in the oracle network model, K = 5, d = 100, and r = 20 for all j E [K]. The noise level a/ E,, 10-3, One observation is that for fixed sample size N greater than 100, the test error decreases as the pruning ratio increases. This verifies that the IMP algorithm indeed prunes the network properly. It also shows that the learned model improves as the pruning progresses, verifying our theoretical result in Thcorem 2 that the difference of the learned model from the oracle model decreases as T3 decreases. The second observation is that the test error decreases as N increases for any fixed pruning ratio. This verifies our result in Theorem 2 that the difference of the learned model from the oracle model decreases the number of training samples increases. When the pruning ratio is too large (greater than 80%), the pruned network cannot explain the data properly, and thus the test error is large for all N. When the number of samples is too small, like N = 100, the test error is always large, because it does not meet the sample complexity requirement for estimating the oracle model even though the network is properly pruned.
Figures and 12 show the test performance of learned models by implementing the IMP algorithm on MNIST and CIFAR-10 10 using Lenet-5 [32 and Resnet-50 (27) architecture, respectively. The

---

experiments follow the standard setup in [00] except for the size of the training sets. To demonstrate the effect of sample complexity, we randomly selected N samples from the original training set without replacement. As we can see, properly pruned network (i.e., winning ticket) helps reduce the sample complexity required to reach the test accuracy of the original dense model. For example, training on pruned network returns model (e.g., P1 and P3 in Figures] 11 and (2) that has better testing performance than a dense model (e.g., P2 and P4 in Figures I1 and 12) trained on a larger data set. Given the number of samples, we consistently find the characteristic behavior of winning tickets: That is, the test accuracy could increase when the pruning ratio increases, indicating the effectiveness of pruning. The test accuracy then drops when the network is overly pruned. The results show that our theoretical characterization of sample complexity is well aligned with the empirical performance of pruned neural networks and explains the improved generalization observed in LTH.
10'
4%
250000
7%
37500
-00000
10
6.5%
42500 -B N
Tost
Test ettor
40000
(5000
0-8 8
10a
6%
10
5.5%
100
Percenlage of remaining parameters (%)
1.5%
0
20
40
60
80
100
60
80
100
---N=100 - N=150 -8- N=200
N N-2 -B- N-300 N-305
Pruning rolio (%)
Pruning ralio (%)
Figure 10:
Test error of pruned
Figure 11: Test accuracy of Figure 12:
Test accuracy of
models on the synthetic dataset
pruned LeNet-5 on Mnist
pruned Resnet-50 on Cifar- 10
5
Conclusions
This paper provides the first theoretical analysis of learning one-hidden-layer pruned neural networks, which offers formal justification of the improved generalization of winning ticket observed from empirical findings in LTH. We characterize analytically the impact of the number of remaining weights in a pruned network on the required number of samples for training, the convergence rate of the learning algorithm, and the accuracy of the learned model. We also provide extensive numerical validations of our theoretical findings.
Broader impacts
We see no ethical or immediate societal consequence our work. This paper contributes to the theoretical foundation of both network pruning and generalization guarantee. The former encourages the development learning method to reduce the computational cost. The latter increases the public trust in incorporating AI technology in critical domains.
Acknowledgement
This work was supported by AFOSR FA9550-20-1-0122 ARO 191INF-21-1-025: NSF 1932196 and the Renssclacr-IBM AI Research Collaboration httpp//airc.rpp.cdu part of the IBM AI Horizons Network http://imm.i//AHHooriiii Haolin Xiong Rensselaer Polytechnic Institute and Yihua Zhang Michigan State University for the help in formulating numerical experiments. We thank all anonymous reviewers for their constructive comments.
We thank Tianlong Chen at University of Texas at Austin,
References
[1] Z. Allen-Zhu, Y. Li, and Z. Song. A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning, pages 242-252. PMLR, 2019.
[2] Arora, R. Ge, B. Neyshabur, and Zhang. Stronger generalization bounds for deep nets via compression approach. In J. Dy and A. Krause, editors, Proceedings of the 35th International
10

---

Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 254-263, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
[3] C. Baykal, L. Liebenwein, I. Gilitschenski, D. Feldman, and D. Rus. Data-dependent coresets for compressing neural networks with applications to generalization bounds. In International Conference on Learning Representations, 2018.
[4] C. Baykal, L. Lie I. Gilitschenski, D. Feldman, and D. Rus. Sipping neural networks: Sensitivit-iifoommed provable pruning of neural networks, arXiv preprint 1rXiv:1910.05422. 2019.
[5] M. Ben, M. Osadchy, V. Braverman, S. Zhou, and D. Feldman. Data-independent neural pruning via coresets. In International Conference on Learning Representations (ICLR), 2020.
[6] M. I., Bermingham, R. Pong- Wong, A. Spiliopoulou, C. Hayward, I. Rudan, Camphell, A. F. Wright, J. F. Wilson, F. Agakov, P. Navarro, et al. Application of high-dimensional feature selection:
evaluation for genomic prediction in man. Scientific reports, 5(1): 2015.
[7] R. Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013.
[8] A. Brutzkus and A. Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 605-614, JMLR. org, 2017.
Learning-Volume
[9] R. T. Chen, Y. Rubanova, J. Bettencourt, and D. Duvenaud. Neural ordinary differential equa- tions. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 6572-6583, 2018.
[10] T. Chen, J. Frankle, S. Chang, S. Liu, Y. Zhang, M. Carbin, and Z. Wang. The lottery tickets hypothesis for supervised and self-supervised pre-training in computer vision models. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 16306 16316, 2021.
[11] T. Chen, J. Frankle, S. Chang, S. Liu, Y. Zhang, Z. Wang, and M. Carbin. The lottery ticket hypothesis for pre-trained bert networks. arXiv preprint arXiv:2007. 122223, 2020.
[12] I.. Chizat and F. Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 3040-3050, 2018
[13] M. Denil, B. Shakibi, L. Dinh, M. Ranzato, and N. de Freitas. Predicting parameters in deep learning. In Proceedings of the 26th International Conference on Neural Information Processing Systems-Volue Volume 2, pages 2148-2156 2013.
[14) V. C. Dinh and L. S. Ho. Consistent feature selection for analytic deep neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 2420-2431. Curran Associates, Inc., 2020.
[15] X. Dong, S. Chen, and S. Pan. Learning to prune deep neural networks via layer optimal brain surgeon. In Advances in Neural Information Processing Systems, pages
2017.
[16] S. S. Du, J. D. Lee, Y. Tian, A. Singh, and B. Poczos. Gradient descent learns one-hidden- layer cnn: Don't be afraid of spurious local minima. In International Conference Machine Learning, pages 1338-137,,1 2018
[17] S. S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes over- parameterized neural networks. In International Conference on Learning Representations, 2019.
[18] B. Elesedy, V. Kanade, and Y. W. Teh. Lottery tickets in linear models: An analysis of iterative magnitude pruning. arXiv preprint 2tt1:2007.082444 2020.
[19] U. Evei, T. Gale, J. Menick, Castro, and Elsen. Rigging the lottery: Making all tickets winners. International Conference Machine Learning, 2020.

---

[20] J. Frankle and M. Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In Internatoonal Conference on Learning Representations, 2019.
[21] J. Frankle, G. K. Dziugaite, D. Roy, and M. Carbin. Linear mode connectivity and the lottery ticket hypothesis. In International Conference on Machine Learning, pages 3259-3269. PMLR, 2020.
[22] J. Frankle, G. K. Dziugaite, D. M. Roy, and M. Carbin. Stabilizing the lottery ticket hypothesis. arXiv preprint arXiv: 1903.01113.111,, 2019,,
[23] H. Fu, Y. Chi, and Y. Liang. Guaranteed recovery of one-hiddennlayer neural networks via cross entropy. IEEE transactions on signal processing, 68:3225-3233 2020.
[24] I. Guyon and A. Elisseeff. An introduction to variable and feature selection. Journal of machine learning research, ((MMar):15571111 2003.
[25] S. Han, J. Pool, J. Tran, and W. Dally. Learning both weights and connections for efficient neural network. Advances in neural information processing systems, pages 1135-1143, 2015.
[26] B. Hassibi and D. G. Stork. Second order derivatives for network pruning: Optimal brain surgeon. In Advances neural information processing systems, pages 164-171, 1993.
[27] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
[28] H. Hu, R. Peng, Y.-W. Tai, and C.-K. Tang. Network trimming: A data-driven neuron pruning approach towards efficient deep architectures. arXiv preprint 1607.0000..3330 00.5000000 2016.
[29] S. loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference Machine Learning, pages 448 456, 2015.
[30] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580, 2018.
[31] V. Kuleshov, A. Chaganty, and P. Liang. Tensor factorization via matrix factorization. In Artificial Intelligence and Statisties, pages 507-516, 2015.
[32] Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel. Backpropagation applied to handwritten zip code recognition. Neurul computation, 1(4):541-55, 1989.
[33] Y. LeCun, J. S. Denker, and S. A. Solla. Optimal brain damage. In Advances in neural information processing systems, pages 598-605 1990.
[34] Y. A. LeCun, L. Bottou, G. B. Orr, and K.-R. Müller. Efficient backprop. In Neural networks: Tricks of the trade, pages 9 9-48. Springer, 2012.
[35] L. Liebenwein, C. Baykal, H. Lang, D. Feldman, and D. Rus. Provable filter pruning for efficient neural networks. In International Conference on Learning Representations, 2019.
[36] Z. Liu, M. Sun, T. Zhou, G. Huang, and T. Darrell. Rethinking the value of network pruning. In International Conference on Learning Representations, 2018.
[37] R. Livni, S. Shalev-Shwartee and O. Shamir. On the computational efficiency of training neural networks. Advances in neural information processing systems, pages 855-863, 2014.
[38] Lu, C. Ma, Y. Lo, J. Lu, and L.. Ying. A mean field analysis of deep resnet and beyond: To- wards provably optimization via overparameterization from depth. In International Conference on Machine Learning, pages 6426-6436. PMLR, 2020.
12

---

[39] E. Malach, G. Yehudai, S. Shalev- Schwar-, and O. Shamir. Proving the lottery ticket hypothesis: Pruning all you need, International Conference on Machine Learning, pages 6682-6691. PMLR, 2020.
[40] S. Mei, A. Montanari, and P.-M. Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(33):E7665-E776) E7671, 2018.
[41] D. Molchanov, A. Ashukha, and D. Vetrov. Variational dropout sparsifies deep neural networks.
In International Conference on Machine Learning, pages 2498-2507 2017.
[42] B. Neyshabur. Towards learning convolutions from scratch. Advances in Neural Information Processing Systems, 33, 2020.
[43] L. Orseau, M. Hutter, and O. Rivasplata. Logarithmic pruning is all you need. Advances in Neural Information Processing Systems, 33, 2020.
[44] S. Oymak and M. Soltanolkotabi. Toward moderate overparamettrrizatio:: Global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1(1), 2020.
[45] V. Ramanujan, M. Wortsman, A. Kembhavi, A. Farhadi, and M. Rastegari. What's hidden in a randomly weighted neural network? In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 1 1189311 19902, 2020.
[46] A. Renda, J. Frankle, and M. Carbin. Comparing rewinding and fine-tuning in neural network pruning. In International Conference on Learning Representations, 2019.
[47] I. Safran and O. Shamir. Spurious local minima are common in two-layer relu neural networks. In International Conference on Machine Learning, pages 4430-4438, 2018
[48] O. Shamir. Iestributtionsppeiiin hardness of learning neural networks. The Journal of Machine Learning Research, 19(1):1135-11) 2018.
[49] S. Singh and A. Majumdar. Deep sparse coding for non non-intrusive load monitoring, 9(5):4669- 4678, Feb. 2017.
[50] M. Soltanolkotabi, A. Javanmard, and J. D. Lee. Theoretical insights into the optimization landscape of para-paraaeerriee shallow neural networks. IEEE Transactions Information Theory, 65(2):742-769, 2018.
[51] S. Srinivas and R. V. Babu. Data-free parameter pruning for deep neural networks. arXiv preprint arXiv: 1507:01507701499 2015.
[52] Y. Tian. An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis. In Proceedings of the 34th International Conference on Muchine Leurning- Volume 70, pages 3404-3413, JMLR. org, 2017.
[53] J. A. Tropp. frer-friendly tail bounds for sums of random matrices. Foundations of computa- lional mathematics, 12(4):389-434 2012.
[54] R. Vershynin. Introduction to the non non-asymptotic analysis of random matrices. arXiv preprint arXiv: 101 2010.
[55] C. Wang, G. Zhang, and R. Grosse. Picking winning tickets before training by preserving gradient flow. International Conference on Learning Representations, 2019.
[56] F. Wang, K. Li, C. Liu, Z. Mi, M. Shafie-Khah, and J. P. S. Catalão. Synchronous pattern matching principle-based residential demand response baseline estimation: Mechanism analysis and approach description. IEEE Transactions on Smart Grid, 96)):6972-6885 2018.
[57] W. Wen, C. Wu, Y. Wang, Y. Chen, and H. Li. Learning structured sparsity in deep neural net- works. Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 2092- 2016.
13

---

[58] T.-J. Yang, Y.-H. Chen, and V. Sze. Designing energy-efficient convolutional neural networks using energy-aware pruning. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pages 5687-5695, 2017.
[59] M. Ye, C. Gong, L. Nie, D. Zhou, A. Klivans, and Q. Liu. Good subnetworks provably exist: Pruning via greedy forward selection. In International Conference on Machine Learning, pages 10820-108300 PMLR, 2020.
[60] M. Ye and Y. Sun. Variable selection via penalized neural network: drop-out-one loss approach. In International Conference on Machine Learning, pages 5620-5629. PMLR, 2018.
[61] M. Ye, L. Wu, and Q. Liu. Greedy optimization provably wins the lottery: Logarithmic number of winning tickets enough. Advances in Neural Information Processing Systems, 33, 2020.
[62] G. Yehudai and Shamir. On the power and limitations of random features for understanding neural networks. In Advances in Neural Information Processing Systems, pages 6594 6604, 2019.
[63] H. You, L. Y. Fu, Y. Wang, X. Chen, R. G. Baraniuk, Z. Wang. and Y. Lin. Drawing carly-bird tickets: Toward more efficient training of deep networks. In International Conference on Learning Representations, 2019.
[64] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprini 161 1.03530, 2016
[65] S. Zhang. M. Wang, S. Liu, P.-Y. Chen, and J. Xiong. Fast learning of graph neural networks with guaranteed generalizabllity.ne-- haaee-hidd--aaaye layer case. In 2020 International Conference on Machine Learning (ICML), 2020.
[66] S. Zhang, M. Wang, S. Liu, P.-Y. Chen, and J. Xiong. Guaranteed convergence of training convolutional neural networks via accelerated gradient descent. In 2020 54th Annual Conference on Information Sciences and Systems (CISS), 2020.
[67] S. Zhang, M. Wang. J. Xiong, S. Liu, and P.- Y. Chen. Improved linear convergence of training cnns with generalizability guarantees: A one-hidden-layer case. IEEE Transactions on Neural Networks and Learning Systems, 32(6):2622-28 2635, 2020.
[68] L. Zhao, Q. Hu, and W. Wang. Heterogeneous feature selection with multi-modal deep neural networks and sparse group lasso. IEEE Transactions on Multimedia, 17(11):196-1145 2015,
[69] K. Zhong. Z. Song, P. Jain, P. L. Bartlett, and I. S. Dhillon. Recovery guarantees for one- hidden-layer neural networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 4140 4149. JMLR. org, https//arxxi.orr/abs//// 706.03175, 2017.
[70] H. Zhou, J. Lan, R. Liu, and J. Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. In Advances in Neural Information Processing Systems 32, pages 3597-3607. 2019.
[71] W. Zhou, V. Veitch, M. Austern, R. P. Adams, and P. Orbanz. Non-vacuous generalization bounds at the imagenet scale: a pac-bayesian compression approach. In International Confer- ence on Learning Representations, 2018
[72] D. Zou, Y. Cao, D. Zhou, and Gu. Gradient descent optimizes over-parameteerized deep relu networks. Machine Learning. (09(3):467-49)) 2020.
[73] D. Zou and Q Gu. An improved analysis of training wer-parameterized deep neural networks.
In Advances Neural Information Processing Systems, pages 2055-2064, 2019.
14


Reviews:
[{"review_id": "mHLi0ES-kYs", "reviewer": "Reviewer_Udgq", "summary": "This work takes a theoretical view of LTH, leveraging the geometric structure of the objective function to analyze the generalization error of a pruned network trained in a teacher-student fashion. In particular, they prove that, as a model is pruned, the desirable (convex) region with high-guaranteed generalization performance enlarges, providing explanation for improved performance of winning tickets. Then, the sample complexity of training the pruned network to achieve zero generalization error is analyzed, finding that the number of samples required is proportional to the number of un-pruned weights. Interestingly, the work finds that pruned models enjoy faster convergence to high performance, providing another possible explanation of why winning tickets outperform dense networks.\n", "questions": "", "limitations": "", "rating": 8, "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": "I begin my review by emphasizing that I am completely open to author feedback upon my review. My final score will be mostly based upon discussion with authors in regard to my points below. \n\nGeneral opinion:\nThe theoretical contributions of this work are very extensive/impressive. All theoretical results are extensively studied in simulated experiments, and experiments on real datasets are also provided. Although the problem setup within the work is somewhat peculiar (I have not seen such a student-teacher setup used within theoretical LTH analysis), I find the work to be well-written, interesting, and useful.\n\nPros:\n- The analysis of the sample complexity required to train the pruned model to convergence seems novel and interesting. It is especially interesting that this sample complexity is found to be superior to the dense model from which the pruned model is derived.\n- The incorporation of momentum into the gradient descent algorithm for pruning is interesting. The fact that acceleration is also achieved in theory is well-done.\n- Analysis is also performed for the generalization performance of pruned networks, which is not as common in theoretical work for LTH. (The only others I know of are https://arxiv.org/abs/1802.05296 or https://arxiv.org/abs/1804.05345, which are both referenced). \n- Theoretical analysis within this work, although based on arguments in [63], seems to be novel and requires numerous technical developments in comparison to previous work. \n- Experiments on real datasets are included.\n\nCons:\n- Analysis is limited to gaussian input data. I believe this is the main/most unrealistic limitation of the theoretical analysis. \n- Theoretical analysis is only done one one-hidden-layer networks (though this is not truly a con, as this is true of much theoretical work for LTH and neural networks in general).\n\nQuestions:\n- I do not fully understand why both teacher and student networks are pruned within the setup. Additionally, this teacher-student setup is not fully reflective of standard methodologies for LTH, so I am a bit curious about how this setup was derived (I assume this setup was adopted from [63], http://proceedings.mlr.press/v70/zhong17a.html?).\n- The paper claims that the convex regions for pruned networks are enlarged. This means that pruned networks have a larger region in which linear convergence is achieved (if I am not mistaken). Although this may mean the pruned network converges faster due to the larger region of convexity, this does not say anything about the quality of the solution, correct? It seems like this analysis cannot be used as evidence for winning tickets having superior performance (though superiority is shown in other areas with sample complexity/generalization bounds). \n- Is there any previous work that studies whether analysis with gaussian input data is reflective of practical behavior? I am unsure whether such an assumption is very limiting (possibly this determination can be made by discussing differences between synthetic/real experiments within the experimental section of this work). \n\nMinor Comments:\n- There are a lot of other papers that analyze over-parameterized neural networks that could be added to the related work (though maybe they are not as relevant to this work, I am not sure). For example, https://arxiv.org/abs/1902.04674 \n- I would recommend that the numerical experiments devote more space/attention to experiments on real datasets. Right now, it seems to be denominated by synthetic datasets, though I understand this is in an attempt to numerically verify aspects of the theory.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss limitations of their work explicitly, see above review for more details. There is no negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "_H1Ec0IZVrE", "reviewer": "Reviewer_b8vh", "summary": "The paper analyzes the possibility of recovering the weight of a teacher network using a student network which is as dense as the original one. The authors prove that with enough samples drawn from the teacher network, the recovery can be done on one-hidden-layer neural networks with linear convergence speed. The authors also discuss the correlation between the needed samples and the sparsity of the teacher network.\n\nTo sum up, the well-designed structure makes the workﬂow clear and easy to follow, but the further analysis and discussion are expected to clarify some contributions in the techniques as well as in the evaluation section.", "questions": "", "limitations": "", "rating": 3, "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": "Strength\n1. The paper analyzes the influence of the number of remaining parameters in pruned subnetworks and derives the required number of samples for successful convergence.\n\n2. The authors conduct the theoretical analysis and justification for improved generalization error of winning ticket in the LTH.\n\n3. The extensive evaluation on both synthetic and real datasets demonstrates the effectiveness of the proposed approach for neural network pruning.\n\nWeakness\n1. The strong assumption that one-hidden-layer neural networks and the input data must follow the Gaussian distribution seriously limit the applicability of the proposed method.\n\n2. The authors claims to provide the theoretical analysis and justification of the LTH. The paper learns pruned neural networks by using the teacher-student setup. However, this is inconsistent with the Lottery Ticket Hypothesis setting that the pruned subnetwork should be \"trained in isolation\".\n\n3. In the main theorems (Theorems 1 and 2), the number of samples drawn from the teacher model are required to be proportional to \\Omega(K^4) or \\Omega(K^6), where K is number of the neurons in the neural network. This may result in a serious efficiency issue, such that the method only work on small-size neural networks. In fact, the paper conduct the experiments over neural networks with merely 5 or 10 neurons.\n\n4. It would be nice to conduct the experiments with the SOTA LTH and neural network pruning algorithms.\n\n-------------------\n\nPost-rebuttal update:\n\nThanks for the authors' efforts in addressing the raised concerns. I have read the author response and other reviews and keep my score due to the following two reasons.\n\nIn the paper, the derived theoretical justification or explanation over LTH or network pruning is based on a strong assumption of the one-hidden-layer neural networks and the input data with Gaussian distribution. Typically, LTH or network pruning methods don't have such strong assumption. If the authors claim the theoretical justification over LTH or network pruning is the main contribution of this paper, then the authors need to extend the proof to general neural networks without this restriction, although this extension is non-trivial. Otherwise, it is hard to say that the paper theoretically justifies the LTH or network pruning. In fact, real-world neural networks are often not satisfied with this assumption, such as Lenet-5 and Resnet-50 used in the experiments in the paper.\n\nLocal convexity (radius of convex region) and convergence are two main theoretical results in the paper. They are validated on synthetic data with small networks (5 or 10 neurons), but not on real data with large ones (Lenet-5, and Resnet-50).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper provided some interesting theoretical insights in the training process of pruned neural networks. However, the analysis is based on impractical assumptions while the derived bound is not tight enough, such that the proposed algorithm is difficult to work on real-scenario neural networks.", "review_text": "", "extra_scores": {"ethical_concerns": "No explicit ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "KWeDz0sSi_2", "reviewer": "Reviewer_HCZd", "summary": "The paper gives theoretical explanation for improved generalization error of winning tickets for which only empirical results are known. Their results are based on teacher-student setting in which training samples are assumed to be generated from an unknown teacher network and student network is supposed to learn only from those samples. They give an accelerated gradient descent method for learning the pruned  network and convergence and sample complexity analysis for this algorithm. The empirical risk function is shown to have an enlarged convex region for a pruned network, which justifies the importance of the winning ticket. Learning on pruned network with the AGD algorithm gives a model closer to the teacher network with the same number of iterations, which implies better generalization of the trained pruned network. These findings are validated with experiments on synthetic and real datasets (MNIST, CIFAR-10). \n", "questions": "", "limitations": "", "rating": 7, "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": "There is significant empirical evidence in support of lottery tickets, however theoretical understanding/justification is not very clear in the literature. This work tries to offer theoretical explanation for the winning tickets in the teacher student setup. Most of the results of the paper are inspired by [63], which has similar results for fully-connected one layer neural network. Straight forward application of bounds from this prior work yields suboptimal bounds for pruned network and hence they adapted it to pruned networks setting. In addition to some key differences in analysis like application of novel concentration bounds, non-smooth activation functions, they also construct new tensors for pruned networks. Overall, the paper is well written, looks technically sound. Though the proofs are inspired from prior works, the adaptation to pruned networks setting is also not trivial. In sum, despite limited technical novelty, I think its a good contribution towards theoretical understanding of winning tickets. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is a limitations section, which highlights key limitations of this work, like it is based on teacher-student setting and one-hidden layer neural network. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "2vSf2fkH8jY", "reviewer": "Reviewer_1uan", "summary": "This paper presents a theoretical analysis of the advantages of learning pruned neural networks . This analysis considers a teacher-student setup with a finite number of training samples. The theoretical results presented in the paper show that pruned networks can have multiple advantages, such as faster training convergence, a lower number of samples required for successful convergence and an enlarged convex region.", "questions": "", "limitations": "", "rating": 7, "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": "Pros:\n\nThis paper tries to give some theoretical insights that explain the performance of pruned neural networks. I agree with the authors that this problem has been studied mostly empirically and a deeper theoretical analysis can provide a better understanding of the behaviour of pruned neural networks. For this reason, I believe that this paper can be a valid contribution in this direction.  \n\nCons:\n\n I think that the analysis presented in the paper has some limitations: i) as highlighted by the authors in Sec. 3.4, this analysis considers only one hidden layer and assumes that the input follows the Gaussian distribution; ii) the authors assume that the whole training data is used at each iteration (instead of using minibatches).\nFor these reasons, it is not clear to me if the theoretical results presented in the paper can be useful when we consider a real setting. Are there any useful insights that can be used in real applications to, e.g., improve the training of pruned neural networks or find better winning tickets? The experiments on real datasets presented in the paper are quite limited and show only the effect of sample complexity, which is not very informative and does not reflect what happens in real applications since usually training is performed using minibatches and does not use the whole training set at each iteration. \n\nMinor comments:\n\nMany details of the theoretical analysis are discussed only in the appendix. Some of them, such as the tensor initialization method, are fundamental in order to understand the theoretical results presented in the paper. I suggest to try to add them to the main paper. This would increases the paper readability.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: We thank the authors for this submission. The paper well-motivates the approach. The authors have provided extensive responses to the concerns raised and the AC + reviewers really thank them for their effort. Overall, the new results obtained during the rebuttal definitely improve the quality of the paper. We all believe that the inclusion of these results (summarized) during the rebuttal period is something that does not heavily change the message of this paper.

There was discussion and consensus that this work is interesting. Having in mind issues/concerns raised by the reviewers and the authors (via private communication), the main points of reviewers during further discussion were that this paper deserves publication, given the promised fixes by the authors during the discussion period.
Decision: Accept (Poster)