Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper:  This paper studies the key problem in deep learning: why pruning can help generalization. They consider a one-layer (I will explain why I call it one layer) neural network with ReLU activation, and assume certain structure of input data and labels. They model the pruning operator as the element wised multiplication between weight matrices and masking matrices. They show that, when pruning ratio is lower than some threshold, it helps generalization; while if the ratio is higher than some threshold, it will hurt generalization. Their proof technique is to study the correlations between model weights and input data noise. If the pruning ratio is lower than some threshold, the pruning will reduce the variance of the noise and hence improve the generalization. When the ratio is higher than some threshold, it will constrain the model capacity such that the prediction will be bounded (less than 1), and hence the generalization is lower bounded by a constant as well.

strength_and_weaknesses: This is the first work towards understanding the generalization of pruned neural networks trained by gradient descent. Their results are interesting: there is a phase transition of pruning ratio. When pruning ratio is lower than some threshold, it helps generalization; while if the ratio is higher than some threshold, it will hurt generalization, which matches our intuition. Their proof is based on assuming sparse data with Gaussian noise, and controlling the correlations between Gaussian random initialized weights and noise. A small pruning ratio provides some regularization-like benefits by reducing the variance of the noise, while the more aggressive pruning will limit the prediction of the network below 1, i.e., $F(\tilde{\mathbf{W}},\mathbf{x}) < 1$, so the generalization will never be smaller than a threshold. The proof idea is interesting to me, and the results are also novel. 

Some issues:

1. The assumption on input data is way strong: the authors assume the input data is composed by basis vector concatenated with Gaussian noise, i.e., $\mathbf{x} = [\mathbf{e}_i, \boldsymbol{\xi}]$. I guess this data assumption follows recent work:
\emph{ Cao, Yuan, et al. "Benign Overfitting in Two-layer Convolutional Neural Networks." arXiv preprint arXiv:2202.06526 (2022).} However, Cao et al do not assume the deterministic part of the data is basis vector. 

2. The neural network structure is bit toy. Usually, for two layer ReLU network, we assume $f(\mathbf{x}) = \mathbf{a}^T \sigma (\mathbf{W}\mathbf{x})$, while in this paper's setting, the top layer is removed. Hence I cannot even call this model a ``two layer neural network''. Perhaps linear model with rectified output is more accurate. It is also surprising that here we only achieve $O(1/\epsilon)$ convergence of training loss, while it is well-known that even for deep neural network, the convergence rate is $O(\log (1/\epsilon))$ in overparameterized setting, or even under only mild overparameterization regime:

\emph{ Nguyen, Quynh. "On the proof of global convergence of gradient descent for deep relu networks with linear widths." International Conference on Machine Learning. PMLR, 2021.}


3. Technical question: in Lemma D.25, the key Lemma to prove generalization, the authors said that the correlation between output model and Gaussian noise: $\langle \tilde{\mathbf{w}}^*, \boldsymbol{\xi} \rangle$ satisfy Gaussian distribution. If $\tilde{\mathbf{w}}^*$ is a constant, it definitely holds. However, if my understanding is correct, output weight $\tilde{\mathbf{w}}^*$ is also a random variable, and the product of two Gaussian RVs is not necessarily Gaussian. So I am curious how the authors eliminate the randomness of $\tilde{\mathbf{w}}^*$? Or do we need to take expectation over $\tilde{\mathbf{w}}^*$ to make it constant?
 

4. Perhaps not extremely relevant but I think the following paper about Dropout should be cited:
Arora, Raman, et al. "Dropout: Explicit forms and capacity control." International Conference on Machine Learning. PMLR, 2021.

clarity,_quality,_novelty_and_reproducibility: Overall, the paper is well-written and easy to follow.
summary_of_the_review: In general, this is an interesting paper towards understanding how GD+pruning helps generalization, and it could inspire a line of follow-up works. However, as I mentioned in weakness part, the setup is way toy, even among the theory papers.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the effect of random pruning at initialization on the generalization of a neural network. The author theoretically shows that pruning of some two-layer convolutional neural networks under small initialization could improve their generalization if the probability of dropping a neural is mildly large, and could deteriorate the generalization if it is too large.
strength_and_weaknesses: Strength: The paper is mostly clear and the results are novel. The analysis of the convergence and generalization of training a pruned-at-initialization network is interesting and new. The analysis studies the neural network training under the so-called "active regime", which is more practically relevant.

