Sparser, Better, Deeper, Stronger: Improving Sparse Training with Exact Orthogonal Initialization

We express our gratitude to the Reviewer for the positive feedback regarding our work. We are delighted that the Reviewer acknowledges the clear impact of our main idea and appreciates the analysis concerning the expected density of matrices generated by our algorithm. Additionally, we were pleased to note that the Reviewer finds that our experimental section effectively positions our algorithm in comparison to existing methods. Below, we provide responses to the raised questions and suggestions:

While the impact is clear, it leave some questions about the price to pay for sparse networks. [...]

Thank you for this suggestion. In order to better understand how different sparsity levels affect our algorithm, we conduct an experiment on the ResNet56 architecture in which we compare the performance of ERK-Base, ERK-AI, and ERK-EOI schemes for varying densities. We include the description and results of this experiment in Appendix K in the revised pdf. We observe that across different densities, the best performance is given by ERK-EOI, with other methods either performing visibly worse or not holding a clear advantage. We also notice that the benefit of using EOI is the largest for the lowest densities. This is expected when compared with the results from Figure 3, where we see that the signal propagation suffers the most in the high sparsity regime and that only EOI is able to maintain good statistics of the singular values for sparsities larger than 0.8.

Questions:

Are some rotation angles better than others? I can't imagine that using only 1 degree Givens will perform similarly to using only 80 degree Givens

This is a great question. In order to answer it, we run an experiment on the ResNet32 with three different distributions of Givens matrices: In the first one, we always pick 1-degree angle rotations; in the second one, we always pick 80-degree angle rotations, and in the third one, we sample the angle uniformly at random (the default method). Please see Figure 9 and the newly added Appendix G. We notice that the learning curves at the beginning of the training are indeed worse for the 1-degree rotations. This indicates that such a degenerated distribution of Givens rotations isn't preferred and that larger values of rotation angles are beneficial for efficient training.

How can one gain sense of the price (in performance) for a given sparsity level?

The question of the price of performance for a given sparsity level is indeed a very interesting one. In other to assess how the performance of our algorithm is influenced by the sparsity level, we include an experiment for different densities on the ResNet56 model in Appendix K (please see also our response above). In addition, let us also note that a general intuition of how sparsity affects performance can be gained by looking into other research works in sparse training. From the empirical point of view, it has been shown that contemporary networks can be pruned up to 80% without a significant drop in performance, while for sparsity of 50% even random pruning achieves surprisingly good performance [1,2]. From the theoretical perspective, the maximal sparsity is also explored by the strong lottery ticket hypothesis, which sets limits on how large a network needs to be to have a smaller, well-performing subnetwork[3,4]. However, we would like to note that the study into empirical or theoretical limitations of sparsity was not the focus of our paper.

I understand the authors' desire to increase the score, and remind that the final decision is not simply based on an arithmetic mean of the scores. I aim to faithfully represent my opinion during the reviewer/AC discussion period, and will consider increasing the score.

We thank the Reviewer for the time taken to assess our work. We appreciate that the Reviewer describes our approach as simple and mathematically grounded and considers our paper well-written and structured.

Before moving into answering the Reviewer's comments, we would like to clarify that the goal of our paper was to study the static sparse training setting. In such a setup, the network is already pruned (using typically unstructured methods) at initialization, and the pruning mask remains fixed throughout the training (see Section 3.3). This means that the removed connections do not take any part in the computations. In consequence, the network is sparse not only during inference (as it happens for post-pruning, including iterative pruning approaches) but also during the training. Static sparse training is also sometimes referred to as Pruning at Initialization (Frankle et al., 2020; Evci et al., 2020). We have slightly updated the paper where the terminology could have been ambiguous. Please find our responses to individual concerns below.

Overall, the paper is well-written [...] readers will not be able to under the SAO method. The paper should be self-contained.

Thank you for pointing out the missing details. Due to the space limits, we only describe SAO briefly in the main paper, but following the Reviewer’s suggestion, we added Appendix H with a detailed description of this method and a link to this Appendix in the main paper.

The link between sparse training and sparse initialization is not clear.

We would like to again emphasize that in this paper, we focused on the static sparse training setup (see the second paragraph of the Introduction and Section 3.3 for the definition of this setup). The goal of static sparse training is to train a sparse subnetwork by pruning a larger model before the training (see e.g. (Lee et al., 2018; Lee et al., 2019; Frankle et al., 2020; Tanaka et al., 2020; Wang et al., 2020)), and keeping the pruning mask fixed throughout the whole optimization. Therefore, every static sparse training method that computes a pruning mask M automatically defines a sparse initialization, which is simply the element-wise multiplication of the weights with their corresponding masks: $W \odot M$. We apologize, we realized we had not introduced the notion of sparse initializations clearly, which may have been a source of confusion for the Reviewer. We have updated Section 3.3 to include the above-mentioned information (see the updated pdf, changes in red).

It is well understood that within a larger dense network [...] one might want individual subnetworks to perform a task within a multi-tasking/meta-learning setting.

