Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: The paper studies if LT exists in ER-like connected neural networks. Theoretical and empirical results are provided.
strength_and_weaknesses: +: 
The problem looks interesting for purely theoretical purposes. 
The theoretical results look solid though I couldn't check the proof. 

-: 
The practical motivation is unclear. Why would one stick with a fixed source sparse network that is randomly drawn? One can probably do much better by not having to stick with a fixed sparsity pattern. 

The weak LT statement is proved with a very strong trainability assumption. Such an assumption would also imply the existence of weak LTs in the dense case too, I guess. 

The theoretical contribution is not clear. Does the ER-version of subset sum result (Lemma 2.1) directly imply Theorem 2.2 using the same proof flow of Pensia et al., 2020? 

Moreover, I am not sure if the ER-version of subset sum result interesting/non-trivial. Maybe I am misunderstood. Since $\frac{1}{\log{1/(1-p)}} \approx 1/p$ when $p$ is small, isn't it kinda obvious that you need $1/p$ expansion factor to solve the subset sum problem? 

Or more seriously, why do we even need a separate proof for Lemma 2.1? With probability $1-\delta_1$, we can show that there will be $np(1-\epsilon_1)$ non-zero terms.  Since $M$ and $X$'s are independent, within those non-zero terms, you can solve the $\epsilon_2$-subset sum problem with probability $1-\delta_2$. By combining these two, we can easily get Lemma 2.1. Please correct me if I am wrong.
clarity,_quality,_novelty_and_reproducibility: see my comments above.
summary_of_the_review: see my comments above.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proves that the Strong Lottery Ticket Hypothesis holds for FC Neural Networks and CNNs which are initialized as Erdos-Renyi (ER) graphs. It extends on the proofs by *Pensia et al.* and *Burkholz et al.* to show that logarithmic overparameterization (and an additional $\log$ factor that depends on the sparsity of the ER initialization) is sufficient to approximate any target network by pruning.
- They also claim to prove a result for the weak LTH but the assumption makes it fairly vaccuous.
- They run some experiments in the vein of Pensia et al. on CIFAR-10, CIFAR-100 and TinyImagenet. They also show that rewiring edges of a pruned network can improve the performance of the final mask significantly.
strength_and_weaknesses: **Strengths:**
- The premise is very interesting as they claim to prove a result about the remarkable performance of random pruning.
- As far as I am aware, a theoretical justification of the weak LTH does not exist in the literature. The authors prove a result showing this, although the assumption makes it quite unsatisfactory.
- The paper is well written and fairly easy to understand.

**Weaknesses:**
1. The paper makes it seem like they are proving a result explaining the remarkable performance of random pruning, but in reality they do not. The theorem only shows that you can further prune a random subnetwork, given sufficient overparameterization. While this is true, I don't find this particulary interesting or surprising.
    -  In the abstract as well as Section 1, they state "We offer a theoretical explanation of how such ER masks can approximate arbitrary target networks if..." - this is simply untrue. They show that within an ER mask, there exists some sort of *sub-mask* which allows you to approximate abirtrary target networks.
    -  The results of Su et al., Liu et al. and Frankle et al. show that random pruning **alone** is sufficient to reach competitive results. They do not further prune the random masks. Therefore, this theory does not imply those results whatsover.
    -  The phrasing of the results is accurate in the contributions section where they state that ER networks contain LTs with high probability. I agree with this statement although I am not sure if it is particulary interesting or surprising.
    -  The additional $\log(1/(1-p))$ factor is fairly obvious if you are familiar with the strong LTH literature. It is merely allowing for larger overparameterization to account for the missing edges from the ER mask initialization.

3. The assumption in the result about the weak LTH is far too strong. It almost assumes the theorem that they are trying to prove. I think this makes the result fairly vaccuous.
    - **Assumption 2.3** assumes that an ER network with layerwise density $p$ is trainable by SGD with standard weight initialization. This is essentially the weak LTH for random pruning. This is the result I would have liked to see proved. But it is just merely assumed. Proving the weak LTH from this seems extremely trivial.
    - They justify this assumption since it is observed in practice from works like Su et al., Ma et al. etc. However, they use it to prove a statement that supposedly explains the results from this very work. This circular reasoning seems incorrect and is akin to assuming the statement they are trying to prove.


5. I understand that the LTH literature has grown quite fast, but Section 1 is missing quite a few citations and is unfair to a few references as well.
    - The literature survey on LTH and pruning algorithms is missing Renda et al., (Comparing Rewinding and fine-tuning in Neural Network Pruning), Gale et al. (The State of Sparsity in Deep Neural Networks), Savarese et al. (Winning the Lottery with Continuous Sparsification).
    - The section on Strong LTH is again missing a few papers: Diffenderfer et al. (Multi-Prize Lottery Ticket Hypothesis), Sreenivasan et al. (Finding Nearly Everything within Random Binary Networks).
    - In Section 1, Tanaka et al. is listed under algorithms that have expensive pruning-retraining iterations but if I'm not mistaken, SynFlow uses a constant number of iterations to identify the mask at initialization. Therefore, it is nearly a single-shot pruning method.