Weakness: I think the theoretical results in the paper are great but I have some concerns about the way this paper is presenting it:

The assumption on the data distribution and the network structure is fairly restrictive. This paper studies the two-layer convolutional network but requires the size of the convolutional kernel to be exactly half of the input dimension and so is the stride so that the convolution layer outputs a 2d binary vector, and the two binary outputs can be viewed as the binary predictions of a linear classifier on the first half and the second of the data vector. Then the data distribution is carefully designed so that each data vector has either the first half as pure signal and the second half as noise or the other way around. Lastly, the weight for the output layer is sparse, binary, and fixed during training. 

I understand many of these assumptions are useful for the analysis (and I really think they are cleverly made) but most of them are impractical, making the theoretical results less relevant in interpreting the performance of a practical neural network trained under a real dataset, and this is shown in the numerical section that experiments on the real dataset cannot be well explained by the theorems in this paper.

Therefore, I think a more detailed explanation of why some assumptions are made about the data and network, together with remarks on how the theoretical results can be (or can be made in future work) relevant to practice is necessary for this paper, otherwise, the theoretical results can be misleading.
clarity,_quality,_novelty_and_reproducibility: The paper is mostly clear and the results are novel. 
summary_of_the_review: Strength: well-written, results are interesting and new;
Weakness: Restrictive assumptions without justification on their practical relevance.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper considered a classification task for overparameterized two-layer neural networks, where the network is randomly pruned according to different rates at the initialization and studied how different pruning fractions affect the model’s gradient descent dynamics and generalization. 

strength_and_weaknesses: Strength: 
The paper considered a classification task for overparameterized two-layer neural networks, where the network is randomly pruned according to different rates at the initialization. In this specific scenario, they theoretically prove that there exists a threshold on the pruning fraction such that pruning helps the neural network’s generalization. the generalization bound gets better as the pruning fraction gets larger.  Also for the overpruning there exists a relatively large pruning fraction such that the learned model yields poor generalization


Weakness:
1- Even though the theoretical result of the paper sounds interesting, they considered a very specific scenario and it is not clear this can be generalized to more complex models with different weight distributions.  

2-The experimental results are very limited and they do not fully support the theoretical results. It is not clear how the results in figure 2 mapped to the bound proposed in theory. The paper should show the simulation results vs the theoretical result to make it more clear.


3- Also the experimental result of the real dataset is not clear. How come the accuracy in y axis is 100%? They only show as the pruning ratio increases the accuracy drops. How do these figures show the claims and arguments made by theory?

clarity,_quality,_novelty_and_reproducibility: The paper provides generalization bound on random pruning for a specific model with some assumption on weight initialization. I understand these assumptions are required to provide such a theoretical bound but it is not clear how it can be extended in the existing model. 

summary_of_the_review: The paper theoretically showed that there exists a threshold on the pruning fraction such that pruning helps the neural network’s generalization and also there exists a relatively large pruning fraction such that the learned model yields poor generalization. Even though these results sound interesting it is not clear how their experimental results support such a theory.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper analyzes pruning for overparameterized two-layer neural networks. The setting is "pruning the second last layer" of a deep neural network, so they assume the input has the form of (x1, x2) \in R^{2d}, where x1 and x2 are either ue_i, or a random vector. In other words, the input has a specical form of "half one-hot, half random noise" form. Moreover, they assume the network structure has the form sigma(<w, x1>)+sigma(<w, x2>), which means the weight w is applied to both x1 and x2 simultaneously. There are a bunch of other assumptions described in condition 2.2, including number of classes, training samples, etc. 