The typical setup used in the literature while comparing different static sparse training methods is a single-task problem (most often, it is a classification task (Lee et al., 2018; Lee et al., 2019; Frankle et al., 2020; Tanaka et al., 2020; Wang et al., 2020)). In order to be directly comparable with those works, as well as to be able to use the same models and datasets, we investigated the performance of EOI in the same setups. We leave extending our results to multi-task or meta-learning setups as an interesting direction for future work

I request authors to support the claim that post-pruning performance is better than sparse initialization-based training. IMHO, if the parameter mask is learned or adaptive during training, the performance is usually better.

The observation that post-pruning (i.e., pruning after training) often exceeds static sparse training (i.e., pruning at initialization) has been shown in the work of (Frankle et al., 2020). We have updated paragraph 3 of the introduction with this citation to avoid further confusion. At the same time, we would like to point out that post-training pruning and standard iterative pruning require dense training (i.e. they start with a dense model). In contrast, sparse training focuses on training architectures that are sparse (i.e. pruned) already at initialization and maintains this sparsity throughout the whole training. However, motivated by your comment, we also conducted an additional experiment in which we consider an extension of static sparse training -- the dynamic sparse training. In dynamic sparse training (DST), the initial mask is allowed to change during the training, but the total density is kept fixed. We compare our EOI approach with two most common methods in DST: SET(Mocanu et al, 2020) and RigL(Evci et al., 2020). We observe that DST methods obtain better test accuracy, but our method is only slightly worse (within the bounds of the standard deviation of the DST methods) and has much lower variance. This suggests that EOI could also be used as an initialization scheme in DST - we are eager to investigate this in the future. Please refer to Appendix I for the results and a detailed description of the experimental setting.

We thank the Reviewer for the feedback. We appreciate that the Reviewer finds our paper clear and easy to follow. Below, we address the raised concerns.

However, it appears that the authors are more dedicated to highlighting the advantages of sparsity and orthogonality than proposing and demonstrating an efficient algorithm.

We kindly ask the reviewer to consider that explaining the motivation behind the need of introducing a new algorithm is a crucial part of a researcher’s task. Only by understanding why we need orthogonality and what advantages it brings to sparsity can we design algorithms that effectively leverage those benefits. Note that orthogonality is commonly known to increase the stability of the training and provide better signal propagation in the network. At the same time, static sparse initializations suffer from poor gradient flow or may result in non-optimal performance (Lee et al., 2019; Evci et al., 2022). By marrying in our algorithm the good signal propagation properties stemming from orthogonality, with the reduced parameter size of static sparse training, we are able to propose a novel sparse initialization scheme that provides a boost of performance over other pruning-at-initialization methods. We do focus on demonstrating the effectiveness of our algorithm through Sections 5.2 and Sections 5.3, where EOI is able to outperform other sparse initialization approaches. It is also the most efficient one for the high sparsity regime setup (Appendix B), which lies at the core of static sparse training research. Finally, note that since EOI produces initializations that are both sparse and orthogonal, any advantages of sparsity and orthogonality that we highlight so crucially in our work are also naturally inherited by our method.

There is a shortage of comparisons with similar algorithms in the experiments.

Please note that in our work, we always include a comparison with 5 most popular static sparse training algorithms (Uniform, ERK, SNIP, GraSP, Synflow - see Section 3.3). In Table 1 and Table 2, each such method is indicated by the “<Method Name> Base” entries. Due to the findings of (Evci et al., 2022) we can also treat such methods as density-per-layer distributions for the orthogonal initialization schemes of AI and EOI (see Section 3). In consequence, for each of the 5 static sparse training methods, we can either directly use the produced by them initialization (“Base”), or treat them as a source of density-per-layer distributions for the AI and EOI algorithm, entries (“AI” and “EOI”). Moreover, for the experiments in Table 1 we also consider SAO, which has its own density distribution. Each combination of these steps yields a different variant of a sparse initialization algorithm. In summary, in Section 5.2 we evaluate in total 14 sparse algorithms, and in Section 5.3 we evaluate 15. We believe it to be a large comparison set. Let us also note that, to the best of our knowledge, AI and SAO are the only other sparse orthogonal approaches to sparse training in the literature.

We recognize that our explanation of that setup might have been vague and might have been a source of confusion for the Reviewer. We have updated Sections 5.2 and 5.3 in the revised paper (changes in text in red) to include this information. In addition, we also corrected the captions of Table 1 and Table 2 to explain the meaning of the “bold” and “underscore” lines. We also encourage the Reviewer to look into our Appendix, in which we conduct additional experimental setups.

We would like to once again thank all the Reviewers for the feedback. We believe we have addressed all the raised concerns and improved our paper following the Reviewers’ suggestions. As the discussion period approaches its conclusion, we kindly request the Reviewers to consider possibly adjusting the score, or alternatively, bring to our attention any further inquiries. We appreciate your time and consideration.