Sparse Training from Random Initialization: Aligning Lottery Ticket Masks using Weight Symmetry

We sincerely appreciate the detailed feedback provided; we provide more details below:

In our work, we used 2 trained dense models to find permutation (perm) mapping, as primary aim of the paper was to understand why winning tickets don't work with different random init. One can also find perm mapping early in training, as noted by [Sharma, 2024]. We have added an additional experiment on early matching with CIFAR-10, which shows that models can be matched earlier in training, thus reducing computational cost of our method. (https://imgur.com/a/BgiE4W3)

We don't think sparse models can be used for finding perm mapping as the mask projects the model into a different sub-space, thus cannot be matched with a perm.

Your observation is indeed correct! As noted in manuscript (L188), the perm matching algo uses a greedy approach and thus finds an approximate solution, i.e., the perm matching is not good enough (as you noted). As discussed in Sec 4.3, perm matching works better for wider models [2]. This can be observed in the LMC plot (Fig 3.), where the loss barrier decreases when the model width is increased, showing that the perm matching finds a better solution as we increase the width. Our experiments in Sec 4.3 show that as we increase the model width, gap between LTH and permuted mask decreases, which suggests that the permuted solution will closely match LTH performance if given an accurate permutation mapping.

What is the difference between IMP and LTH in Table 1? Is IMP trained over 5 different seeds and LTH uses the same mask and init over 5 different run

Yes, IMP is trained independently over 5 different seeds with iterative pruning to obtain 5 different sparse/pruned solutions with different sparse masks/topologies ($M_0$, $M_1$, $M_2$, $M_3$, $M_4$, $M_5$). LTH ensemble is trained using the same mask ($M_0$) and init ($w_0$) over 5 different runs (with different data order). Random init $w_0$ defines the winning ticket for mask $M_0$. The permuted ensemble is trained using 5 different permutations ($\pi_1$, $\pi_2$, $\pi_3$, $\pi_4$, $\pi_5$) of the same mask ($M_0$) with five different random inits ($w_1$, $w_2$, $w_3$, $w_4$, $w_5$).

The permutations however, have different random initializations. In spite of this, the permuted solutions are similar or worse than IMP.

This is an interesting question! Our intuition is that in the case of IMP, models are trained with different random initializations, and they discover different sparse topologies, which helps in learning more diverse solutions but is computationally expensive and not practical to create ensembles. The IMP baselines serve as an upper bound for diversity metrics as both training from different random initializations and learning different topologies introduce high randomness/stochasticity to learn very diverse solutions.

LTH, as noted in prior work, does not learn diverse solutions as they are trained using the same mask and init but over different runs [1]. Thus, LTH is not suitable for generating ensembles.

In contrast, our proposed method allows us to reuse the LTH mask with different random inits, introducing more source of randomness than the LTH baseline and thus improving the diversity of the solution. However, since we reuse the mask to train permuted ensembles, the diversity will be less than IMP (which uses both different init and sparse topologies) but good enough for making ensembles. This can be observed in Table 1., where the LTH ensemble does not improve the accuracy compared to a single model, while the permuted ensemble significantly improves the performance compared to a single model. It is worth noting that for CIFAR-100 datasets, the permuted ensemble (77.85%) surpasses the LTH ensemble (75.99%), demonstrating that the permuting mask can help train more diverse solutions with less computational cost incurred as compared to IMP.

We will add more explanations and define LTH, IMP, and Permuted ensembles for an easier understanding.

"Low width networks observe a smaller improvement with permutation"

The perm matching algorithm doesn't work well with lower widths, which can be observed in the loss-barrier plots (high barrier --> poor perm matching). We still observe smaller but statistically significant improvements with the permuted mask, as discussed below. As we increase the width, perm matching becomes better, and the loss barrier decreases (fig 3.); our proposed method with permuted mask becomes closer to LTH.

Even at width=1, we can see significant improvements at 97% sparsity:

CIFAR-10: +1%

CIFAR-100: +3.5%

Imagenet (at 95% sparsity, width=1): +2% (top-1)

We have added more experiments in our reply to reviewer oZBY, which you may also find interesting. If you're satisfied with our explanation, we'd greatly appreciate you updating your score.

[1] Evci et al, Gradient Flow in Sparse Neural Networks

[2]. Ainsworth et al., Git Re-Basin

The authors claim that the IMP sparse mask may not match the basin in which other random init resides. evidence for this claim is just analysis in Figure 1 with assumption of a single layer with two parameters case.

We validate our hypothesis through comprehensive experiments conducted across multiple datasets and model architectures. Our findings are substantiated by similar observation in [3], which demonstrated that IMP sparse masks only work when dense and sparse models are within the same loss basin and linearly mode-connected.

Our hypothesis is intuitive: by matching loss basins of two models with different initializations, we can permute and reuse the IMP mask from a rewind point. Our experimental results provide empirical evidence supporting this claim, showing consistent improvement across different model arch and datasets.

Thus, the assumption that an initialized model is supposed to be in a specific basin may not be true.

We agree that initialization alone does not determine the basin. However, we do not claim this anywhere in the manuscript. Models trained from the same initialization can end up in different basins [1]. That’s why using a rewind point for Lottery Tickets is necessary, and we use a rewind point with our method as well. We will add a note on this in final version of manuscript to make it clearer.

Our method builds upon the fact that models trained using LTH mask (with rewind points) always land in the same basin, as the authors observed in [2]. Our key claim is that the winning mask can be used with a rewind point obtained from different init, provided we account for weight symmetry to align the basins. We empirically demonstrate this through extensive experiments across multiple datasets and model architectures.

If the proposed sparsification method is effective with larger models, it would be meaningless.

We respectfully disagree with this statement. Even with width=1, we can observe statistically significant improvement for different datasets as shown in Tables 5, 9, 10, 11.

• CIFAR-10 (at 97% sparsity, width=1) - Improvement of 1%
• CIFAR-100 (at 97% sparsity, width=1) - Improvement of 3.5%
• Imagenet (at 95% sparsity, width=1) - Improvement of 2% (top-1)

These improvements are statistically significant and demonstrate the efficacy of our method. In the manuscripts, we added experiments with varying widths to get more insights about the accuracy of permutation matching and show that once permutation matching gets better on increasing the width, the gap between LTH and permuted mask (our method) reduces. This experiment provides more insight into the role of permutation matching for our proposed method. You can find more details in Sec 4.3.

We would also like to highlight our work aims at better understanding of lottery tickets and winning masks, not just improving the accuracy. As noted by reviewer oZBY, our work "provides novel insights into the relationship between winning tickets and their original dense networks.” We believe our findings will be useful for the sparse training research community.

In the main manuscript, the authors use 'LTH mask' repeatedly. However, it is difficult to find the details of which methods the authors use in the main manuscript and I managed to find the details in the Appendix. Similarly, in experimental sections, It is difficult to find what 'Naive' refers to. Overall, a clearer and more reader-friendly presentation seems to be required.

We appreciate the suggestion; we will add a separate paragraph to define naive, LTH and permuted masks for an easier understanding.

However, we would like to point out that we have defined the LTH, naive, and permuted mask at multiple places in the manuscript (first one at L94-96; see more below). Moreover, Figure 2 in the manuscript explains the differences between LTH, naive and permuted baselines.

• Line 94-96: "Permuting the LTH sparse mask to align with the new random initialization improves the performance of the trained model (permuted), compared to the model trained without permuting the sparse mask (naive)."

• Line 190-192: "We denote training with the permuted mask, $\pi(**m**_A)$ as permuted and with the non-permuted mask, $**m**_A$ as naive"

• Line 212-214: "To evaluate the transferability of the permuted LTH mask we train, a different random initialization $**w**_B^{t=0}$, the LTH sparse mask $**m**_A$ and permuted LTH mask $\pi(**m**_A)$, which we denote the naive and permuted solution respectively."

If you're satisfied with our reply, we'd appreciate if you can update your score.

[1]. Frankle et al., Linear mode connectivity and the lottery ticket hypothesis

[2] Evci et al, Gradient Flow in Sparse Neural Networks and How Lottery Tickets Win

[3]. Paul et al., Unmasking the Lottery Ticket Hypothesis: What's Encoded in a Winning Ticket's Mask

 1. LTH was introduced by Frankle et al. [1], who hypothesized the existence of winning tickets at initialization. However, in this paper, they only experimented with small models and datasets and found that LTH from random init doesn’t work for larger models. 

 2. Quoting directly from paper: "We only consider vision-centric classification task on smaller dataset (MNIST, CIFAR10). We do not investigate larger dataset."

3. Follow-up paper [2] from Frankle et al. proposed that for LTH to work on larger models, we need to apply the mask at the rewind point (not at init) and linked this to SGD instability: "In this paper, we demonstrate that there exist subnetworks of deeper networks at early points in training"  (page 2).