6. There are some minor issues with claims made and terminology used in the paper.
    - It is mentioned repeatedly that strong LTs are also weak LTs. This is a somewhat imprecise statement. If you assume that weak LTs need to be trainable to high accuracy, then several strong LTs do not satisfy this requirement. Strong LTs can approximate any target network, but they do not provide any guarantees on similar trainability as the target networks. I think the literature has moved quickly and the strong LT term has caught on, but I think it should be used more carefully.
    - In Section 1.1, it is stated that the best performing WLTs are still obtained by expensive iterative pruning methods like IMP. This is not necessarily true. (See Sreenivasan et al. Rare Gems: Finding Lottery Tickets at Initialization)
    - In Section 1.1 they state that "we show that ER masks are competitive for various choices of layerwise sparsity ratios": But the results involve finding masks within ER masks. The final pruned subnetwork is not an ER graph.
    - They repeatedly claim that the theorems identify a lower bound on the width of the ER source network for which they can show existence. While this is true, it is really an upper bound on the width of the source network to guarantee existence since we have not yet proved a matching lower bound. Theorem 2.7 is indeed a lower bound.

7. Appendix A.1 Flow Preservation:
    - How often does flow preservation need to be done? Is this at every gradient step? This could get quite expensive since it needs to check every weight in the network.

clarity,_quality,_novelty_and_reproducibility: **Clarity, Quality, Novelty:**
- The paper is well written and easy to understand.
- As I mentioned above, some of the claims are exaggerated in the text, so if they are modified, I think it would be a reasonable contribution.
- While the work relies heavily on past works in the Strong LTH literature, the application of the proof technique to ER graphs is novel.
summary_of_the_review: I do not think the paper in its current state should be accepted as several claims made are exaggerated and imprecise. However, if the literature survey is updated, claims modified and limitations more clearly described, I think it would be a reasonable contribution. I would be happy to change my mind if my concerns are addressed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides a theoretical analysis that ER masks can approximate arbitrary target networks if they are wider by a factor of 1/log(1/s), where s denotes the sparsity ratio. The paper prove that ER randomly initialized network contains strong lottery tickets, and also prove the existing of weak lottery tickets that require a lower degree of overparameterization than strong lottery tickets. Additionally, a lower bound on overparameterization in ER networks that illustrates the limits of ER masks. The authors verify their theory on multiple DL applications like VGG on CIFAR10.
strength_and_weaknesses: **Strength**
* This paper gives solid theoretical justification on ER random network, the theory partially substantiates why some recent works on sparse networks that use ER initialization is better in practice, like (Evci et al., 2020a). I did not read all the proof, but the main claim in the paper looks correct to me.
* While I personally am not familiar with the literature in this line of work, the theory looks interesting and novel to me.

**Weakness**
* It's likely that I missed something in the literature, but it is unclear to me what the definitions for SLT and WLT are. I'd encourage the authors to clearly identify this in the revision.
* While I appreciate the authors for giving theoretical justification to ER networks, it's still unclear to me how the theory connects to the current success. Take (Evci et al., 2020a), the main success in RigL paper is that the rewiring of weight parameters is signaled by gradients instead of random variables. The authors mentioned in their contributions that theoretical support is provided on targeted rewiring, but I'm not sure how the theory given in Theorem 2.7 is related to (Evci et al., 2020a).
* The majority of the experiments are done to verify the ER trainable assumption in real-world training applications. On the other hand, I think it'd be interesting to also give evidence on how ER network contains SLT/WLT on toy examples.

clarity,_quality,_novelty_and_reproducibility: Please see above.
summary_of_the_review: Overall I think this is a good paper, because it provides detailed theoretical justification to ER networks. I'd appreciate if the authors could provide follow-up explanations of how the provided theory relates to (Evci et al., 2020a).
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper claims that randomly generated pruning masks can create surprisingly effective sparse neural network models, and can often compete with dense architectures. These random super masks can be initially set up with small computational overhead, and can theoretically approximate any target network with a logarithmic factor in the inverse sparsity. 

There are two critical reviewers, one of which has significantly engaged with the authors during the rebuttal. They note that despite the paper being well-written, it is unclear if the ER-version of subset sum result is interesting or non-trivial. Several claims are perhaps exaggerated and imprecise (the authors did work to improve it). Perhaps most importantly the assumption in the result about the Weak LTH is far too strong. 

This can perhaps be a reasonable contribution for a future venue if the claims and limitations are clarified, and the text is significantly reworded to a point that is beyond this current format.
justification_for_why_not_higher_score:  Despite the paper being well-written, the reviewers and I are uncertain about the theoretical contribution of this work in light of its assumptions, and practical considerations.
Decision: Reject