Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

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

The results are clearly explained, and the paper is well-written.

Comments:

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

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

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


The 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?

review_title: Review4

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary of review:

This 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

Setting:

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

Results:

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

(ii) The second result shows how to learn the ground truth weight matrix, by extending the tensor initialization approach in Zhong et al'17.

(iii) Numerical results are provided to validate the above two theoretical results.

Pros:

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

Cons:

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

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

Writing:

Overall, this paper is easy to follow. The quality of writing is marginally acceptable. Please find several detailed comments below.

- P1, "the theoretical justification of winning tickets are remains elusive expect for a few recent works" -> remove "are", replace "expect" with except

- P4: "an one-hidden-layer neural network" -> a one-hidden-layer neural network

- P5: here you say that $\varepsilon_1 = \Theta(\sqrt r)$, but $r > 1$ and $\varepsilon_1 < 1$. Please clarify.

- P5: regarding the convergence for the vanilla GD algorithm. Please add a reference to this claim.

- P5: "accurate estimate" -> replace "estimate" with estimation
review_title: Theoretical results for learning a one-hidden-layer neural network with sparse ground truth weights given a Gaussian input distribution

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

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

1. 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.
2. 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.
3. 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.
review_title: review

final_score: rating: 7: Good paper, accept
review_content: Summary:

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

####################################################################### 
pros: 

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

####################################################################### 
cons/questions: 

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

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

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

#######################################################################
 Score:

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

Comments: 

* In Theorem 7, it would be good to precise that your initialization is independent from the data you use for your AGD.
review_title: Review of Why Lottery Ticket Wins? A Theoretical Perspective of Sample Complexity on Sparse Neural Networks

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