4. Frankle et al. added more analysis in subsequent version of the paper—which you cited [3]—and studied SGD stability by analyzing linear mode connectivity: 
 "We introduce instability analysis to determine whether the outcome of optimizing a neural network is stable to SGD noise, and we suggest linear mode connectivity for making this determination." 
 "We show that IMP subnetworks become stable and matching when set to weights from early in training, making it possible to extend the lottery ticket observations to larger scales."

Thank you for the detailed feedback and helpful insights. We have added new experiments based on your insights/questions and added our response below:

a natural question that arises is whether the permutation function can be obtained early in training eliminating the requirement for fully training the new model?

In our work, we used 2 trained dense models to find the permutation mapping, but we can also find the perm mapping early in the training, as noted by [Sharma, 2024]. We have added an additional experiment on early matching with the CIFAR-10 dataset, which shows that models can be matched earlier in the training, thus reducing the computational cost of our method. (https://imgur.com/a/BgiE4W3)

For instance can those masks be reused across datasets ?

We conducted an additional experiment where we obtained a mask for the CIFAR-10 dataset and reused the mask with a new init on SVHN datasets. Permuted mask outperforms unpermuted mask (naive) at all levels of sparsities. Thank you for this interesting direction, we will add more experiments in the final version of the paper. (https://imgur.com/a/UDiMQHs)

Can the randomly initialized neural network be permuted

Yes, indeed, we can also apply the permutation, $\pi$, to the random initialization instead of the mask; the resulting network remains functionally equivalent. In our work, we chose to permute the mask as we did not want to modify the new random init.

Can the authors clarify what they mean by rewind points? Is it simply the training iteration at which the masks were applied to various dense networks ?

That's correct! Rewind points is the training epoch at which sparse mask is applied to the dense model. We will make it more clear in the paper.

Is it also the point at which the weights were rewinded during IMP while obtaining the original mask ($**m**_A$) resulting in different masks for different rewind points?

We used IMP-FT, which does not use weight rewind to obtain sparse masks. We preferred IMP-FT over IMP with weight rewinding because IMP-FT is computationally less expensive, which allowed us to conduct extensive experiments. In our experiments, we obtain a mask from IMP-FT and apply the mask to the dense model at different rewind points.

in Figure 4, is the IMP used along with weight rewinding or is IMP-FT used?

Since Paul et al. used IMP (with weight rewinding) for their analysis [1], which suggested only successive IMP iterations are linearly mode-connected, we used IMP (with weight rewinding) in Fig 4. to show that all sparse networks found in each iteration of IMP and dense networks are linearly mode-connected once the variance collapse is taken into account. We decided to use IMP with weight rewinding in Fig 4. for a fair and direct comparison to observations made in [1].

If IMP-FT was used then does the linear mode connectivity exist between the dense network and the sequential winning tickets of lower density?

We conducted an additional experiment to confirm that linear mode connectivity exists between the dense network and sparse models at each iteration of IMP-FT. We appreciate your attention to detail; this additional analysis provides valuable insights that strengthen our paper's findings. (https://imgur.com/a/2l7khkN)

The results show a clear trend as the width of the networks increases. The authors show that this is due to better LMC. Can this be simply because the permutation matching is better because each unit has a larger pool of units to match from ?

Yes, that’s correct. We have the same intuition as yours that wider models (with $\ell$ layers, each of width $n$) have more possible permutations (up to $(n!)^{\ell}$), which makes matching two models more accurate. We show this by increasing the model width and comparing the LMC. As observed in Fig.3, on expanding the model width, LMC becomes better, suggesting permutation matching is better for wider models. We will add this explanation/intuition to the final manuscript.

Additionally, the variance in the unit activations can be studied, larger width may result in lower variance and better match.

This is an interesting insight that could explain why activation (permutation) matching works better for wider models. We analyzed the variance across all layers and observed that the variance for each layer significantly decreases with increasing the width. For example, variance for the second conv layer in third block decreases from 0.012 to 0.0001 on increasing width from 1 to 4. Other layers follow the same trend. We will add plots for all the layers in the manuscript.

We hope that we have answered all your questions/concerns; we would really appreciate it if you could update your final score!

[1] Paul et al., Unmasking the Lottery Ticket Hypothesis: What's Encoded in a Winning Ticket's Mask