Analyzing Lottery Ticket Hypothesis from PAC-Bayesian Theory Perspective
Authors: Keitaro Sakamoto
Issei Sato
Venue: NeurIPS 2022 Accept (2022)

Abstract: The lottery ticket hypothesis (LTH) has attracted attention because it can explain why over-parameterized models often show high generalization ability. It is known that when we use iterative magnitude pruning (IMP), which is an algorithm to find sparse networks with high generalization ability that can be trained from the initial weights independently, called winning tickets, the initial large learning rate does not work well in deep neural networks such as ResNet. However, since the initial large learning rate generally helps the optimizer to converge to flatter minima, we hypothesize that the winning tickets have relatively sharp minima, which is considered a disadvantage in terms of generalization ability. In this paper, we confirm this hypothesis and show that the PAC-Bayesian theory can provide an explicit understanding of the relationship between LTH and generalization behavior. On the basis of our experimental findings that IMP with a small learning rate finds relatively sharp minima and that the distance from the initial weights is deeply involved in winning tickets, we offer the PAC-Bayes bound using a spike-and-slab distribution to analyze winning tickets. Finally, we revisit existing algorithms for finding winning tickets from a PAC-Bayesian perspective and provide new insights into these methods.

Analyzing Lottery Ticket Hypothesis from PAC- Theory Perspective
Keitaro Sakamoto
Issei Sato The University of Tokyo sato ecc. u-tokyo ac. jp
The University of Tokyo
sakakei 19990g.. ecc. u-tokyo.ac.. JP.
Abstract
The lottery ticket hypothesis (LTH) has attracted attention because it can explain why over-parameterized models often show high generalization ability. is known that when we use iterative magnitude pruning (IMP), which is an algorithm to find sparse networks with high generalization ability that can be trained from the initial weights independently, called winning tickets, the initial large learning rate does not work well in deep neural networks such ResNet. However, since the initial large learning rate generally helps the optimizer to converge flatter minima, we hypothesize that the winning tickets have relatively sharp minima, which is considered a disadvantage confirm this hypothesis and show that the PAC- PAC-Bayesian theory can provide an explicit understanding of the relationship between LTT and generalization behavior. On the basis of our experimental findings that IMP with small learning rate finds relatively sharp minima and that the distance from the initial weights is deeply involved in winning tickets, we offer the PAC-Bayes bound using spike-and-slab distribution to analyze winning tickets. Finally, we revisit existing algorithms for finding winning tickets from IAC-Bayesian perspective and provide insights into these methods.
terms of generalization ability. In this paper, we
Introduction
The high generalization ability of modern neural networks can attributed to the heavier overparam- eterization and effective learning algorithms [22] 30 41]. This increase in the number of parameters leads to high computational cost and high memory usage, and network pruning is one the effec- tive techniques for addressing these problems [22 parameters, the pruned network can often work well with little or no accuracy loss. However, training this sparse subnetwork independently from the initial weights often does not work, and can only obtain the sparse subnetwork through pruning after training the whole network.
14 23 After pruning significant number of
Frankle and Carbin [10] presented "Lottery Ticket Hypothesis (LTH)" that states the existence of winning tickets: small but critical subnetworks which can trained independently from scratch. They proposed algorithm called iterative magnitude pruning (IMP) obtain winning ticket. They pointed out that, for deeper networks such as VGG (35] and ResNet [16), small learning rate is required obtain winning ticket. However, since large learning rate helps the generalization ability of neural networks [25], the learning rate should be well controlled to find a winning ticket that has higher test accuracy. Frankle et al. [11] found correlation between the stability to SGD noise and the ability to find the winning ticket and empirically showed that the large learning rate moves weights much under the low-stability learning process.
this paper, we first empirically show that winning tickets are actually more vulnerable to label noise setting compared to the subnetwork created with the large learning rate; that is, the generalization ability of winning tickets degraded due to the learning rate constraint. In this connection, we then
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

focus on the two concepts flatness and the distance from the initial weights of the winning tickets. We next apply the PAC-Bayesiag theory LTH on the basis of the flatness motivation and show that can explain the relationship between LTH and generalization behavior. We use the PAC-Bayes bound for a spike-and-slay distribution to analyze winning tickets, which is based on our experimental findings that reducing the expected sharpness restricted to an unpruned parameter space and adding the regularization of distance from the initial weights can enhance the test performance of winning tickets. Finally, we revisit existing algorithms such as IMP, continuous sparsification (34] from the point of view of the PAC-Bayes bound optimization. This consideration gives an interpretation of these methods as approximation of bound optimization.
To sum up, our contributions are as follows.
We experimentally show that IMP with small learning rate finds relatively sharper minima and that the distance from the initial weights is critical for IMP, i... balancing the distance and the training error helps to find them.
On the basis of our findings, we reveal that the PAC-Bayesian formulation for a spike-and- slab distribution effectively captures the winning tickets behavior.
We revisit the existing algorithms from the PAC-Bayesiag perspective and explain their behavior.
2
Related Work
Learning Rate The initial large learning rate often improves generalization of deep neural networks
[19 25). The large learning rate generally helps optimizer to converge to flatter minima [24] (3), and these flatter minima are advantagcous for generalization ability rather than sharper minima
18 20 21]. The relationship between flatness and generalization can be considered from PAC- Bayesian perspective 31 32) (see Appendix (A). Frankle et al. [1] provided the insights in why IMP with the large learning rate fails into find winning tickets in some problem settings. They proposed IMP with rewinding to an early epoch to avoid the very early training process because training is not stable to SGD noise in the early training regime (see Appendix A).
Empirical Results on LTH Some studies have also investigated the flatness and the distance from the initial weights on LTH. Bain 2 plotted the loss landscape of winning tickets visually and found that IMP produces more convex and sharper minimum relative to random pruning. Bartoldson et al. 3 found that pruning regularizes similarly to noise injection, and they discussed the generalization of pruned networks considering flatness. They measured flatness by using the trace of Hessian and gradient covariance matrix. He et al. [17] refers the distance from the initial weights to analyze the label noise robustness of winning tickets; they stated that the influence of the label noise is lessened if the distance is suppressed. Liu et al. [26] discussed the relationship between winning tickets and the learning rate considering the similarity between initial and trained weights in terms of pruning mask overlap instead of the distance from the initial weights. There is recent study on finding mask that shows good accuracy without training weights at all [33
Theoretical Results on LTH Malach et al. 29 demonstrated a subnetwork with a comparable
accuracy to the original network in a sufficiently wee-parraeteriize network, without any training. Zhang et al. [42] analyzed the winning tickets generalization based on sample complexity. Although it is limited to the case of a one-hidden-layer neural network, they provided insight into why the sparsity increases the generalization ability. For PAC- Bay-Baa theory, Hayou et al. [15] also used spike-and-slat prior and posterior distributions. However, their motivation and purpose are completely different from our work. Their aim was to obtain a sophisticated pruning mask by optimizing the PAC-Bayes bound, and this is mainly in the context of network pruning rather than LTH. Our work differs in that we use it to analyze the generalization behavior of given winning ticket on the basis of our empirical findings on the learning rate, the flatness, and the distance from the initial weights. In addition to these, we also discuss the relationship with existing algorithms.

---

Clean
Nony
Noisy
0.52
2.8
0.50
0.50
0.00
08
135
0.92
0.80
Test Accurec)
2.92
2.44
0.08
0.20
0.67
0.00
1.82
Test
0.99
0.00
0.80
2.80
0.70
0.47
0.01
Learning rate
Learning
(a) ResNet20
(b) VGG16
Figure 1: Test accuracy on CIFARIO whose labels are randomly flipped (clean: green line, noisy: orange line) when ResNet20 (90% sparse) and VGGI6 (99% sparse) are trained. These subnetworks produced by IMP with various learning rates. The dashed green line shows the unpruned baseline with the same learning rate. In the label noise setting, the model has not yet converged at the same number of epochs the clean setting; therefore we train them until convergence, and training epoch is increased from the setting of Frankle and Carbin [00.
Empirical Analysis
We first show some empirical results because our new findings about winning tickets in this empirical analysis motivate the PAC-Bat BaC-Bayesi analysis for LTH; thus, we interpret the results on the basis of the PAC-Bayesian perspective in the next section.
We empirically investigated the properties of winning tickets mainly related to the learning rate. The small learning rate is good for finding the winning ticket, which is contrary to the intuition that a large learning rate is good in terms of generalization ability. First, we show the small learning rate actually disadvantageous for generalization ability of subnetworks through experiments under label noise. Next, as reason for this, show that the small learning rate finds the relatively sharper minima, and it is possible to find the winning tickets the flatter minima using sharpness regularization. We also focused on the distance from the initial weights reason for why the small learning rate is important for IMP. On the basis of these findings, we will develop a discussion from PAC-Bayesian perspective in the next section. We will show this perspective will theoretically support the findings in this section. We followed the experimental setting of Frankle and Carbin [10 and used modified version of OpenLTHH repository (9]
3.1 Vulnerability to label noise
We examined the test accuracy when some fractions of the labels in the training set are randomly flipped to see whether the generalization behavior of winning tickets is degraded by the constraint that the learning rate must be small. Figure [] shows the test accuracy on clean and label noise datasets of sparse subnetworks produced by IMP with different learning rates. As for the no label noise setting (green line), there is an accuracy drop at some point as the learning rate is increased. We added the original unpruned baseline (dashed green line) to discuss the subnetwork is a winning ticket, and this baseline shows no such accuracy drop when increasing the learning rate. The subnetwork eventually performs worse than the original unpruned network, which means that IMP ultimately fails to find the winning ticket. In contrast, the test accuracy generally continues to improve without decreasing as the learning rate is increased
the high label noise setting (orange line). The test accuracy increases even when it is not a winning ticket for no label setting at the same learning rate. To sum up, the large learning rate is not suitable for finding winning tickets under a clean dataset but is advantagcous in the high label noise setting.
3

---

Small
Large
Small Ir SAM
2eesNec20 CIFAR10
Restec20 CIFARIDO
VGG16 CIFARIU
VCG1O CIFAR1OD
575
500
30-
5:5
Training
500
475
177
130
12
1.01
-1.0
2.11
-0.3 0.55
1.0
-10
0.
3.2 -1.0
1200
1.0
Perturbation along Top Eigenvector
Figure 2: 1-d training loss landscape along cigenvector corresponding to largest eigenvalue Hessian around trained parameters. The test accuracies in the caption correspond to the parameter the center of perturbation (0.0 on the horizontal axis) and show accuracy for the small learning rate (blue), the large learning rate (orange), and the small learning rate SAM (green) form left to right. The subnetwork of ResNer20 has 90% sparsity, and that of VGG16 has 99% sparsity. The top eigenvectors calculated by using PyHessian 44
3.2 Flatness
Now that have that winning tickets have undesirable properties due to the small learning rate, we investigated whether this result comes from the difference in flatness around the found solution. There many previous studies that discuss the relationship between the learning rate and flatness 24 (8) In this experiment, perturbations are added only to unpruned weights to consider flatness on pruned networks. We will discuss this justification in detail in Section 4
First, we visualized the loss landscape shape subnetworks produced by IMP. Figure 2hows 1-d loss landscape of the subnetwork that has a high sparsity. This landscape shows the training loss around the trained weights adding perturbation restricted to unpruned parameters. We can see that the parameters of the winning ticket (small learning rate) in the sharper minimum compared with the large learning rate. The large learning rate can find a flatter minimum; however, the training loss higher and the test accuracy is worse than the small learning rate. This graph is fixed sparsity loss landscape; therefore, it is not possible to discuss whether or not the subnetwork a winning ticket accuracy drop in the large learning rate setting when sparsity is
from this graph. There is actually changed, which means this is not a winning ticket.
Given that IMP requires a small learning rate rather than a large one, these results suggest two possible interpretations; 1) sharp minimum is essential find winning tickets, therefore the large learning rate fails in IMP, 2) sharp minimum is simply the result of small learning rate training, and flat minimum is better for winning tickets if possible. To investigate these possibilities, we used sharpness- aware minimization (SAM) [8] and neural variable risk minimization (NVRM) 37 to search for parameters that lie in neighborhoods having uniformly low loss. They differ in that SAM minimizes the maximum loss in the neighborhood, whereas NVRM minimizes the expected loss in the neighborhood. We used both of them to compare with normal SGD as a baseline. These optimizers are based on SGD with the same setting the original LTH paper [10], and the noise considered in these methods is limited to the unpruned parameters. Figure 2 also shows the loss landscape when SAM is used; It can actually reach flatter minimum. The loss landscape is flat as the large learning rate setting; however, unlike this, the test accuracy is higher than that of the small learning rate.
Next, we investigated the trace of Hessian to analyze the flatness of winning tickets created by these optimizers. The trace of Hessian is used as measure of flatness in the prior work 4 21 39] Table shows that SGD with the small learning rate finds relatively a sharper minimum and that IMP can find flatter one by using SAM NVRM. These optimizers can find relatively flatter minima, which improves the test accuracy to some extent compared with the SGD with the small learning rate (see Appendix T)
also found that the large learning rate still cannot find winning tickets even though we use SAM instead of SGD (see Appendix B.2). The large learning rate has already found relatively flatter

