Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes utilizing the existing "lottery ticket" result with the re-initialization method. This work has some novelty since doing re-initialization is not studied in other papers.


main_review: Questions: (1) The performance is actually no better than the previous method, for eg. ResNet18 on Cifar10 as compared to https://openreview.net/pdf?id=U_mat0b9iv. As a result, the performance gain by IteRand as compared to edge-popup is not clear. (2) For Theorem 4.1, the value of R is chosen unrealistically. Even for l=10, d=1000, R needs to be at least 10k/\epsilon. (3) The technical difficulty is not clear to me as compared to previous proofs. This should be emphasized. (4) What happens if the method is applied to NLP problems?

-----------------------After rebuttal----------------------------
The authors resolved my concern so that I increased my score.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a new technique to reduce the network width required for pruning based algorithms. In particular, instead of starting from a wider network and then pruning weights to train the network, the paper proposes that pruned neurons can be resampled with random weights. Hence, instead of having extra weights in the form of extra width from the beginning, the new technique brings in new weights every time some of the existing weights are pruned. The motivation behind this is to reduce the memory footprint of the network before the pruning. 

The idea and the empirical results are good, however, the theoretical result could be improved significantly.
main_review: The new idea that pruned weights can be resampled seems very intuitive and effective. The empirical results suggest that this indeed outperforms existing pruning techniques. However, the authors should provide more empirical evidence like actual training time, comparison with state-of-the-art (SGD+pruning) techniques like the lottery ticket hypothesis, and the actual number of times weights were resampled.

The theoretical result does not provide a strong support for the technique. In particular, even though the result is purely existential, the requirement on the number of re-samplings, $R$, is huge. It is proportional to the network depth and width. This seems to suggest that the procedure might not be efficient (in terms of computational time) for training large networks, since each resampling would need at least one complete iteration. 

The paper is well written and easy to understand.

Overall, the proposed technique is novel and can improve the state-of-the-art in pruning techniques.
limitations_and_societal_impact: 1. Please compare your results with techniques that use both SGD and pruning iteratively. Even though (SGD+pruning) might outperform purely pruning based techniques, like the one proposed in this paper, it is still a necessary evaluation that should be included in the paper.
2. Please provide the comparisons for the actual training time (in seconds) for different techniques.
3. Please provide details on the number of re-samplings that happened during the training.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a memory-efficient approach for \textit{weight-pruning optimization}, which suffers from a much larger memory cost than standard \textit{weight optimization}. 

The proposed approach, weight-pruning with iterative randomization (IteRand), decreases the required network width by introducing pruned weights randomization at each iteration. The author theoretically shows that, with sufficient randomizing operations, the width can be reduced to constant factors of that of a standard network trained by weight-optimization. 

The empirical experiments demonstrate IteRand achieves better performance than existing weight-pruning optimization methods under the same memory budget. 
main_review: **Reason to accept**
- The paper is well-organized and finely written.
- The limitations of the existing works are thoroughly discussed and the paper is clearly motivated.
- The authors both theoretically prove and empirically verify that IteRand can effectively reduce memory consumption and increase the complexity of the network.

**Reason to reject & Questions**
- Section 5.1&5.2: The gain of IteRand seems to decreases as the network size scales up (ResNet34 > ResNet50 > ResNet101 in Figure 3(a), and the same phenomenon in Figure 2.). I wonder how IteRand performs in settings where the memory constraint is an actual consideration (e.g., when training a model with hundreds of million parameters). 
- How much is the additional computational cost of IteRand over edge-popup? 
- I wonder if the authors can show some empirical results on 1) given the same size of $f(x)$, what is the width required for $g(x)$ for IteRand and for EdgePop to achieve the same performance? This may help understand the percentage of memory that is actually saved. 2) the performance under different $p$s to verify the consistency of the improvement.

Disclaimer: I am not an expert in theoretical proofs. All my evaluation assumes the correctness of Theorem 4.1 and is subject to change if the proof turns out to be erroneous.
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work proposes an improved method to find a performative subnetwork within a randomly weighted neural network. In contrast to prior work, a fraction of unused weights are periodically reset. This is a novel idea with empirical improvements and theoretical justification.
main_review: Overall the paper is clear to follow and enjoyable to read. The method is interesting, well motivated, and there are empirical gains. A few suggestions which could improve quality:

1) Additional empirical results would strengthen the paper's message. For instance, this work is introducing two new hyperparameters (r and K_per), though there is only an ablation on one of these parameters. How did the authors choose K_per? Moreover, edge-popup could be added to Figure 3 -- it does seem as though this work performs better.

2) There are a couple points where clarity in limitations could be improved. For instance, is IteRand just has an SC initialization but is no longer SC by the end of training. This is a shortcoming as weights can no longer be encoded with in binary. Moreover, with edge-popup or Zhou et al., a single random seed can be stored which generates all the weights, it seems this is no longer the case with IteRand.

Minor comments:
- Line 32-33 I believe Pensia et al. show that their theoretical result holds with log overaparam and not that this is required emperically.

-- Added --

I acknowledge the response and have raised my score to 7
limitations_and_societal_impact: Authors adequately addressed the limitations and potential negative societal impact.
review_title: null

Meta-review: The paper presents a new algorithm for learning by pruning. In the original work by Ramanujan et al. the random weights of a network could be pruned away so that the resulting network could achieve arbitrary accuracy for a given task, at the cost of slight overparameterization. The authors in the current paper show that the performance of such learning by pruning schemes can be improved by further rerandomizing the weights at consequent pruning iterations. This results in a reduced overaparemeterization to achieve the same accuracy compared to past results. The results are novel, and interesting with regards to the related literature. The reviewers have posted several points that the work can be improved, and all are addressed/can be addressed by the final version of the paper. 
Decision: Accept (Spotlight)