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:  (2021)
Keywords: Sparse neural network
Lottery Ticket Hypothesis
network pruning
generalization analysis
optimization landscape
sample complexity

Abstract: The $\textit{lottery ticket hypothesis}$ (LTH) states that learning on a properly pruned network (the $\textit{winning ticket}$) has improved test accuracy over the originally 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 sparse 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 sparse neural network is specified as (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 model weights in the hidden layer. With a fixed number of samples, training a pruned neural network enjoys a faster convergence rate to the desirable 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 sparse neural network of one hidden layer, while experimental results are further provided to justify the implications in pruning multi-layer neural networks.

Under review conference paper at ICLR 2021
WHY LOTTERY TICKET WINS? A THEORETICAL PERSPECTIVE OF SAMPLE COMPLEXITY ON SPARSE NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
The lottery ticket hypothesis (LTH) (Frankle & Carbin 2019) states that learning on a prop- erly pruned network (the winning ticket) has improved test accuracy over the originally 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 winning ticket remains elusive. To the best of our knowledge, our work, for the first time, characterizes the performance of training a sparse 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 the neural network model is pruned, indicating the structural importance of winning ticket. Moreover, as the algorithm for training a sparse neural network is speci- fied as (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 fixed number of samples, training pruned neural network enjoys faster convergence rate to the desirable 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 sparse neural network of one hidden layer, while experimental results are further provided to justify the implications in pruning multi-layer neural networks.
INTRODUCTION
Neural network pruning reduce the computational cost of training model significantly (LeCun al.
1990 Hassibi & Stork 1993. Dong et al.) 2017 Han et al. 2015: Hu et al., 2016,) Srinivas & Babu 2013
Yang et al.) [2017; Molchanov al. 20117) ). The recent Lottery Ticket Hypothesis (LTH) (Frankle & Carbin 2019) claims that a randomly initialized dense neural network always 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 most the same amount of training time. This so-called "improved generalization of winning tickets" verified empirically in (Frankle& & Carbin, 2019). LTH has attracted significant amount of recent research interests (Ramanujan et al. [2020|Zhou /hou et al., 2019 Malach et al.) 2020). Despite the empirical success (Evci al., 22000] You et al. [019]] Wang et al.) 2019: Chen et al. 2020a), the theoretical justification of winning tickets remains clusive except for a few recent works. |Malach et al. (2020) provides the first theoretical evidence that within randomly initialized neural network, there exists a good sub-network that can achieve the same test performance as the original network. Meanwhile, recent work (Neyshabur) 2020)
trains neural network by adding the l regularization term to obtain a relatively sparse neural network, which

---