---

Table 1:
Trace of Hessian for ResNet20 and VGGI6 trained on CIFARIO and CIFARI00. We used three optimizers, SAM, NVRM, and SGD. The hyperparameter of SAM and NVRM b are chosen from (0.05, 0.1, 0.2, 0.5) and (0.014, 0.018, 0.022, 0.026) respectively with the highest test accuracy. As baseline, we show the results of SGD with small learning rate, and the learning rate
also set to small for SAM and NVRM. The trace Hessian calculated by PyHessian 40 We averaged over three different subnetworks.
ResNet20
VGGI6
Dataset
Sparsity (%)
SGD
SAM
NVRM
SGD
SAM
NVRM
90
1356
365
1238
107
67
70
CIFARTO
95
1786
791
1218
171
79
62
90
4010
2071
3190
231
119
159
CIFARI00
95
6340
758
2997
411
226
190
Sparsity: 0%
Sparsily: 80%
Sparsity: 90%
Sparsity: 95%
0.1 + Init
0.1 norm
0.9
Telt Accuraty
10
10
10
10-3
10"2
10
10
10
10
10-2
0.01
12 Init
0.01 + norm
10
Regularization on hyperparameterr.
A
Figure 3: Test accuracy of ResNet20 trained on CIFARIO when regularization term is added. Top row shows the results of the large learning rate (0.1) and bottom row shows those of the small learning rate (0.01). Left: 12_ 12_init, Right: 12 2_norm. The dashed red line in the top left shows the unpruned baseline with the small learning rate (0.01).
minima as shown Figure therefore, considered that the results not change by using SAM. This fact implies that the flatness around the parameters found by SGD with large learning rate and by SAM with a small learning rate are similar, however winning tickets cannot be found with the large learning rate because they find different solutions in terms of some other properties. Next, analyze this difference by focusing on the distance from the initial weights.
3.3 Distance from initial weights
As reason for the small learning rate constraint, we hypothesized that winning tickets can only be found by IMP within range not far from the initial weights. In order to confirm this, we ran IMP suppressing this distance and compare it with the usual regularization by the L2 norm regularization. In addition, we also discussed the pruning mask structure Appendix [B. in relation to the distance from the initial weights.
We empirically confirmed that the winning ticket can obtained via the regularization of this distance under the large learning rate setting. Let Ls be the empirical risk on the training samples S,
5

---

À be regularization hyperparameter, 0 be network weights, and m E {0, 1,101 be a pruning mask. In this experiment, the parameters were regularized only for unpruned weights. Specifically, we designed the loss function with 12_ init and 12_norm, respectively, as follows.
(s( m @
0m:) Ls(0)
A| m 012
(1)
Figure 3 shows the test accuracy with different regularizations by changing the hyperparameter A. We plot 80%, 90% and 95% sparsity subnetworks and the original unpruned network as a baseline. If the subnetwork accuracy is close to the whole network accuracy, is considered to be successful in finding the winning ticket. As discussed previously, the large learning rate fails to find winning tickets unlike the small learning rate setting: however adding the regularization from the initial weights changes this trend. In Figure 3/ X around 2 x 10-4 shows that a winning ticket is found since the aceuracy drop from the whole network is suddenly reduced, and there no such a trend when L2 norm regularization is added. This means that IMP can obtain winning tickets suppressing the distance from the initial weights even with the large learning rate. This finding shown more clearly in Appendix B.4 We confirmed it by examining the test accuracy when sparsity is changed for problem settings other than ResNet20 CIFARIO.
We can also obtain interesting results when the learning rate is small. The accuracy drop is small while À is small; however it becomes large increasing In the case of 12_inil, it is possible that the gap widens because sparse networks are more affected by strong regularization (it is the same for large learning rate setting). but in the case of 12 norm, the gap widens significantly even though generalization ability increases because of the regularization. The strong norm regularization makes IMP fail find a winning ticket even if a winning ticket could be found originally.
These results are related to the prior-mean selection from the PAC-Bayesian perspective. In the training of normal network, there is a trade-off between suppressing the parameter norm, i.e., reducing the KL term, and reducing the training loss. Therefore, it is important to ensure a balance between them. As for IMP, there is specific situation where suppressing the parameter norm makes the training loss large due to the failure to find a winning ticket. If we take the initial weights as a prior mean instead of 0, the training loss can decrease by suppressing the KI. term when the trained weights are far from the initial weights. This experiment corresponds to what to take as a prior mean in terms of minimizing PAC-Bayes bound, and this result indicates that setting the initial weights to a prior mean seems to be compatible with minimizing the PAC- PAC-Bayes bound in the case of winning tickets.
4 PAC Bayesian Analysis on LTH
First, we present some possible definitions of subnetwork flatness and consider PAC-Bayes bound of a spike-and slab formulation based on our experiments. Next, we show that this bound captures the generalization behavior of winning tickets and revisit existing algorithms from the perspective of this bound.
4.1 Flatness winning tickets
While we could simply consider the neighborhood of the trained weights in an unpruned neural network, it is not trivial define the flatness of pruned networks depending on how the pruned weights are taken into consideration. The possible measure of the expected sharpness are as follows.
1. Add noise to the parameters restricted unpruned parameter space.
2. Add noise to the parameters including the pruned weights.
3. Recover pruned weights and train the whole network to convergence (re-dense training 13 and measure its flatness.
Measure 2 the same as the unprumed neural network, but the sparse weights in the whole parameter space can no longer be in the local minimum; thus, it is uncertain whether flatness has any meaning such a setting. He et al. 17 conducted re-dense training and showed that solutions at high sparsity are no longer minimizers in high dimensions. They also found that the winning ticket has higher sharpness than the original network based on Measure 3 and concluded that highly sparse solutions do not stick around the flat basins of minimizers. However, none of these metries has any justification.

---

It is known that flatness can be viewed from a PAC-Bayesian perspective [ 31 32 We use
PAC-Bayes bound of spike-and-slat formulation, where expected sharpness corresponds Measure 1. We will also compare this formulation with the normal Gaussian formulation (Measure 2) through numerical experiments and show that the spike-and-slab formulation captures the generalization behavior of winning tickets better. This supports our findings that using SAM and NVRM on pruned networks can enhance the generalization accuracy of winning tickets.
4.2 Spike-and-slab formulation
There are several problems when it comes to using the Gaussian distribution prior and posterior for analyzing winning ticket properties. As discussed in Section 3.3 the distance from the initial weights of the winning ticket is expected to be small. We set the prior mean as the initial weights to take advantage of this property; however the original PAC Bayesian formulation based on the Gaussian distribution has the disadvantage that the pruned weights have weight O and the norm of the initial weights corresponding to these weights remain in the KL part. This not only results in large bound but also behaves contrary to the purpose of getting sparse subnetworks when the bound is optimized. This is because the more sparse the subnetwork is, the larger the bound becomes. In addition, noise inevitably added to the pruned weights when considering expected sharpness since the variance of the pruned part cannot set to zero.
In order to limit the distance from the initial weights and noise added in expected sharpness only to the unpruned weights, we use spike-and-slate distribution, which is the mixture of the Gaussian distribution N and Dirac delta distribution with peak at zero-weight &to), in the PAC-Bayes bound. Let a and og be vectors whose 7th element is variance of Gaussian distribution, X, and X₂ be vectors that represents the mixture ratio of prior and posterior, respectively. 0 represents the network parameter, and mnt is the initial weights and @ is the trained weights.
We design the prior IP and posterior Q as follows.
P(O,) = (1 - \p.1)610) + N(0; I O Opå); ((0,) (1 (0)) + No. 6;, a.a))
(2)
The KL divergence the ppike-and-shle distribution (36] can be calculated as
KL [Q()))
Σ
Agit log
J.S. + Tg.6
02 + (0: Omit.
+ kl (Aquillppue))
(3)
20,
2
where
Agi
(1- Ag.i Appip
kl [Ag.sl] spss = Agas log
+ (1
>q.) log
(4)
Ap.i
Here, Ap.á is set to the target sparsity, so if we want 90% sparsity winning tickets, then Xp,s is set to 0.1. Since the structure the pruned network is given, we set the element of Ag to or 1 asymptotically according to the pruning mask and obtain the following kl divergence about X. This operation has been conventionally done in the entropy discussion [28].
log Ap,
(unpruned)
kl [ (pp.s =
(5)
log(1 - Ap.))
(pruned)
The expected sharpness is as follows.
Ls (s((()) Ls(0)= = Ls | Ls())
where
[Nlx 10, (.. (unpruned) (0/0)
(pruned)
This means that flatness of pruned networks can be discussed adding noise to only unpruned weights. The advantage of this definition compared the Gaussian distribution setting, where we cannot avoid adding noise to pruned weights, will be discussed in the next subsection.
7

---

spike-and-slab
Gaussian (prior mean: zero)
180000
0.90
94000
100000
92000
0.88
140000
0.85
80000
C
120000
54000
0.83
0.1
0.3
risk
Figure 4: Correlation between training risk term and KL term when PAC-Bayes bound is optimized. We plot over subnetworks (90% sparse) generated by different learning rates of IMP (ResNet20 CIFARIO). Left: spike-and-shae distribution, Right: Gaussian distribution with zero-mean prior.
4.3 Numerical Experiment
conducted numerical experiments to confirm that our PAC-Bayes formulation can adequately explain the behavior of winning tickets. We optimized the posterior variance to minimize the PAC- Bayes bound, and plot KL term and the training loss on the posterior distribution to investigate that the bound capture the test accuracy of the subnetworks produced by IMP. As comparison, also experiment with the Gaussian distribution setting using the zero-mean prior. The PAC- -ay-sian bound used here is the variational KL bound [6] (Theorem D.2, and see also Appendix B.7 and implemented the code following Dziugaite et al. 7
Figure 4 shows the distribution of the training risk term and KL term when optimizing the PAC-Bayes bound, and the actual lest accuracy colored. We show that the bound with the spike-and-slab formulation successfully explains the behavior of winning tickets, dividing the point cloud into three groups: A) winning tickets (moderate learning rate), B) subnetworks that failed to find winning tickets (too high learning rate) and C) not much trained subnetworks (too small learning rate).
In the left figure, as the learning rate is increased, the distance from the initial weights increases and the training risk gradually decreases from C to A; The same trend also appears on the right figure. On the other hand, the distribution of differs greatly between left and right. The right figure does not capture the test accuracy well because B should have higher test accuracy considering its KL term and training risk term. This means that, as the learning rate increased and winning tickets can no longer be found, the KL term when prior mean is zero becomes much smaller than that of A. This is because many parameters become close to zero rather than near their initial weights when winning ticket fails to be found (see Appendix B.5). In terms of not only the bound optimization but also the analysis of the existing winning ticket, is preferable to use the spike-and apike-and-slab distribution to set the prior mean as the initial weights.
4.4 Revisiting existing algorithms
We reconsider the existing algorithms for winning ticket searching from the perspective of optimizing the PAC-Bayes bound. Although we focus only on IMP and continuous sparsification, this view could be helpful for other methods as well.
4.4.1 IMP
IMP is heuristic method and does not have explicit target function. Here, explain how IMP behaves the sense PAC- AC-BBayes bound with our formulation instead of viewing IMP as a direct bound optimization problem.
The risk term and KI. term in the PAC-Bayes bound are basically trade-off relationship; choosing complex model to fit the training data will increase the KL term, while choosing simple model

---

Table Drop training accuracy with different pruming criteria. We averaged the accuracy drop of five winning tickets (90% sparsity) produced by different learning rate (ResNet20, CIFARIO).
Criteria
After pruning (%)
After rewinding (%)
After retraining (%)
large_final
-99.8
-88.6
-0.3
small_ final
-89.7
89.5
88.0
random
-88.8
88.66
- 5.77
may not have high accuracy on the training data. We point out that the two steps of IMP: 1) train the subnetwork, 2) prune the subnetwork and revert its weights, optimize the overall bound by alternately reducing one term while suppressing the increase in the other term.
In the first step, IMP trains the subnetwork from initial weights under a given pruning mask. This process reduces the training risk, and the increase in KL term is not expected be so large in our formulation because the prior mean is set to the initial weights and the trained weights of IMP are not far from the initial weights as shown in Sections 3.3 and 4.3
In the second step, IMP prunes a certain percentage of the smallest magnitude weights and reverts the trained weights to the initial state. Reverting 0 to Oinit and changing part of X from 1 to 0 make the KL term small. The number of Gaussian KL summations decreases and the distance from initialization gets to 0, and the À KL part is also reduced if the prior mixture ratio Ap is set to the final target sparsity. This KL reduction is not dependent on the pruning criterion. The problem here is how to minimize the increase in training loss, which is related what heuristic pruning criterion choose and why pruning weights with a small absolute value works well.
Table 2 lists the training accuracy drop when we use three different pruning criteria; large_ innal leaves a large absolute value weights and corresponds to IMP, small mi conversely leaves small weights, and random prunes randomly. This notation of criteria follows that of Zhou et al. 43. As expected, large_final has a smaller drop in training accuracy after pruning than the others. Training accuracy gets lower after reverting; If we assume that retraining can reach weights that show the same or better accuracy because weights achieving good accuracy with the same structure exist, seems to make sense to large final to decrease the KL term while suppressing the increase in training loss. The results in Table 2 confirm this assumption empirically.
We can also discuss the reason why large_final pruning criterion is good for IMP by considering the following simple Taylor expansion (see Appendix (B.6).
If(e + A0) - f()) < 2
| sup 0+740
(6)
Amax
7E/0,1]
where 10+y200 a top eigenvalue Hessian H + 720)
This provides brief insight into why IMP succeeds by pruning small magnitude weights under the assumption that the maximum eigenvalues are not very different.
4.4.2 Continuous Sparsification
Continuous sparsification is a method to find winning tickets by removing the parameters continuously instead of alternating between training and pruning. This target function is as follows,
34
min Cm(m ② 0) + ||m/]],.
(7)
ERR (0,11)
where > is a hyperparameter. Continuous sparsification is formulated as the training loss minimization with the Ln regularization of weights, and sigmoid function a is used for the continuous relaxation of the regularization term as follows.
min
lim (s(a(Bs) 3 0) + (1o(8))]1
(8)
RERd
$-000
40
We can regard this function as an approximation of the PAC-Bayes bound of our formulation. Let Φ; 2 0 be the Gaussian KL part in 3 the summation of training risk and KL is follows.
Ls QQ) + Σ Gidg, + Σ [ Appal

---

We make three approximations: 1) replace Q with E(O) over the spike-and and-slab distribution by first-order Taylor expansion on the training risk. 2) simplify the second term to the L1 norm of X because the second term can be viewed as weighted summation of yq.i. and 3) remove the third term, which can be regarded as a regularization to the target sparsity. This yields the following, which is similar to Eq. 8
min
Cs(Ag C 0) + P
(10)
0 0ER - (0.13
Since the Gaussian KI. de is approximated, the distance from the initial weights is not taken into account in this setting. The authors adopt a problem setting where the weights trained a few epochs ahead instead of the initial weights are used for ticket search following Frankle et al. [[]: therefore their work does not have to consider suppressing the learning rate, i.e., the distance from the initial weights. Note that Hayou al. [13] proposed PAC-Bayes pruning (PBP) by optimizing the PAC- Bayes bound. However, the limitation of our amalysis is that we cannot reveal an explicit relationship between continuous sparsification and PBP.
5 Conclusion
In this work, we explored the fact that small learning rate is required to find winning tickets, and we provided empirical analysis related to flatness and the distance from the initial weights. On the basis of these findings, we used the PAC-Bayesian framework to analyze winning tickets and experimentally showed that it captures the generalization behavior. Finally, we reconsidered IMP and continuous sparsification from PAC-Bayesian perspective. In this study, we not analyze the case where solution exists near the initial weights, which needs IMP with rewinding to early epoch.
6 Acknowledgements
We appreciate anonymous reviewers of NeurIPS 2022 for giving constructive suggestions to improve our manuscript. IS was supported by JSPS KAKENHI Grant Number 20H05703 Japan.
References
[1] Pierre Alquier, James Ridgway, and Nicolas Chopin. On the properties of variational approx- imations of gibbs posteriors. The Journal of Machine Learning Research, 17(1):8374 8414, 2016.
[2] Robert Bain. Visualizing the loss landscape of winning lottery tickets. arXiv preprint arXiv:2112.08538, 2021.
[3] Brian Bartoldson, Ari Morcos, Adrian Barbu, and Gordon Erlebacher. The generalization- stability tradeoff in neural network pruning. Advances in Neural Information Processing Systems, 33:20852-20864. 2020.
[4] Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In International Conference on Machine Learning, pages 1019-1028. PMLR, 2017.
[5] Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proceedings of the Thirty-Thins Conference on Uncertainty in Artificial Intelligence, 2017.
[6] Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, and Daniel Roy. On the role of data in pac-bayes. In International Conference on Artificial Intelligence and Statistics, pages 604-612. PMLR, 2021.
[7] Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, and Daniel M Roy. On the role of data in pac-bayes bounds. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
[8] Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware min- imization for efficiently improving generalization. In International Conference on Learning Representations, 2020.
10

---

[9] Jonathan Frankle. Openlth: A framework for lottery tickets and beyond. attps://githur ccmm/facebollressarr//oooaa
2020.
[10] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2018.
[11] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. International Conference on Machine Learning, pages 9259-3269. PMLR, 2020.
[12] Song Han, Jeff Pool, John Tran, and William J Dally. Learning both weights and connections for efficient neural network, In NIPS, 2015.
[13] Song Han, Jeff Pool, Sharan Narang. Huizi Mao, Enhao Gong, Shijian Tang. Erich Elsen, Peter Vajda, Manohar Paluri, John Tran, et al. Dsd: rense-sparse-dent training for deep neural networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[14] Babak Hassibi, David G Stork, and Gregory J Wolff. Optimal brain surgeon and general network pruning. In IEEE international conference on neural networks, pages 293-299. IEEE, 1993,
[15] Soufiane Hayou, Bobby He, and Gintare Karolina Dziugaite. Probabilistic fine-tuning of pruning masks and pac-bayes self- bounded learning. arXiv preprint arXiv:21 10.11/1/00111 /804, 2021.
[16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[17] Zheng He, Zeke Xie, Quanzhi Zhu, and Zengchang Qin. Sparse double descent: Where network pruning aggravates overfitting. International Conference on Machine Learning, pages 6659. PMLR, 2022.
[18] Sepp Hochreiter and Jürgen Schmidhuber, Flat minima. Neural computation, 9(1::1-42, 1997.
[19] Stanislaw Jastrzehski, Maciej Szymczak, Stanislav Fort, Devansh Arpit, Jacek Tabor, Kyunghyun Cho and Krzysztof Geras*. The break-even point on optimization trajectories of deep neural networks. In International Conference on Learning Representations, 2020.
[20] Yiding Jiang Behnam Neyshabur*, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. In International Conference on Learning Representations, 2020.
[21] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. ICLR, 2017.
[22] Steve Lawrence, C Lee Giles, and Ah Chung Tsoi. What size neural network gives optimal generalization? convergence properties of backpropagation. Technical report, 1998.
[23] Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances neural information processing systems, 2, 1989.
[24] Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. 2020.
[25] Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[26] Ning Liu, Geng Yuan, Zhengping Che, Xuan Shen, Xiaolong Ma, Qing Jin, Jian Ren, Jian Tang, Sijia Liu, and Yanzhi Wang. Lottery ticket preserves weight correlation: Is it desirable or not? In International Conference on Machine Learning, pages 701 1-7020. PMLR, 2021.
[27] Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. In International Conference Learning Representations, 2018.

---

[28] David JC MacKay, David JC Mac Kay, et al. Information theory, inference and learning algorithms. Cambridge university press, 2003.
[29] Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In International Conference Machine Learning, pages 6682-6691 6691. PMLR, 2020.
[30] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. In ICLR (Workshop), 2015.
[31] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generalization in deep learning. Advances in neural information processing systems, 30, 2017.
[32] Behnam Neyshabur, Srinadh Bhojanapalli. and Nathan Srebro. A PAC-bayesian approach to spectrally-normalizer margin bounds for neural networks. In International Conference on Learning Representations, 2018
[33] Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari. What's hidden in a randomly weighted neural network? In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
[34] Pedro Savarese, Hugo Silva, and Michael Maire. Winning the lottery with continuous sparsifi- cation. Advances in Neural Information Processing Systems, 33:1 1380-1133000 1390, 2020.
[35] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. ICLR, 2015.
[36] Francesco Tonolini, Bjorn Sand Jensen, and Roderick Murray-Smin -mithh Variational sparse coding. In Uncertainty in Artificial Intelligence, pages 690-700. PMLR, 2020.
[37] Zeke Xie, Fengxiang He, Shaopeng Fu, Issei Sato, Dacheng Tao, and Masashi Sugiyama. Arti- ficial neural variability for deep learning: on overfitting, noise memorization, and catastrophic forgetting. Neural computation, 33(8):2163-211 2192, 2021.
[38] Zeke Xie, Issei Sato, and Masashi Sugiyama. A diffusion theory for deep learning dynamics: Stochastic gradient descent exponentially favors flat minima. In International Conference on Learning Representations, 2021.
[39] Zhewei Yao, Amir Gholami, Qi Lei, Kurt Keutzer, and Michael W Mahoney. Hessian based analysis of large batch training and robustness to adversaries. Advances in Neural Information Processing Systems, 31, 2018.
[40] Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W Mahoney. Pyhessian: Neural networks through the lens of the hessian. In 2020 IEEE International Conference on Big Data (Big Data), pages 581-590. IEEE, 2020.
[41] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. ICLR, 2017.
[42] Shuai Zhang, Meng Wang, Sijia Liu, Pin- Yu Chen, and Jinjun Xiong. Why lottery ticket wins? a theoretical perspective of sample complexity on sparse neural networks. Advances in Neural Information Processing Systems, 34, 2021.
[43] Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. Advances in neural information processing systems, 32, 2019.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "bolunuUrlAI", "reviewer": "Reviewer_rPEu", "summary": "This work considers the generalization ability of the winning lottery tickets in the lottery ticket hypothesis.\n\nThe 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:\n- Comparing the test accuracy of iterative magnitude pruning (IMP) with various learning rates with/without label noise;\n- 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.\n\nThe 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.\n\nThe 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.\n", "questions": "Please see =Strengths and Weaknesses= above.", "limitations": "N/A", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strength: the hyperparameters used for SAM and NVRM regularization are explicitly mentioned;\n- Weakness\n    + 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.\n    + 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. \n    + The presentation can be improved. For example\n        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;\n        2. It is unclear how $\\lambda_{p,i}$'s are chosen in the experiments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Vawo_iRPHW", "reviewer": "Reviewer_K8ue", "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.\n\nThe 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.", "questions": "See the weaknesses.", "limitations": "The limitations are addressed well.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n+ 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.\n+ The PAC-Bayesian perspective framework is a novel and interesting viewpoint and the resulting interpretation of IMP is also interesting and convincing.\n+ The paper is overall clearly presented and will be of interest for most of researchers in the sparse neural network community.\n\n----------------------------------------\n\nWeaknesses:\n\n- 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.\n- 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.\n- 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JO9RejjmewD", "reviewer": "Reviewer_RxB8", "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.", "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.\n\nOne 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?\n\nMy 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}$.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper is clear and has a clean presentation.\n\n- 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).\n\n- 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.\n\n- 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.\n\n\n\nWeaknesses:\n\n- 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.\n\n- 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.\n\n- 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "A6nI281pAEm", "reviewer": "Reviewer_MZGr", "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.\n\nThey 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.", "questions": "1. Exactly how are you motivating the use of a PAC-Bayes bound for a non-random predictor and which are you using?\n2. 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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe overall area discussed is highly interesting and of great relevance to the community.\n\nThe empirical evaluation in the paper is well thought out and reasonably comprehensive, backing up the central argument well.\n\n\n**Signficance**\n\nTo 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.\n\nI 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.\n\n\n**Background**\n\nThe 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.\n\n\n----\n\nI 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept