Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work analyzes the key factors or indicators behind the successful identification of winning tickets in Lottery Ticket Hypothesis (LTH). That is, the flatness of the trained models and the closeness of the trained weights to the initialization. The motivation is that finding winning tickets requires small learning rates. How large a learning rate we use is related to the above two indicators. Empirical results turn out to show that the flatness seems to be of less relevance because we can find winning tickets either way: (1) using a small learning rates, which leads to winning tickets with sharp minima; or (2) using a large learning with sharpness regularization, which leads to winning tickets with flat minima.

The authors then empirically verified that properly regularizing the distance between the trained weights and the initial weights helps to find winning tickets when using a large learning rate. And they provide a framework to analyze this from the PAC-Bayesian perspective by setting the prior mean as the initial weights. Then IMP can be interpreted as alternating between minimizing the training risk term and the KL term in PAC-Bayesian framework.
strengths_and_weaknesses: Strengths:

+ The authors designed a delicate series of experiments to dissolve the implication of flatness and to show that the weight closeness to the initialization seems to be a more related factor.
+ The PAC-Bayesian perspective framework is a novel and interesting viewpoint and the resulting interpretation of IMP is also interesting and convincing.
+ The paper is overall clearly presented and will be of interest for most of researchers in the sparse neural network community.

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

Weaknesses:

- One constructive feedback I could give is that some presentations of plots could be improved for clearer comparisons. For example, I think the unpruned baselines could be added to plots in Figure 1. And to show that the closeness regularization really helps to find winning tickets, it would be better to compare large learning rates plus $\ell_2$_init with unpruned baselines with small learning rates.
- I think it would be nice to know, if flatness is not the key factor behind winning tickets, whether the sharpness regularization like SAM happens to have an implicit regularization on the weight closeness so that it also helps find winning tickets.
- The authors mentioned in the conclusion that they didn't "analyze the case 307 where no solution exists near the initial weights, which needs IMP with rewinding to early epoch." In my opinion, the failure of finding winning tickets in large networks (which is the motivation to introduce weight rewinding in Frankel's work) can also be explained by the trade-off between the minimization of risk term and KL term under the PAC-Bayesian framework --- because training larger networks makes the trade-off so hard that the alternative minimization with IMP also fails. I wonder if the authors have tried this but got no improvement or have not tried at all.
questions: See the weaknesses.
limitations: The limitations are addressed well.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies how the scale of the learning rate and properties such as $\ell_2$ regularization and distance to initialization can affect the performance of sparse subnetworks, especially in the setting of trying to extract winning tickets. Empirical results show that the distance to initialization can play an important role when searching for winning tickets, and regularizing such distance leads to better performing tickets when training with large learning rates. The PAC-Bayesian framework is used to validate some of the presented ideas and to draw connections between IMP, CS, and a minimization of a PAC-Bayes bound using spike and slab distributions.
strengths_and_weaknesses: Strengths:

- The paper is clear and has a clean presentation.

- The findings are interesting, especially how regularizing the distance to initialization can be beneficial when searching for winning tickets even with large learning rates. I think this is promising since there is a significant advantage in having a sparse subnetwork that can be trained from scratch compared to one that can only be trained from an 'early iterate' (as is commonly the case for networks like ResNets when trained with large learning rates): in this case the winning ticket can be completely defined by the binary mask and the random seed used for initialization, instead of having to store/transmit all the parameter values (as in the case of subnets that can only be re-trained from an early epoch).

- The PAC-Bayesian perspective is also interesting, especially Fig. 4 where the two main terms are shown for subnetworks extracted with different learning rates, showing that the KL divergence is indeed smaller for winning tickets.

- Lastly, the connections drawn between minimizing the PAC-Bayes bound and the two ticket search methods IMP and CS are valuable and might have practical implications on how to improve ticket search.



Weaknesses:

- The experimental results are constrained to the CIFAR 10/100 datasets. While ticket search on ImageNet can be quite costly, it is hard to draw final conclusions from results only on CIFAR.

