Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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). 

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. 
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_title: null

final_score: rating: 3: Clear rejection
review_content: 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.

To 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.
main_review: Strength
1. The paper analyzes the influence of the number of remaining parameters in pruned subnetworks and derives the required number of samples for successful convergence.

2. The authors conduct the theoretical analysis and justification for improved generalization error of winning ticket in the LTH.

3. The extensive evaluation on both synthetic and real datasets demonstrates the effectiveness of the proposed approach for neural network pruning.

Weakness
1. 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.

2. 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".

3. 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.

4. It would be nice to conduct the experiments with the SOTA LTH and neural network pruning algorithms.

-------------------

Post-rebuttal update:

Thanks 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.

In 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.

Local 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).
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_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.

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. 

General opinion:
The 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.

Pros:
- 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.
- 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.
- 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). 
- 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. 
- Experiments on real datasets are included.

Cons:
- Analysis is limited to gaussian input data. I believe this is the main/most unrealistic limitation of the theoretical analysis. 
- 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).

Questions:
- 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?).
- 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). 
- 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). 

Minor Comments:
- 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 
- 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.

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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: Pros:

This 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.  

Cons:

 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).
For 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. 

Minor comments:

Many 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.

limitations_and_societal_impact: N/A
review_title: null

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)