Under review conference paper at ICLR 2021
has a better performance numerically. Arora al. 2018 and Zhou et al. (2018) show that the expressive power of a neural network is comparable to a compressed neural network and both networks have the same generalization error. However, no theoretical explanation has been provided for the improved generalization of winning tickets, i.e., winning tickets can achieve higher test accuracy after the same training time.
Contributions:
This paper provides the first systematic analysis of learning sparse neural networks with a finite number of training samples. Our analytical results also provide justification of the LTH from the per- spective of the sample complexity. In particular, we provide the first theoretical justification of the improved generalization of winning tickets. Specific contributions include:
Sparse neural network learning via accelerated gradient descent (AGD); We propose an AGD algo- rithm with tensor initialization to learn the sparse model from training samples. Considering the scenario where there exists a ground-truth sparse one-hidden-layee neural network, we prove that our algorithm converges to the ground-truth model linearly. which has guaranteed generalization testing data.
2. First sample complexity analysis for pruned networks: We characterize the required number of sam- ples for successful convergence, termed the sample complexity. Our sample complexity depends linearly on the number of the non-pruned weights of the sparse network and is a significant reduction from directly applying conventional complexity bounds in (Zhong et al. 2017 Zhang et al. (020a(c).
3. Characterization of the benign optimization landscape of pruned networks: We show analytically that the empirical risk function has enlarged convex region near the ground-truth model if the neural network is sparse, justifying the importance of good sub-network (i.e., the winning ticket).
Characterization of the improved generalization of winning tickets: We show that gradient-descent methods converge faster to the ground-truth model when the neural network is properly pruned, or equiva- lently, learning on a pruned network returns a model closer to the ground-truth model with the same number of iterations, indicating the improved generalization of winning tickets.
1.1 RELATED WORK
Winning tickets. Frankle & Carbin 2019) proposes Iterative Magnitude Praning (IMP) algorithm to obtain the proper sub-network and initialization. IMP and its variations (Frankle et al. 2019a Renda et al.) 2019) succeed in deeper networks like Residual Networks (Resnet)-50 and Bidirectional Encoder Repre- sentations from Transformers (BERT) network (Chen et al.] 20206). (Frankle et al., (019b) shows that IMP succeeds in finding the "winning ticket" if the ticket is stable stochastic gradient descent noise. In parallel, (Liu et al. 2018) shows numerically that the "winning ticket" initialization does not improve over a random initialization once the correct subnetworks are found, suggesting that the benefit of "winning ticket" mainly comes from the sub-network structures.
Over-parameterized model. When the number of weights in a 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 (Livni al.) [004]] /Zhang et al. 2016) /oottan et al. 2018). However, the global optima is not guaranteed to generalize well on testing data (Yehudai Shamir| 2019 Zhang et al. 2016).
Model estimation & Generalization analysis. This framework assumes a ground-truth model that maps the input data to the output labels, and the learning objective to estimate the ground-truth model, which has generalization guarantec testing data. The learning problem has intractably many spurious local minina even for anc-hidden-layer neural networks (Shamir) 2018), [afran Shamir 2018 Zhang et al. Assuming an infinite number of training samples, (Brutzkus & Globerson, |017 Du et al. [018
20161.
Tian
2017) develop learning methods to estimate the ground-truth model. (Fu et al.) 2018 Zhong et al.
2017
Zhang et al. 2020a extend to the practical case of a finite number of samples and characterize the
2

---

Under review conference paper at ICLR 2021
sample complexity for successful estimation of the ground-truth model. Because the analysis complexity explodes when the number of hidden layers increases, all the analytical results about estimating the ground- truth model are limited see-hidden-llyeee neural networks, and the input distribution often assumed to be the standard Gaussian distribution.
1.2 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 and e; denote the identity matrix and the i-th standard basis vector. [2] stands for the set of {1, 2, ... } for any number N In addition, f(r) = ((g(r)
(or f(r) (g((r)) if ʃ C g (or
C g) for some constant C. when is large enough.
[(r) = (g(r)) if both f((r) = (g((r) and f(r) ((g(r) holds, where c S S C for some constant c C when r is large enough.
2 PROBLEM FORMULATION
Given N pairs of training samples D n Yn x=1 where In E Ied represent input features and E IR represents the corresponding output label. We consider a teacher-student setup where for any input æ, the corresponding output y is gen- erated by a sparse me-hidden-layer neural network, which is called teacher, as shown in Fig. [ Specifically, the teacher network is equipped with K neurons where each neuron is connected to r" (r" I df input features. Let W E R contain all the ground truth weights of the K neurons in the teacher network, where the j-th column, denoted by wi E
One-hidden-layer Sparse Neural Network
Naise
Cx
y
Imput
Output
Hidden layar with X Keeerose
IR"", contains the edge weights connected to the j-th neuron. Let 22 denote the set of indices of the input features to which the j-th neuron connected in the teacher network.
Figure 1: Illustration of the model
Given input In, let Zn,0; E IR" represent the sub-vector that is connected to j-th neuron, where j E [K]. Then, regression problem, Yn obtained by the teacher network through
Vn Σ j=1
(
(100TTnnsh kn.0;) + En == g W*) + En:
(I)
where &a is the unknown additive noise and & is the activation function.
We train neuron in the student network is connected to r input features instead rf Let S2 denote the set of indices of the input features which the j-th neuron is connected in the student network. Then, given any estimated weights W [wo, W2, .... wx] E |ReX for the student networks, the empirical risk function with respect
student network equipped with same K neurons in the teacher network, however, each
the training set D is defined
fo (W)
Σ
Σ
dw kn, Un
2N
K
We consider the same r" for each neuron in this paper, but the analysis can be easily modified to handle the case of different numbers of features per neuron.
"The analysis extendable binary classification, and the output is generated by Prob (yn, 1/æ.)) = g(ann W*).
3

---

Under review conference paper at ICLR 2021
where we consider the square loss function here. We focus on the case that r and 22 2 f2% We will discuss how to obtain such a student network from a fully connected neural network in Section 4.1
Hence, the learning objective is estimate proper weight matrix W for the student network from the training samples DD via solving the following problem:
min WER"X
fo(W).
(3)
Let us define an augmented matrix W E Br*k such that Wi, = WGy if belongs to both S2 and 22 and 0 otherwise. Clearly, W is global minimizer both and its expectation ED ED/o(WW) (W).
when measurements are noiseless, i.e., E. = 0 for all n. Hence, if one can estimate W accurately from the training data the student network, one can find the teacher network with W equivalently, which has guaranteed generalization performance on the testing data.
Following the standard assumption in (Zhong et al. 2017). 2n is independent and identically distributed (i.id.) from the standard Gaussian distribution ((0, Laxa).
3 Throughout the paper, we consider rectified linear unit (ReLU), where <(2) max 0}. En can be arbitrary, and only assume &n. is bounded as lsal & [g] for some constant Ç.
The questions that this paper addresses include: (1) what algorithm to estimate the augmented ground truth weights W*? (2) what the sample complexity for the accurate estimate? (3) what is the impact of the network pruning on the difficulty of the learning problem and the performance of the learned model?
Connections with conventional pruned networks. To connect the student network with conventional pruned networks, we define a further augmented matrix W E d where the j-th column of W denoted by vnj, contains the weights connected to the j-th neuron, and W is zero padded in other entries for non-existing weights. other words, " i.Q. = w for all j E [K]. and Wi = 0 if & Ω, The mask matrix M, as discussed in (Frankle Carbin 2019). with respect to W' is defined as Myj = i E O2y. and Mr = 0 otherwise. Then, we have M @ W W where stands for the entry-wise multiplication. In (Frankle & Carbin| (219), an Iterative Magnitude Pruning (IMP) algorithm is proposed to compute the mask matrix M for the lottery ticket. Equation 3 can be equivalently written
N
K
1 = 2N
min WEROEK
fo(W)
(w xnd) - yn
s.t. W W.
(4)
K
1
j=1
where =
wx E RdxK is an estimate of the augmented weight matrix W W is a global minimizer to when measurements are noiseless. Note that (4) differs from the learning problem
[in 122
of the conventional dense networks in the additional constraint M @ W W. Back to the problem setup in this paper, suppose M denotes the mask of the teacher model, then we learn
student network with mask M satisfying Supp MM) 2 Supp(MM". where Supp(-) stands for the indices of the non-zero entries. Moreover, when M is an all-one matrix, i.e., d, (4) reduces to the conventional learning problem of a one-hidden-laye neural network.
We will mainly focus on the case that proper student network is given with r 2 r" and 22 2 Q2 and will discuss how to obtain proper student network by the IMP algorithm in Section 4.1
'The assumption is critical in thcoretical analysis since the proof is built upon bounding the population risk function. and the Gaussian assumption is leveraged to analyze the landscape of the population risk function. It is possible extend the analysis to other distributions and will leave that for future work.
4

---

Under review conference paper at ICLR 2021
3 LOCAL GEOMETRIC STRUCTURE
We defer the algorithmic design and analysis to Section 4 and study the geometric structure of (2) here. Theorem characterizes the local convexity of fo( in It has two important implications.
Strictly local convex ball around W (WW is strictly convex around W and the radius of the convex ball is negatively correlated with vr, where r is the number of non-pruned weights per neuron. Thus, the convex ball enlarges as r' decreases.
2. Importance of the winning ticket architecture: Compared with training on the dense network directly, training on a correctly pruned sub-network has a larger convex region near W which may lead to easier estimation of W To some extend, this result can be viewed as theoretical validation of the importance of the winning architecture (a good sub-network) in (Frankle & Carbin 2019), Formally, we have
Theorem (Local Convexity). Suppose constants Eo, $1 E (0, 1). When the number of samples satisfies
2 log N = ((TTT K
(5)
then for any W that satisfies
Eu w = o
W
(6)
k2
we have
θ
ED E1
1
v f (W) θ
K
(7)
K
Theorem shows that with enough samples shown in ( local region of W as shown in (6). all the eigenvalues of Hessian matrix of the empirical risk function are lower and upper bounded by two positive constants. This property useful in designing efficient algorithms to recover W* as shown in Section 4
Moreover, when the number of samples N fixed and r changes, E1 can be @(vr/N) while (5) is still met. Eo in (7) can be arbitrarily close to but small than 1 - that the Hessian matrix is still positive definite. Then from (6. the radius of the convex ball is @(1) O(vr/N), indicating an enlarged region when r decreases.
4 CONVERGENCE ANALYSIS WITH ACCELERATED GRADIENT DESCENT
We propose to solve the non-convex problem 3 via the accelerated gradient descent (AGD) algorithm, sum- marized Algorithm Compared with the vanilla gradient descent (GD) algorithm, AGD has additional momentum term, denoted by 3 (?() W(t-1)), ), in each iteration. AGD enjoys faster convergence rate than GD in solving optimization problems including learning neural networks (Zhang et al. 2020b). Vanilla GD can be viewed as a special case of AGD by letting 3 = O.
The initial point ( can be obtained through tensor initialization method, which is built upon Algorithm 1 in (Zhong et al. 2017) for fully connected neural networks with modification to handle a sparse neural network. Specifically, we reduce the complexity dependence from input data dimension d to the sparsity the definitions of the high-order moments (see
(13)- in Appendix are modified by replacing æ in VK ビラ=1 En, E R Details of the tensor initialization
Definition& 5.1 in Zhong et al. (2017) with a method provided in Appendix A
The theoretical analyses of our algorithm are summarized Theorem 2 (convergence) and Lemma | tialization). The significance of these results can be interpreted from the following aspects.
(Ini-
5

---

Under review conference paper at ICLR 2021
Algorithm 1 Accelerated Gradient Descent (AGD) Algorithm
1: Input: training data D {( yn.) )n gradient step size 1), momentum parameter 3, and an initial-
ization ( by the tensor initialization method:
2: Partition D into T = (og(1/e) disjoint subsets, denoted (Dijizi:
3: for /. 1,2, ... T do
4: ( = ( v/ (V -W(-)) w((-1)
5: end for
6: Return: ((T)
Linear convergence to the ground-truth model: Theorem 2 implies that if initialized in the local convex region, the iterates generated by AGD converge linearly to the ground truth W when noiseless. When there is noise, they converge to point W The distance between ( and W is proportional to the noise level and scales in terms of (( //N). Moreover, when N is fixed, the convergence rate of AGD is @( Ø(vr/K). Recall that Algorithm reduces to the vanilla GD by setting f = 0. The rate for the vanilla GD algorithm here is ((Vr/K) by setting 8 = 0 by Theorem 2 indicating slower convergence than AGD. Lemma shows the tensor initialization method indeed returns an initial point in the convex region.
2. Sample complexity for accurate estimation: We show that the required number of samples for success- ful estimation is @r d), which is order-wise optimal with respect to the number of non-pruned neuron weights r. and only logarithmic with respect to the input feature dimension d. Our sample complexity much less than the conventional bound of (d log d) for mied networks (Zhong et al. 2017] Zhang et al. 2020a c). This is the first theoretical characterization of learning a pruned network from the perspective of sample complexity.
Improved generalization of winning tickets: We prove that with a fixed number of training samples, training a properly pruned sub-network converges faster to W than training on the original dense net- work. 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 (Frankle & Carbin, 2019)
Theorem 2 (Convergence), Suppose W satisfies (6) and the number of samples satisfies N 2(55" K rog d log(L/s))
(8)
for some Eo E 10.1/2). Let n K/14 in Algorithm Then the iterates (W J returned by Algorithm I converges linearly to W up to the noise level with probability at leust 1 - KTT
d as
(w W S x())
+ K2r O0( d/N) [g].
[ (0) 1'
- W 10 + 0(v K2r K2rlog d/N) Kgl.
(10)
I - S & 0 K2rloog [4)
(11)
where v(B) is the rate of convergence that depends on 3 with v(3t) 0
1=g0 for some non-zero 3* VK
and v0) = 1 =1 0
Lemma (Initialization). Assume the noise K5 < [ and the number of samples N 1 d) for > O, the tensor initialization method outputs W(O), such that (6 holds, i.e., ()) W* 0 EagA))
6

---

Under review as conference paper at ICLR 2021
With a fixed number of samples, when r decreases, ED can be (VVF) while the condition in (8) is still met. Then (0) ()) and v(3*)= = ((vr/K). Therefore, when r decreases, both the stochastic and accelerated gradient descent converge faster. The theoretical bound of the improvement of the convergence rate by accelerated gradient descent is the same as that in (Zhang et al. 2020a However, (Zhang et al.) focus on convolutional neural networks without any network pruning, while our results consider pruned networks. Note that as long as W is initialized in the local convex region, not necessarily by the tensor method, Theorem 2 guaranttes the accurate recovery.
2020a c
In our proof of Theorem we need to address the technical challenge that does not appear in (Zhogg et al. 2017 such that each w connects to different subset of ar here instead of the same x in Zhong et al. 2017 Hence. the concentration theorem cannot be directly applied here to bound the distance between population and empirical risk function as used in (Zhong et all 2017 Moreover, we need to revise the tensor initialization method and the corresponding proof due to the pruned network architecture. If we choose r = d, our analysis reduces to the case in (Zhong et al.) 2017). Moreover, our algorithm enjoys a faster convergence rate since we consider AGD method rather than GD as in (Zhong el al. 2017).
4.1 OBTAINING A PROPER STUDENT NETWORK VIA MAGNITUDE PRUNING
We next show that one can combine Algorithm | and magnitude pruning to find a proper student network
such that r 2 rr and S2 2 S25 from a fully-connected network under some assumptions. Suppose the number of samples is at least S2( d log d log(1 (1/=)). we train directly on the fully-commected dense network using Algorithm The number of iteration in line 2 of Algorithm is set as Ti- = (log(2W max W min)): where Wiin and W max denote the smallest and largest value of W respectively. From (TO). after Ti iterations, the returned model, denote by W(T)), is close to the augmented ground-truth W Specifically, if Wij * 0 and W = 0, then (Ti) > Why sort the weights based on their absolute values and prune them sequentially starting Trom the least absolute value. As long as the ratio of pruned weights is most 1 1-r- /d, all the weights are removed correctly, leading to proper student network. In fact, if we remove exactly 1 - r" /d fraction of weights, the pruned network has the same architecture as the teacher network.
s'y' for any j. ,'3 (See Appendix E for details). Then we
5 NUMERICAL EXPERIMENTS
We first verify theoretical results synthetic data and then analyze the pruning performance of the IMP algorithm (Frankle & Carbin 2019) on both synthetic data and real data, The synthetic data are generated using a ground-truth sparse neural network in Fig. The input {I, ) x= are randomly generated from Gaussian distribution ((, Iaxa) independently, and the index set 22 S JJS K)) is generated by selecting r numbers randomly from [d] without replacement. Each entry of the weight matrix W* is randomly selected
from [-0.5, 0.5] independently. The noise {En J are i.i.d. from ((0 o²), and the noise level is measured
by a/ Ey. where Ey is the average energy of the noiseless outputs {g(Zn; W") calculated as Ey
N 2n 1g( 2
Algorithm| D is implemented with two minor modifications. First, the initial point is randomly selected from { (W(0) (o) - W [| < } for some constant X > 0 to reduce the computation. Second, we use the whole training data instead of a fresh subset in each iteration. Algorithm [ terminates when /|| is smaller than 10-8 reaching 10000 number of iterations. In Section 5.2
7

---

Under review conference paper at ICLR 2021
we implement the IMP algorithm (Frankle & Carbin 2019 prune the neural network. The real dataset
we use is the MNIST dataset, and the network architecture Lenet-5 structure (Lecun et al. 1998).
5.1 EVALUATION OF THEORETICAL. FINDINGS ON SYNTHETIC DATA
Local convexity near the ground-truth. We set the number of neurons K = 5, the dimension of the data d = 500 and the sample size N = 3000. Figure 2 illustrates the success rate of Algorithm | when the network sparsity changes. The y-axis is the relative distance of the initialization W to the ground-truth. For each pair of and the initial distance, we run 100 independent tests, and the network weights, training data and the initialization (0) are all generated independently in each test. Each test is called successful if the relative error of the solution W returned by Algorithm| 1 measured by IW W ||2/||| [ than 10- 4, A black block means Algorithm 1 fails in estimating W in all runs while a white block indicates
||2, is less
all successes. Algorithm succeeds W in the local convex region near W From Figure see that the radius of convex region is indeed linear in - /r, as predicted by Theorem
we can
30
10
==1
0.985
- AGD (5-0:2)
Relative earor
r-0
Convargence rete
0.99
*- GD (340)
26
100
0.985
14
1
130
0.90
0.975
10
12
14
16
20 18
500
1000
1500
2000
6
8
10
12
Number Iterations
Figure 2: The radius of the lo- cal convex region against /r
(a)
(6)
Figure 3: Convergence rate when r changes
Convergence rate. Figure 3 shows the convergence rate of Algorithm [ when changes. N = 3000,
d 300, K = 5, 17 = 0.5, and 3 = 0.2. Figure 3[a) shows that the relative error decreases exponentially the number of iterations increases, indicating the linear convergence of Algorithm As shown in Figure B(), the convergence rate almost linear in vT, as predicted by Theorem 2 We also compare with GD by setting /3 as 0. One
that AGD has smaller convergence rate than GD, indicating faster convergence.
Sample complexity. Figure Isowws the phrase transition of Algorithm T when varying and r. d is fixed 100. For each value of N, we construct 100 independent runs where the ground-truth model and training data are generated independently in each run. We can see that the required number of samples for successful estimation is linear in r, predicted by (8)
Performance in noisy case. Figure 5) shows the relative error of the learned model by Algorithm from noisy measurements when r changes. N 1000, K 10, and d 300. The relative error is linear vr, as predicted by (9). Moreover, the relative error is proportional to the noise level [E]-
5.2 IMP FOR FINDING WINNING TICKETS
Here we implement the IMP algorithm to obtain pruned networks on both synthetic data and real data. Figure the test performance of pruned network synthetic data with different sample sizes. Here the ground-truth network model, K 5, d = 100, and r/d = 20%. The noise level a/ E, = 10 One observation is that for a fixed sample size N greater than 100, the test error decreases the number of remaining parameters decreases. This verifies that the IMP algorithm indeed prunes the network properly. It also shows that the leamned model improves the pruning progresses, verifying theoretical result in
"The code is downloaded from http:////hhhcoooooaaaaaaaaaaaaae
8

---

Under review conference paper at ICLR 2021
10
Kuesher of Samples (N)
550
Relatve ettor
10
450
350
10:
150
10
10
50
30
70
.1,, -00
-Q-
wit"
- dE -00"
- .n
Figure 4: Sample complexity when changes Figure 5: Relative error against vF different noise level
Theorem that the difference of the learned model from the ground-trute model decreases the number of remaining weights decreases. The second observation is that the test eπтоr decreases as N increases for any fixed number of remaining parameters. This verifies our result in Theorem 2 that the difference the learned model from the ground-truth model decreases the number of training samples increases. When the network pruned significantly such that the percentage of reaming parameters less than the ground-truth 20%, the pruned network cannot explain the data properly, and thus the test enror is large for all N. When the number samples is too small,
100, the test error always large, because does not meet the sample complexity requirement for estimating the sparse model even though the network is properly pruned.
Figure shows the performance of the IMP algorithm on MNIST dataset using Lenet5 architecture. The percentage of weights to be pruned after each cycle is 20%, and other parameters are set default values. Although not as obvious as the results on synthetic data, we still observe the same phenomenon of the performance when pruning progresses. That is, the test accuracy first increases when we properly prune the network (e.g., the case of N 20000), indicating the effectiveness of proper pruning. By contrast, the test accuracy drops the network is overly pruned.
10
Best BestTest Test A Accurey
Test emror
0.9
0.99
10
0.980
0.8
0.97
2
0.7
0.96
0.95
10
100
40
20
100
60
40
20
0.6
100
80
60
40
20
Percentage of remaining parameters (%)
Percentage of remaining parameters (%)
N=100 - -N=150 N=200
N=10000
+ N=20000 --- N=30000
- N=40000)
N=250 -B N=300 N=350
Figure 6:
Test error of pruned models on the syn-
Figure 7: Test accuracy of pruned models on MNIST dataset
thetic dataset
6 CONCLUSIONS
This paper provides the first theoretical analysis of learning one-hidden-layer sparse 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 learning algorithm, and the accuracy of the learned model. We also provide extensive numerical validations of theoretical findings. One desired future work will be generalizing our theoretical analysis to the scenario network pruning on multi-layer neural networks.
9

---

Under review conference paper at ICLR 2021
REFERENCES
Sanjeev Arora, Rong Ge. Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedingy of Machine Leurn- ing Research, pp. 263, StockholmsmAAssan. Stockholm Sweden, 10-15 Jul 2018. PMLR. URL
html
Rajendra Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In Proceedings of the 34th International Conference on Machine Learning-Volure 70, pp. 605-614. JMLR. org, 2017.
Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Zhangyang Wang, and Michael Carbin. The lottery ticket hypothesis for pre-trained bert networks. arXiv preprint vrXiv:2007.12223, 2020a.
Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Zhangyang Wang, and Michael Carbin. The lottery ticket hypothesis for pre-trained bert networks. arXiv preprint urXiv:2007,1222:: 2020b.
Xin Dong, Shangyu Chen, and Sinno Pan. Learning prune deep neural networks via layer-wise optimal brain surgeon. In Advances in Neural Information Processing Systems, pp. 4857-4867, 2017.
Simon Du, Jason D Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learns one-hidden-layer cnn: Don't be afraid of spurious local minima. In International Conference on Machine Learning, pp. 1338-1347, 2018.
Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. International Conference on Machine Learning, 2020.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neu- ral networks. In International Conference on Learning Representations, 2019. URL https:// openreview net/ met//ooummme (oorummid=rrJ--aar
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Stabilizing the lottery ticket hypothesis. arXiv preprint 10Xiv:1903001611 2019a.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. arXiv preprint arXiv: arXiv: 1912.0561, 2019b.
Haoyu Fu, Yuejie Chi, and Yingbin Liang. Guaranteed recovery of one-hidden-layer neural networks via cross entropy. arXiv preprint arXiv: 1802.0663,, 2018
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient
neural network. In Advances in neural information processing systems, pp. 1135-1143 143, 2015.
Babak Hassibi and David G Stork. Second order derivatives for network pruning: Optimal brain surgeon. In Advances in neural information processing systems, pp. 164-171, 1993.
Hengyuan Hu, Rui Peng. Yu-Wing Tai, and Chi-Keung Tang. Network trimming: A data-driven neuron pruning approach towards efficient deep architectures. arXiv preprint arXiv: 1607.03000 2016.
Volodymyr Kuleshov, Arun Chaganty, and Percy Liang. Tensor factorization via matrix factorization. In Artificial Intelligence and Statistics, pp. 507-516, 2015.
10

---

Under review conference paper at ICLR 2021
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied document recognition. Proceedings of the IEEE, 86(11):2278-2) 222222244,,, 1998.
Yann LeCun, John $ Denker, and Sara A Solla. Optimal brain damage. In Advances in neural information processing systems, pp. 598-605, 1990.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. In International Conference on Learning Representations, 2018.
Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir. On the computational efficiency of training neural networks. In Advances in neural information processing systems, pp. 855-863, 2014.
Eran Malach, Gilad Yehudai, Shai Shalev-Shwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning all you need. arXiv preprint arXiv:2002.00585, 2020.
Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational dropout sparsifies deep neural net- works. International Conference on Machine Learning, pp. 2498-2507, 2017.
Behnam Neyshabur. Towards learning convolutions from scratch. Advances in Neural Information Process- ing Systems, 33, 2020.
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari. What's hidden a randomly weighted neural network? In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11893 11902, 2020.
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. In International Conference on Learning Representations, 2019.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International Conference on Machine Learning, pp. 4430-4438, 2018.
Ohad Shamir. Distribation-specific hardness of learning neural networks. The Journal of Machine Learning Research, 19()):135-1116) 2018.
Mahdi Soltamolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization land- scape of over woer-paameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2): 742-769, 2018.
Suraj Srinivas and R Venkatesh Babu. Data-free parameter pruning for deep neural networks. arXiv preprint 1077v:1507.06114 2015.
Yuandong Tian. An analytical formula of population gradient for two-layered relu network and its applica- tions in convergence and critical point analysis. In Proceedings of the 34th International Conference on Machine Learning- -Volume 70, pp. 1440--3415 JMLR. org, 2017.
Joel Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational math- ematics, 12(4):399-434, 2012.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint 1rXiv:1011.3027, 2010.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference Learning Representations, 2019.
11

---

Under review conference paper at ICLR 2021
Tien-Ju Yang. Yu-Hsin Chen, and Vivienne Sze. Designing energy-efficiiet convolutional neural networks using energy-aware pruning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5687-5695 2017.
Gilad Ychudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. In Advances in Neural Information Processing Systems, pp. 6594-6604, 2019.
Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang. Xiaohan Chen, Richard G Baraniuk, Zhangyang Wang, and Yingyan Lin. Drawing early-bird tickets: Toward more efficient training of deep networks. International Conference on Learning Representations, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: /6/ 1.03530, 2016.
Shuai Zhang, Meng Wang, Sijia Liu, Pin-Yu Chen, and Jinjun Xiong. Guaranteed convergence of train- ing convolutional neural networks via accelerated gradient descent. In 2020 54th Annual Conference on Information Sciences and Systems (CISS), 2020a. URL 1tt.:11.1199111//////
2020.
1570627111
Shuai Zhang, Meng Wang, Sijia Liu, Pin-Yu Chen, and Jinjun Xiong, Fast learning of graph neural networks with guaranteed
httpiiiabiiit.ooooeiiideeeeeeee case. In 2020 International Conference on Machine Learming (ICML), 2020b.
Shuai Zhang, Meng Wang, Sijia Liu, Pun-Yu Chen, and Jinjun Xiong. Learning one-hidden-layer convo- lutional neural networks via accelerated gradient descent with generalizability guarantees. submitted to IEEE Transactions on Neural Networks and Learning Systems, 2020c.
Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit S Dhillon. Recovery guarantees for one- hidden-layer neural networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 4140-4149. JMLR. org, https://axxiv.orr/bss///000 wot../////..///7.003077/.55 2017.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. In Advances in Neural Information Processing Systems 32, pp. 3597-3607. 2019.
Wenda Zhou, Victor Veitch, Morgane Austem, Ryan P Adams, and Peter Orbanz. Non-vacuous generaliza- tion bounds at the imagenet scale: a pac-baycsian compression approach. In International Conference on Learning Representations, 2018.
12


Reviews:
[{"review_id": "cxCBwJUE9zz", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper analyzes the geometric structure of the objective function for a sparse one hidden layer neural net, and has a novel theorem on the convergence rate of the algorithm that recovers the weights in the one hidden layer neural net. From the perspective of sample complexity, namely how many samples are needed to have the whole recovery of the weights in the neural net, it is established that a sparse one hidden layer neural net usually requires fewer samples than a fully connected counterpart. The paper uses many simulations to support the theoretical results. The sparse neural net can represent the winning ticket for the lottery ticket hypothesis, and the sample complexity explains why the winning ticket has better performance. The paper seems the first work to focus on the weights recovery of sparse neural networks and provides useful guarantees with important insights, and the paper should be distributed to other researchers.\n\nAlthough the paper has many contributions and should be worth distributed to other researchers, the paper appears to be just below the threshold for acceptance to the ICLR conference. Therefore, I am afraid I might not recommend to accept the paper in this current form.\n\n1. Frankly, the technical novelty over the reference Zhong 2017 (Recovery guarantees for one-hidden-layer neural networks) seems not fully clarified. While it is accepted that this work has the sparsity $r$ and proves a tighter bound than Zhong 2017, it seems not fully clarified what technical novelty or key breakthrough are directly due to the sparsity setting in this paper, compared with the approach that Zhong 2017 took. The authors should highlight key technical differences in the proof due to the sparsity setting, to make it more convincing about the novelty of this paper.\n2. The paper only explains why a sparse neural net should train well with fewer examples than fully connected counterpart. The observation has its own merit. To my understanding, the paper starts from the assumption that the neural net to be learned is sparse – however, this could not be always correct for the lottery ticket problem. Thus, the assumption seems not always plausible for real applications of the lottery ticket hypothesis, and it would be useful if there can be examples of sparse neural networks that come naturally for some problem.\n3. Here is a question for the authors to confirm. Although the work is on sparse neural networks, the sparsity $r<<d$ is not assumed in Theorem 1 and 2, correct? Even if $r=d$, we still have the theorems valid? Please feel free to let me know if I do not understand well.", "extra_scores": {}, "extra_text": {}}, {"review_id": "OaK82EPOM-R", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of review:\n\nThis paper provides recovery guarantees for learning one-hidden-layer neural networks with sparse ground truth weights, given an isotropic Gaussian input distribution. The main result shows local convexity guarantees near the ground truth. Provided that a mask of the sparsity pattern is already known, this paper extends the tensor initialization approach of Zhong et al'17 to show a convergence guarantee for learning the sparse neural network. Simulations validate the local\n\nSetting:\n\nThis paper focuses on learning a one-hidden-layer neural network, where the weight matrix of the hidden layer is sparse, given input samples from an isotropic Gaussian distribution. \n\nResults:\n\n(i) The first result is that within a small vicinity of the ground truth weight matrix, the standard mean squared loss for learning the neural network is convex.\n\n(ii) The second result shows how to learn the ground truth weight matrix, by extending the tensor initialization approach in Zhong et al'17.\n\n(iii) Numerical results are provided to validate the above two theoretical results.\n\nPros:\n\n- The sample size requirement of both result (i) and (ii) growly proportionally to the sparsity of the ground truth matrix, as opposed to the size of the matrix. This result is particularly interesting in light of recent empirical results about network pruning and learning sparse ConvNets (Neyshabur'20).\n\nCons:\n\n- The authors prove the above results by adapting the proof of Zhong et al'17. In fact, since the input distribution is isotropic, standard concentration results apply whether or not the ground truth matrix is sparse. Therefore, it is unclear to the reviewer whether this result is as novel as the authors claim in the introduction.\n\n- The learning algorithm assumes knowledge of the sparsity mask. This seems like a strong assumption. Isn't the point of IMP to find this sparsity mask? Understanding how to find this sparsity mask seems like a more important question, but this is not discussed at all in this paper.\n\nWriting:\n\nOverall, this paper is easy to follow. The quality of writing is marginally acceptable. Please find several detailed comments below.\n\n- P1, \"the theoretical justification of winning tickets are remains elusive expect for a few recent works\" -> remove \"are\", replace \"expect\" with except\n\n- P4: \"an one-hidden-layer neural network\" -> a one-hidden-layer neural network\n\n- P5: here you say that $\\varepsilon_1 = \\Theta(\\sqrt r)$, but $r > 1$ and $\\varepsilon_1 < 1$. Please clarify.\n\n- P5: regarding the convergence for the vanilla GD algorithm. Please add a reference to this claim.\n\n- P5: \"accurate estimate\" -> replace \"estimate\" with estimation", "extra_scores": {}, "extra_text": {}}, {"review_id": "Hpy-7uD2wie", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper investigates the theoretical evidence behind improved generalization of the winning lottery tickets. More precisely authors characterize the testing error of a pruned network that is then trained using AGD. Under relatively reasonable assumptions, they manage to show an improved generalization bound for a properly pruned network over the full network.\n\n####################################################################### \npros: \n\nThis is one of the first works to provide theoretical guarantees for winning lottery tickets under the one-hidden-layer sparse neural network model. The objective function being highly non-convex in general, authors rely on local convexity of the latter objective function around the ground truth. Hence Given a good initialization, they managed to show that AGD achieves a good performance after a certain number of steps. Numerical experiments are interesting and complement pretty well the theory of the paper. \n\n####################################################################### \ncons/questions: \n\n* Line 6 page 5, you say that the radius of the convex ball is $\\Theta(1) - \\Theta(\\sqrt{r})$. How is that even positive as $r$ grows? The same comment also holds for your comment after Lemma 1.  \n\n*  Using local convexity, which is a uniform property, you should be able to prove your main result based on the whole training data instead of sample splitting. I don't see why you have only managed to show your result under sample splitting which is less interesting in my opinion.\n\n* The hypothesis of a sparse ground model where you are given the true corresponding support is too restrictive. It would have been very interesting to apply a variant of IHT to your proposed algorithm. I believe your results should hold under relatively similar conditions. I strongly think proving your result without prior knowledge of the true support would make the present paper stronger and would avoid having trivial follow-up works that may take more credit than yours.\n\n#######################################################################\n Score:\n\nThis paper is well written and the proofs seem sound to me. Overall, I think the present paper is marginally above the acceptance threshold because of the reasons I explain above. I am willing to revise my score if the authors give constructive feedback to my concerns. \n\nComments: \n\n* In Theorem 7, it would be good to precise that your initialization is independent from the data you use for your AGD.", "extra_scores": {}, "extra_text": {}}, {"review_id": "1XAeiamIlJe", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the lottery ticket hypothesis, which says that there is an underlying sub-network (lottery ticket) in a neural network such that if we train it, we will obtain a better test accuracy compared to the original network. The authors develop a theoretical validation of the improved generalization error of the lottery ticket. Similar to many theoretical results for neural networks, several assumptions have been made. For example, it is assumed that the underlying function, which we try to learn, can be entirely captured by a sparse neural network. This assumption indicates that for some underlying sub-graph, we can learn with zero generalization error. They provide empirical validation for their results as well.\n\nThe authors consider a significant problem. Pruning techniques allow us to enjoy high accuracy while reducing neural networks' memory and computational running time. These techniques have been studied for a long time, but mostly from an empirical perspective. I believe understanding the pruning problem's theoretical aspects will help us develop better algorithms for pruning as well.\n\nThe results are clearly explained, and the paper is well-written.\n\nComments:\n\nIn empirical cases, the pruned network's initialization is often set to the weights obtained in the training of the more extensive network. Is this technique used in your comparisons in the numerical evaluation?\n\nIt is assumed that the covariates x_i's are coming from a Gaussian distribution, implying that the label y_i is a mixture of truncated Gaussians. (before adding noise). While this assumption has been made in previous works, the role of this assumption is not well-explained. \n\nI am not sure whether the underlying assumption trivialized the problem. It is assumed that the function f, which we try to learn, can be captured by a sparse one-hidden-layer neural network. This sparse sub-network would essentially be the lottery-ticket of the fully connected network. Then it is claimed that if we know the structure of this sparse sub-network (i.e., known mask matrix M), then it means we are learning in a lower dimension of parameters compared to the case of a complete network. Thus, it is not surprising to see that the SGD algorithm converges faster. In other words, by knowing M, we already set a large portion of parameters to their optimal values. Thus, it is easier to find the optimal solution to the minimization problem. \n\n\nThe ultimate goal of the pruning problem is to get the sub-structure and train it efficiently. Does your result affect how one could potentially improve the current pruning techniques (such as IMP)? Or can we say anything about the algorithm's performance when a large fraction of the sub-network is picked correctly?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Even though the authors revised the problem formulation, the paper seems not ready for publication. The assumptions are still too strong (The learning algorithm assumes knowledge of the sparsity mask). The proof technique also heavily relies on Zhong et al'17 without properly highlighting the difference. 
Decision: Reject