- While the observations regarding learning rate x label noise (Sec 3.1) and learning rate x sharpness (Sec 3.2) are valuable, they seem a bit disconnected from the rest of the paper. While there is some inherent connection between the sharpness observations and the PAC-Bayesian analysis since the PAC-Bayes bound itself has its own measure of sharpness, the learning rate x label noise seems somewhat out of context compared to the rest of the paper. Additional discussion connecting Sections 3.1, 3.2, 3.3 and 4 would be helpful here, or either moving Section 3.1 to the end of the paper (or even to the Appendix) in case there isn't a strong connection between it and the main ideas.

- The biggest weakness, in my opinion, is regarding the results shown in Figure 3. The paper claims that regularizing the distance to init (l2_init) enables one to find winning tickets even when adopting large learning rates, and although in the top left plot of Fig. 3 we do see the 90% sparse ticket performing similarly to the dense network, this considers a suboptimal regularization strength for the dense model. More specifically, the dense model seems to achieve ~92% test acc. with standard $\ell_2$ regularization and $\lambda \approx 10^{-4}$ (top right plot), but in the setting where paper claims to find a winning ticket with large learning rate (top left plot, $\lambda \approx 5 \cdot 10^{-4}$), the dense model seems to yield around 88% test accuracy. Ideally, one would want to achieve close to 92% test acc. when re-training the subnetwork from scratch.
questions: It would be extremely valuable if the ticket depicted in the top left plot of Fig. 3 could achieve a performance similar to a dense model when trained with standard settings, which seems to achieve around 92% test accuracy.

One question is whether the authors have tried to adopt the l2_init regularizer with $\lambda \approx 5 \cdot 10^{-4}$ (the value at which the orange curve 'spikes' in the top left plot) when training the dense network to extract the binary mask, but then switching to l2_norm and a different value for $\lambda$ when re-training the sparse subnetwork -- and if yes, was there any performance improvement compared to adopting the same $\lambda$ and the l2_init regularizer during both phases?