Under these assumptions, the authors were able to prove interesting results on pruning the network. Specifically, they show that, after mild pruning, the generalization performance is increasing; after over pruning, the generalization performance is not better than random guess, but the training loss goes to 0. The nice thing about their analysis is, it is based on feature learning, instead of NTK analysis. In other words, they show the network learns the feature vector after mild pruning, and the network fails to learn the feature vector after over pruning. 

strength_and_weaknesses: Strength: 
This is a well organized and well written paper. I did not have enough time to read all the details in the appendix, but I did go through the theorem statement in the main paper, which looks reasonable to me. 
Pruning is pretty effective empirically, but as the authors mentioned in Section 3.2, if one only applies the "NTK analysis", it seems that pruning will only hurt. The nice thing about this paper is it uses the new technique called feature learning, and based on this technique, they can indeed show the effectiveness of pruning. 
Empirically, feature learning is a much more realistic setting, so I think such analysis is interesting, and can be seen as a nice theoretical support for pruning methods. 

Weakness:
The weakness of this paper, as well as many neural network theory papers, is the strong assumptions on the model. The assumptions on the input data and for the network structure look especially strange to me. However, given this is the first analysis for pruning, I guess that might be OK. It can be the first starting point for analyzing pruning methods. 
clarity,_quality,_novelty_and_reproducibility: Clarity: Good. It is a pretty technique paper, but the writing is overall fairly good. I enjoyed the reading. 

Quality: Good. I did not check all the proofs in the appendix, but I think this is a rigorous paper. 

Novelty: Good. I think theory analysis for pruning is interesting and important. 

Reproducibility: Not applicable. This is a theory paper, and all the proofs are included in the appendix. 
summary_of_the_review: This is an interesting theory paper of pruning for overparameterized two layer networks, with special assumptions on the input and network structure. The analysis is based on feature learning, which says with mild pruning, the network will still learn the feature signal but the noise signal will be reduced; with over pruning, the network is essentially learning the noise.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies the effect of random pruning at initialization on the generalization of a two-layer neural network. The paper claims to show that there is a phase transition of pruning ratio, such that mild pruning improves generalization while over pruning hurts it. The paper uses a feature learning approach to analyze the convergence and generalization of the pruned network.

The reviewers appreciate the novelty and interest of the topic, and the clarity and rigor of the writing and the proofs. However, they also raise several major concerns that prevent the paper from being accepted:

- The paper makes very strong and unrealistic assumptions on the data distribution and the network structure, which limit the applicability and relevance of the results. The data is assumed to be composed of half one-hot and half random noise vectors, and the network is assumed to apply the same weight to both halves of the input. These assumptions are not justified or motivated by any practical scenario, and they are not discussed in relation to existing work or real data. The paper should provide more explanation and evidence for why these assumptions are necessary and reasonable, and how they can be relaxed or generalized in future work.

- The paper does not provide sufficient empirical evidence to support the theoretical claims. The experiments on synthetic data are very limited and do not show how the theoretical bounds compare to the actual performance. The experiments on real data are unclear and do not demonstrate the phase transition of pruning ratio. The paper should show more comprehensive and convincing experiments that illustrate the main results and compare them with existing methods or baselines.

- The paper does not discuss the related work and the implications of the results in a broader context. The paper should cite and compare with other works on pruning, feature learning, and generalization, and discuss the limitations and extensions of the results. The paper should also explain how the results can inform the design and understanding of pruning methods for more complex and realistic models and data.

In summary, the paper has some interesting and novel aspects, but it also has many flaws and gaps that need to be addressed. The paper is not ready for publication in its current form, and it requires major revisions and improvements. Therefore, the paper is rejected.
justification_for_why_not_higher_score: The paper can not be accepted because it does not meet the standards of quality, novelty, and significance for ICLR. The paper does not convincingly demonstrate the validity and relevance of the results, and it does not provide enough empirical and theoretical support for the claims. The paper also does not engage with the existing literature and the broader implications of the work. The paper needs to address the reviewers' concerns and feedback, and to provide more rigorous and comprehensive analysis and experiments. The paper also needs to justify and motivate the assumptions and the setting, and to discuss the limitations and extensions of the work. The paper has the potential to be an interesting and important contribution, but it requires more work and refinement.
Decision: Reject