My second question is whether the authors have tried to combine the l2_init regularizer with CS instead of IMP, and whether the same results were observed (orange curve doesn't get close to ~92%).
limitations: The main limitation is described in the last point of 'Strengths And Weaknesses', more specifically the fact that the ticket fails to achieve a performance similar to the dense model trained with standard $\ell_2$ regularization and $\lambda \approx 10^{-4}$.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors examine the generalisation of "winning tickets" trained by iterative magnitude pruning (IMP). It has been observed that a low learning rate is needed to train winning tickets, which usually leads to sharper minima being found and greater vulnerability to label noise. The authors use a series of experiments to show that the sharp minima is not a precondition for winning tickets and argue that the true condition is that the final trained weights are near to the initialisation. They show that by using different training methods, such as SAM or a larger learning rate alongside a regularisation to remain near the initialisation can also lead to winning tickets without sharp minima, which in some cases can generalise better.

They show that this behaviour can be described by a spike-and-slab PAC-Bayes formulation and use this to explain the behaviour of IMP and other methods for finding winning tickets.
strengths_and_weaknesses: The paper is relatively clear and well written. The most complex section is the empirical analysis which makes the main argument about generalisation and closeness to the initialisation, which is relatively well explained but perhaps could be prefaced by slightly more motivation for the following set of experiments (these are well explained individually but the conclusion is somewhat left to the reader). The background on PAC-Bayes and IMP is a little lacking but this may be due to space considerations.

The overall area discussed is highly interesting and of great relevance to the community.

The empirical evaluation in the paper is well thought out and reasonably comprehensive, backing up the central argument well.


**Signficance**

To my (limited) knowledge the viewpoint given of winning tickets as being a phenomenon relating to closeness to the initialisation is a new one and is quite interesting. The PAC-Bayes perspective suggested seems to have real explanatory power and represents progress in this important problem. However I am not familiar enough with the literature to say how original this explanation is.

I note though that the spike-and-slab idea itself is not new. I should also note that the authors appear to use a PAC-Bayes bound for a randomised predictor to upper bound the error of a deterministic one (i.e. $L(f) \le \mathbb{Q}_{f} L(f)$), which has been used as an assumption by some empirical works, but this should be clearly stated.


**Background**

The major caveat in my review is that it is unclear which of the most significant ideas in the paper are new, this should be more clearly explained.


----

I am happy with the answers to my questions and that the PAC-Bayes analysis has been placed on a more solid footing, so I increase my score accordingly.
questions: 1. Exactly how are you motivating the use of a PAC-Bayes bound for a non-random predictor and which are you using?
2. Which of the ideas from the analysis using spike-and-slab and closeness to initialisation are new and which appear in the literature already? This affects my evaluation of the contribution of the paper significantly.
limitations: Yes I believe the paper clearly explains which problems it is addressing.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This work considers the generalization ability of the winning lottery tickets in the lottery ticket hypothesis.

The first message of the paper is that the winning tickets have sharp minima and lead to worse generalization. This message is supported by the following experiments:
- Comparing the test accuracy of iterative magnitude pruning (IMP) with various learning rates with/without label noise;
- Comparing the projected 1-d landscape and calculating the trace of Hessian at convergence for IMP with small learning rate, IMP with larger learning rate, and IMP with learning rate and additional penalty terms.

The second message is that adding regularization on the deviation from the full network parameters allows finding a winning ticket with a large learning rate. This message is supported by comparing the behavior of (sub-)networks with different levels of sparsity.

The third message is that the generalization behavior of winning tickets found via IMP can be captured by a PAC-Bayesian model with a spike-and-slab prior. The choice of the spike-and-slab prior is partially justified by the second message. It is claimed that such a PAC-Bayesian model captures the behavior of winning tickets under different learning rates. This is established by comparing against the zero-mean Gaussian model on the evaluation of the risk/loss and KL-divergence for tickets found with different learning rates. For the proposed model, tickets found with large learning rates have large KL-divergences from the prior and larger risk terms than the tickets found with moderate learning rates. In section 4 the spike-and-slab model is used to provide some explanation for IMP and continuous sparsification.

strengths_and_weaknesses: - Strength: the hyperparameters used for SAM and NVRM regularization are explicitly mentioned;
- Weakness
    + The criterion for finding the winning ticket is unclear: In the experiments reported in Figure 1, the (implied) criterion for finding the winning ticket seems to be the test accuracy being high on the clean dataset, while in Figure 3, the criterion is that the subnetwork accuracy is close to that of the full network.
    + The connection between IMP for winning tickets and the PAC-Bayesian model is not strong. The claim is solely based on the ordering of the risk and KL-divergence for three groups of tickets found through various learning rates. 
    + The presentation can be improved. For example
        1. While it can be inferred that $\delta_{ \{0\} }$ stands for the delta function with a peak at zero-weight, it would be more clear to define explicitly;
        2. It is unclear how $\lambda_{p,i}$'s are chosen in the experiments.
questions: Please see =Strengths and Weaknesses= above.
limitations: N/A
review_title: null

Meta-review: metareview: Overall: The paper analyzes the key factors or indicators behind the successful identification of winning tickets in Lottery Ticket Hypothesis (LTH).

Reviews: The paper received four reviews. Strong accept (absolutely confident), Accept (Absolutely confident), Accept (confident) and Reject (less confident). It seems that there are at least three reviewer that will champion the paper for publication. The reviewers 
found the paper is clear and has a clean presentation. The findings are interesting, as well as the PAC-Bayesian perspective. The authors have provided extensive answers to reviewers' comments, answering most of them successfully.

Main issues raised by reviewers:
- The criterion for finding the winning ticket is unclear
- The connection between IMP for winning tickets and the PAC-Bayesian model is not strong
- The presentation can be improved.
However, the authors have tackled most of the concerns raised.

After rebuttal: The authors have provide extensive clarifications with many additional experimental results, addressing several of the issues raised by the reviewers (some of them acknowledged this effort and they have raised their scores). Overall, the engaged reviewers seem happy with the changes and propose acceptance.

Confidence of reviews: Overall, the reviewers are fairly confident. We will put more weight to the reviews that got engaged in the rebuttal discussion period.
confidence: Certain
Decision: Accept