{'fraction_non_alphanumeric': 0.03942195026689233, 'fraction_numerical': 0.01473766436661893, 'mean_word_length': 4.46160409556314, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 3, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Accelerated Sparse Neural Training: A Provable and Efficient Method to Find N:M Transposable Masks

Unstructured pruning reduces the memory footprint in deep neural networks (DNNs). Recently, researchers proposed different types of structural pruning intending to reduce also the computation complexity. In this work, we first suggest a new measure called mask-diversity which correlates with the expected accuracy of the different types of structural pruning. We focus on the recently suggested N:M fine-grained block sparsity mask, in which for each block of M weights, we have at least N zeros. While N:M fine-grained block sparsity allows acceleration in actual modern hardware, it can be used only to accelerate the inference phase. In order to allow for similar accelerations in the training phase, we suggest a novel transposable fine-grained sparsity mask, where the same mask can be used for both forward and backward passes. Our transposable mask guarantees that both the weight matrix and its transpose follow the same sparsity pattern; thus, the matrix multiplication required for passing the error backward can also be accelerated. We formulate the problem of finding the optimal transposable-mask as a minimum-cost flow problem. Additionally, to speed up the minimum-cost flow computation, we also introduce a fast linear-time approximation that can be used when the masks dynamically change during training. Our experiments suggest a 2x speed-up in the matrix multiplications with no accuracy degradation over vision and language models. Finally, to solve the problem of switching between different structure constraints, we suggest a method to convert a pre-trained model with unstructured sparsity to an N:M fine-grained block sparsity model with little to no training. A reference implementation can be found at https://github.com/papers-submission/structured_transposable_masks.


Introduction
Deep neural networks (DNNs) have established themselves as the first-choice tool for a wide range of applications, including computer vision and natural language processing. However, their impressive performance comes at a price of extensive infrastructure costs -as state-of-the-art DNNs may contain trillions of parameters [10] and require thousands of petaflops [6] for the training process. For this reason, compression of DNNs training and inference process is a research topic of paramount importance in both academia and industry. The main techniques of compression include quantization [2,34], knowledge distillation [17], and pruning [15,23].
Pruning DNNs is one of the most popular and widely studied methods to improve DNN resource efficiency. The different pruning methods can be categorized into two different groups: unstructured and structured pruning. While the former can achieve a very high compression ratio, it usually fails in reducing the computational footprint in modern hardware. In contrast, structured pruning methods, such as block [41] or filter [23] pruning, are more hardware friendly. Unfortunately, these methods usually fail to keep the original accuracy for high compression ratios [37]. Finding an optimal structured sparsity pattern is still an ongoing research topic.
Recently, Nvidia [36] announced the A100 GPU, containing sparse tensor cores which are able to accelerate fine-grained sparse matrix multiplication. The sparse tensor cores in A100 enable a 2x acceleration of regular matrix multiplication in DNNs, Y = W X, where W and X are weight and input matrices, respectively. The only requirement is that W would have a fine-grained 2:4 sparsity structure, i.e. out of every four contiguous elements in W , two are pruned. Nvidia [36] suggested a two-fold scheme for pruning a pretrained dense model: (a) Define a fine-grained 2:4 fixed mask, and (b) retrain with the masked weights using original training schedule. Indeed, the Nvidia [36] approach is very appealing for the common case where a pretrained dense model is given.
While the Nvidia [36] method works well on many models, a pretrained model is not always given. In those cases, one has to first train a dense model and only then try to prune it. To alleviate this demand, Zhou et al. [43] suggested a method that trains from scratch a model with N : M fine-grained mask, using a sparse-refined straight-through estimator (SR-STE). Similarly to the quantization-awaretraining methods [18], they maintain a dense copy of the weights and prune it in every iteration, passing the gradients using the straight-through estimator [5]. Since the mask dynamically changes while training, they suggest adding an extra weight decay on the masked (i.e. pruned) elements to reduce the mask changes during the training process. As opposed to Evci et al. [9] that aims to reduce memory footprint for sparse training from scratch, Zhou et al. [43] only eliminates the need to train a dense model before pruning it. work. Motivated by understanding fine-grained sparsity we first suggest a measure to rank different sparsity mask, then we suggest a method to accelerate training with fine-grained sparsity and finally propose a method to change the fine-grained mask without re-training.
Motivated by these promising results, our goal here is to answer three remaining questions: (Fig. 1) 1. How to rank different types of sparsity masks? We suggest a new measure called "mask diversity", which is the first to connect mask constraints and network accuracy (Section 3). 2. Can fine-grained sparsity masks accelerate training? We start by observing both the forward and the backward matrix-multiplications involving the weight matrix W . Since the backward pass requires using the transposed matrix W T : and in general W T does not have an N : M fine-grained sparsity structure (even if W has this structure), the methods suggested in [43,36] accelerate only the forward pass matrix-multiplication, Y = W X. Consequently, the current methods only utilize in part the sparse tensor cores to accelerate training. We propose a novel N : M transposable-fine-grained sparsity mask, where the same mask can be used for both forward and backward passes (Fig. 2). We focus on accelerating sparse training in the two settings detailed above: (a) starting from a pretrained model, and (b) starting from scratch. For (a) we derive a novel algorithm to determine the optimal transposablemask using a reduction to a min-cost flow problem. For (b) we devise an approximation algorithm with an (almost) linear (in input-size) time complexity that produces a mask whose 1 norm is within a factor of 2 from the optimal mask. We show the effectiveness of both methods (Section 4). 3. Can we change the type of sparsity mask structure without re-training? Different hardware devices can support different types of fine-grained sparsity masks. Therefore, we suggest the "Adaprune" method, which converts between types of sparsity masks (even from unstructured masks) without the need of re-training, and almost no degradation in accuracy (Section 5).

Related work
Pruning of neural networks weights has been extensively investigated, starting with classical methods in the late 1980s [20,31,32,21] and then amounting to dozens of papers published in recent years. Since DNNs are generally over-parameterized, pruning the weights reduces their memory footprint. In special cases, when the sparsity mask has a specific pattern, it has the potential to reduce computational footprint as well. The most common practice is to prune a pretrained dense model, so that it will be sparse at deployment. Since the accuracy of the pretrained dense model is known, one can tune the sparsity level to ensure comparable accuracy for the sparse model. Recently, a new line of research that aims to train sparse models from scratch [14,7,9] has emerged. The goal is to train models that cannot fit into currently available hardware. Next, we briefly overview the structured, unstructured, and accelerating-sparse-training categories. Unstructured pruning. It removes individual elements of the matrix, aiming for high total sparsity, while being agnostic to the location of the pruned elements. Standard pruning methods are based on different criteria, such as magnitude [15], approximate L 0 regularization [26], or connection sensitivity [22]. Recent methods [12], suggested to train a dense network until convergence, extract the required mask ("winning ticket"), and use the original training regime to re-train the active weights from their original initialization or final values [38] using the original training schedule. These methods are able to achieve over 80% sparsity on ResNet50-ImageNet dataset [38]. Despite the high sparsity ratio that can be achieved with these methods, modern hardware cannot efficiently utilize such a form of sparsity for reducing computational resources [36]. Structured pruning. It removes weights in specific location based patterns, which are more useful for hardware acceleration. Such methods can be applied at either the level of channels or layers. For example, Li et al. [23] remove the channels with the lower norm, Luo et al. [27] prune channels according to the effect on the activation of the following layer, and [41] split the filters into multiple groups, applying a group Lasso regularization. All these methods are natively supported in both hardware and software, as they effectively change the model structure by reducing channels or groups. Yet, no such method was able to achieve a reasonable accuracy with sparsity levels higher than 50%. As observed by Liu et al. [25], filter pruning of a pretrained dense over-parameterized model is rarely the best method to obtain an efficient final model. Thus, here the structured pruning serves mostly as a DNN architecture search for the optimal compact model [40,42]. Our work is most closely related to Zhou et al. [43], which is the first work that attempted training with a fine-grained N : M structured sparsity mask, as explained above.
Accelerating sparse training for model deployment. The most common approach for sparse model deployment requires a three steps process: (a) train a dense model; (b) define a sparsity mask (c) fine-tune while enforcing the mask on the model's weights. The lottery ticket hypothesis of Frankle & Carbin [12] demonstrates that we can avoid the dense training, i.e., step (a), had we known how to choose the appropriate mask. Since Frankle & Carbin [12] discovered the optimal mask (winning ticket) by applying dense training, the question of how to find the optimal mask without training remained open. Since setting a predefined fixed mask results in some accuracy degradation (Gray et al. [14] that requires expanding the model size), several researchers [4,29,30,7,9] tried to enable dynamic mask changes during the training process. All methods focused on unstructured sparsity and aimed to enable training large models on hardware with memory limitations. In contrast to these approaches, Zhou et al. [43] does not aim to reduce the model memory footprint during training, but rather accelerate inference while avoiding dense pre-training. To that end, they keep a dense weight matrix, and in each iteration they re-calculate the mask. With the obtained pruned copy of the weights they perform the forward and backward pass and update the dense copy. Therefore, this method is most relevant when a pretrained dense model is not given, and one wishes to obtain a fine grained N : M sparse model for inference. While our work focuses on the setting of Zhou et al. [43], we argue that it can easily combined with Evci et al. [9] work, as it aims to solve a different issue within the same problem.

Mask Diversity
Structured sparsity requires masks with a hardware-friendly structure type. Yet, which structure should be employed is still an open question. The additional hardware cost (mainly chip-area and power) required to support each of the structures is hard to quantify, as it varies based on the hardware design. However, the effect of the structure on the model accuracy is oblivious to the hardware at hand. Therefore, in this section, we aim to find a method for ranking different types of sparsity masks, which can predict help the model accuracy. We start from an hypothesis that the structure constraints cause accuracy degradation. Thus, we expect that the best sparsity levels, without accuracy degradation, would be achieved by unstructured sparsity, which has no requirements on the sparsity structure type. To quantify how much a specific structure constrains the model, we introduce a new measure, called mask-diversity (MD). MD is the number of all possible masks that adhere to the restrictions of the structure under similar sparsity level. As an example, we derive the MD for a tensor size T under four different structure constraints: 2.8 · 10 12 5.7 · 10 14 Transposable 6 · 10 4 4 · 10 8 1.7 · 10 13 Sequential 4 · 10 9 4 · 10 7 4 · 10 5 Table 1 shows the MD for a matrix of size 8 × 8 with 50% sparsity under different constraints. As expected, unstructured sparsity achieves best in class MD, however its hardware cost makes it unfeasible to use on modern architectures [14,8,13]. Additionally, sequential N:M sparsity has worst in class MD and consequently we expect that using it would harm the model accuracy (Fig. 3a). Thus, from here on, we focus on the structured and transposable structured fine-grained sparsity. Notice the MD of structured 2:4, which was used in [36,43] is severely reduced when transposable constraints are enforced. Since a transposable structure enables training acceleration (Section 4), supporting this structure is essential. Thus, we suggest a minimal expansion of the block size (from 4 to 8) which enables the transposable fine-grained structure to reach a similar MD as the 2:4. Increasing the block size requires more multiplexers to support the N : M structure [24]. However, the hardware cost increases only logarithmically with respect to N (details given in Appendix A.5). We therefore argue that such an expansion is reasonable. To better test our hypothesis, we measured the accuracy degradation with respect to the mask diversity on ResNet18 with Cifar-100 dataset. As can be seen in Fig. 3a, the accuracy correlates with the MD metric and the 4:8 transposable fine-grained mask reached a comparable accuracy to the 2:4 fine-grained mask. Moreover, recall the common method of magnitude pruning has an underlying objective to preserve the tensor 1 norm. We therefore measured the effect of the different constraints on the 1 norm in Fig Notice that mask diversity is correlated with magnitude preservation. As expected the 4:8 transposable mask has a similar 1 norm score as the 2:4 mask. Additional results and details in Appendix A.7 .

Computing transposable sparsity masks
In general, training DNNs requires three matrix multiplications per layer. The first multiplication is required for the forward propagation between the weights and activation. The other two multiplications are used for the backward and update phases. The backward phase calculates the gradients of the loss function with respect to the input of the neural layer. This is done by recursively passing the error from the last layer to the first (Eq. (1)). Note that the backward phase uses the transposed weight matrix. Hence, accelerating the backward phase requires the transposed weight matrix to adhere to the hardware required pattern (e.g., N : M fine-grained sparsity). In this section, we tackle this issue by presenting a novel to find N : M transposable fine-grained sparsity masks, where the same mask can be used to accelerate both forward and backward passes (Fig. 2). The required mask contains only M − N non-zero elements, for every contiguous M elements, in both W and W T simultaneously. We formulate the problem and suggest two methods to generate the transposable mask.
Problem formulation. First, we provide an integer-programming (IP) formulation for finding an optimal transposable fine-grained mask. Let us consider a block of size M × M in a weight matrix W . Our goal is to maximize the 1 norm of W after masking N elements in each row and column. We formulate the problem as an integer program. Define a binary sparsity mask S ∈ {0, 1} M ×M , where S i,j = 1 if and only if the element W i,j is not pruned, and otherwise S i,j = 0. The resulting integer program is In the following, we examine several methods for solving this problem. We first describe an optimal, yet computationally expensive method. We then describe a more efficient method, which provides an approximate near-optimal solution.
Reduction to Min-Cost Flow. General integer programs (IP) require exponential time complexity with respect to the input size (worst-case). Fortunately, Fig. 4 shows that our IP formulation (Eq. (3)) reduces to a min-cost flow problem. There is a vast literature on efficient min-cost flow algorithms (see e.g., [1]), however, the most efficient algorithms for our setting take M transposable-sparsity optimization as a min-cost flow problem. In addition to a source and a sink, the network has a node for each row and for each column. The construction uses three types of edges: (i) source edges emanating from the source node s into each row node i; (ii) sink edges connecting each column node j with the sink node t; and (iii) a coefficient edge (i, j) for each matrix element Wi,j. Each source edge (s, i) has capacity M 2 which is equal to the number of elements that need to be selected for pruning in row i. Similarly, each sink edge (j, t) has capacity M 2 which is equal to the number of elements pruned in column j. Each coefficient edge (i, j) has unit capacity and cost |Wi,j|. Finally, selecting a matrix element with weight Wi,j for pruning corresponds to a unit flow on the coefficient edge (i, j). Assuming the source and sink edges have zero-cost, there is a one-to-one correspondence between a min-cost flow solution that sends a flow of value M 2 2 from the source s to the destination t in this construction, and an optimal transposable mask minimizing the sum of absolute values selected for pruning.
2-Approximation algorithm. We design a greedy 2-approximation algorithm (see Algorithm 1) having a low time complexity that can be used in practice without compromising too much the quality of the solution produced. Unlike the optimal min cost flow solution that runs in time complexity of O(M 3 ) for a block size of M × M , Algorithm 1 has a running time of O(M 2 log M ) i.e., a time complexity that is almost linear in the number of block elements M 2 . The approximation algorithm uses the same construction described in Fig. 4, but instead of running a min-cost flow on the graph, it employs a simple greedy approach. Let P be the list of edges pruned by Algorithm 1, let W (P ) be the total weight of the edges in P , and let W * be the weight of an optimal solution (i.e., the minimal sum of edges that can be pruned to create a M 2 : M transposable sparsity mask). The next lemma establishes that Algorithm 1 finds a 2-approximate solution (proof in Appendix A.2, with an example showing the upper bound is tight): Lemma. Algorithm 1 produces a tight 2-approximate solution, i.e., W (P ) < 2 · W * . if degree(u)≤ M 2 or degree(v)≤ M 2 in P then P ← P + e i .
In Table 2 we show the running time overhead of ResNet50 training with IP, min cost flow and 2approximation algorithms over regular training, the algorithms were implemented in a non-optimized way. All experiments were run in a single GPU and the mask was updated every 40 iterations. Notice the acceleration achieved with the 2-approximation algorithm in comparison to the naive IP. In Appendix A.3 we extend the complexity analysis. In this section, we demonstrate the effectiveness of our proposed transposable N : M fine-grained structured sparsity in computer vision and natural language processing tasks. We evaluate the suggested method in two cases: (i) initialize from a trained dense model and re-train with a fixed mask, similar to APEX's Automatic Sparsity (ASP [36]), (ii) train from scratch and update the mask frequently, as done by Zhou et al. [43]. We show comparable accuracy to previous methods, while achieving a significant reduction of the training process resources -by exploiting the sparse tensor core abilities, allowing their use both in forward and backward passes. In all the experiments we use a 4:8 transposable-mask, which as shown in Table 1, have a similar MD as 2:4 mask used in previous works [36,43]. Initialization from a trained dense model We evaluate the suggested N : M transposable mask using a trained dense model as initialization. In order to find the transposable mask, we solve the min-cost flow reduction (Fig. 4) on the dense trained network and then fix the mask. In Table 3 we compare our method with ASP [36] on classification (ResNet50 -ImageNet dataset), detection (MaskRCNN -COCO dataset) and question answering (BERT-large -SQuAD dataset) tasks. While both methods initialized from the pre-trained models, the 4:8 transposable enables propagation acceleration in the retraining phase where ASP does not. Sparse Training from scratch. In order to avoid the training of a dense model, we also evaluate the proposed transposable N : M mask in the training from scratch setting. Similar to Zhou et al. [43] we keep a dense copy of the weights and before each forward pass we mask the weights with a N : M transposable mask. In contrast to Zhou et al. [43] who changed the mask every iteration, we found that we can use 2-approximation scheme to extract the transposable mask every 40 iterations. Empirically we found that the 2-approximation scheme is on average within a factor of 1.2 from the optimal mask. The hyper-parameters used for training are equal to the ones suggested by Zhou et al. [43]. In Table 4 we test the proposed method over ResNet18, ResNet50, ResNext50, Vgg11 (ImageNet dataset) and fine-tune of Bert (SQuAD-v1.1 dataset) and compare to Zhou et al. [43] results. As can be seen, we achieved comparable accuracy with 2x sparse tensor cores utilization in the training process.

Structured sparsity without full training
In section Section 4 we suggested 4:8 transposable-mask to accelerate training, but what should we do if we wish to deploy the output of such training on hardware that supports only 2:4 finegrained sparsity. Forcing structured sparsity on a model that was trained with a different structured sparsity, leads to a severe accuracy degradation as several bits of the mask may change to satisfy the structured sparsity requirements. In this section we would focus on the more common case of deploying unstructured sparse model on hardware that support N:M structure. This is a fundamental problem as most DNN pruning methods focus on unstructured pruning, which reduces the memory footprint. However, current hardware implementations suggest that, unless very high sparsity levels are achieved, the model cannot be accelerated at all. Hence, commonly, the weights are simply decompressed before multiplication. To understand the problem we study the probability that an unstructured mask would not violate any N : M constraint [36]. Then we discuss two light methods to bridge the gap when a sparse model is given but the hardware does not support its structure.
Probability for violating the N : M constraint in unstructured sparsity. Let X = {x 1 , x 2 , ..., x M } be a block of independent and identically distributed random variables. Assume that with a probability ρ, x i can be pruned without accuracy degradation (i.e., unstructured pruning).
In this section, we consider a general form of block sparsity in which, for a block of size M , at least N values could be pruned. Define X to be N : M sparse if this M sized block has at least N values that can be pruned without harming accuracy. The probability of having a N : M sparse block is given by the binomial distribution and so In Fig. 5a we plot Eq. (4) for the case of ρ = 0.5. To force a given sparse model to have a fine grained N : M sparsity, we need to make sure that N out of every M contiguous elements are zero. Therefore, as in Nvidia [36], in each block we prune N weights with the lowest magnitude (including any zero weights, e.g., non-active). Forcing this pattern on an existing unstructured mask might remove active (non-zero) weights, i.e., flipping some of the mask values from one to zero. We named those required flips, pattern-violations. Removing active weights without re-training tends to severely degrade the model accuracy. To demonstrate the problem we used an unstructured sparse pretrained ResNet-50 model (ρ = 0.86) and set the N : M structure per-layer, based on Eq. (4), such that the probability for a pattern-violation would be equal or less than a given percentage. Here we used a block size of M = 8. Notably, without any optimization even a 1% pattern-violation results in severe degradation (Fig. 5b). Next, we describe two light methods to boost the accuracy. Fixing pruning bias using mean absorption. Several works [3,11,19] reported that it is important to fix the bias introduced when quantizing the model. We build on those results and suggest absorbing the mean of the N pruned weights into the M − N non zeroed weights. As can be seen in Fig. 5b this simple fix, by itself, greatly boosts accuracy.
AdaPrune. Recently, several works [19,33] suggested light and fast fine-tuning techniques for post-train quantization. These techniques replace the heavy full model training with a fast perlayer optimization which requires only a few iterations to converge. While each method applies a different optimization technique, they all aim to reduce the discrepancy between the quantized and full-precision layer outputs. We adjusted the parallel-AdaQuant [19] technique to the pruning problem by defining its objective to be: where W is the original weight layer, W is the weight layer we aim to find, X is the output of the previous activation layer, S is the weight sparsity mask, and is a component-wise product. We named this method AdaPrune. In our experiments we used 1000 images from the ImageNet training set as a calibration set. As can be seen in Fig. 5b, AdaPrune is capable of correcting the remaining error and obtain less than 1% degradation from the original unstructured-sparse model counterpart.
We argue that with AdaPrune, we can potentially adapt any generic mask to the hardware at hand, thus elevate the need to retrain the model. However, full re-training is still necessary when starting from a dense model (thus having 50% pattern-violation), since there we get 2.3% degradation using AdaPrune. We discuss and extend those experiments in Appendix A.1.

Conclusions
In this work, we analyze the constraints introduced by fine-grained sparsity. We discuss the limitations of current research in the field and suggest a new measure called mask diversity to connect between the mask constraint and the accuracy of the network. In addition, we discuss the inherent problem of accelerating sparse training and suggest a novel N:M transposable-mask which enables accelerating the backward phase as well. We formulate the question of finding the optimal mask as a minimumcost-flow problem and show no accuracy degradation in a variety of tasks with 2x acceleration in comparison to previous methods [36]. We experimented with transposable-masks also in the setting of Zhou et al. [43] where pretrained model is not given but the mask is dynamically changing based on the gradients and a copy of the weights which are kept dense. In this setting we define an approximation scheme with an (almost) linear (in input-size) time complexity that produces a mask whose 1 -norm is within a factor of 2 from the optimal mask and allow 2x acceleration in comparison to Zhou et al. [43]. While a different line of research suggested more extreme setting which restrict the memory footprint to the compressed model size [4,29,30,7,9], we argue that our method is orthogonal to it and both methods could be easily be combined. We believe this work paves the path toward true efficient sparse training. Finally, we suggest a simple method (AdaPrune) to transform an unstructured sparse model to an N : M fine-grained sparse structured model with little to no training (e.g., less than 1% degradation in ResNet50). Furthermore, with a light training procedure over a calibration set (i.e., AdaPrune) we can switch from unstructured model to 4:8 structure sparsity and thus gain 2x inference speedup.
Broader impact. Training DNNs is an expensive process which requires a high amount of resources and time. This long time can prevent the use of DNNs in many applications, despite their impressive performance. Reducing training time gives the opportunity to to use of DNNs in additional applications, or even use the extra time to improve the existing models. We need to take into account that accelerated training could introduce training instabilities. These models will need a careful examination, specially when used in real applications, such as medical devices.
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's

A.1 Additional AdaPrune experiments
To further examine AdaPrune capabilities we checked two additional settings: (a) starting from pre-trained dense model, and (b) staring from less constrained N:M mask.

A.1.1 AdaPrune from Dense
While this case is more common, we expect to see some degradation as we know that we have 50% mask violations. Yet as can be seen in table 2 we managed to restore accuracy to 2-3% of the full-precision baseline using just AdaPrune. To further improve results we applied batch-norm-tuning as suggested by Hubara et al. [19] and kept the first and last layers dense which results in less than 2% degradation. We believe it to be the first tolerable post-training-pruning results reported. In Section 3 we explained why as the block size decreases the mask diversity decreases. Thus, we expect to have many violations when a pre-trained sparse model with N 1 : M 1 translates to N 2 : M 2 , for N 1 > N 2 and M 1 > M 2 . We argue that this might be a common case in the future as different hardware vendors would support different formats. In table Table A.2 we can see results of converting ResNet-50 model trained with 4 : 8 sparsity pattern to 2 : 4 and 1 : 2 patterns. As can be seen, converting from 4 : 8 to 2 : 4 produces results with negligible accuracy degradation (less than 0.5%). Therefore, we argue that AdaPrune is an efficient and useful approach to convert models which were optimized on a different hardware than the one in use, as it removes the need for full sparse training. This is even more important when the training data is not available.  We note that we can truncate the list of i at M/2, since if i has more than M/2 edges adjacent to it in P , then any such edge (i, j) would also appear in E(j) (among the first M/2 edges adjacent to j) by the minimality of the solution P . Thus, the union of the lists E(i) contains all edges in P . We now prove by induction that for any n, n ≥ 1, w(e n ) ≤ w(e n ). (A.2) • Base case (n = 1): w(e 1 ) ≤ w(e 1 ), since by construction of Algorithm 1, edge e 1 is the lightest edge adjacent to node i.
• Inductive step: assume w(e n ) ≤ w(e n ), then it must hold that w(e n+1 ) ≤ w(e n+1 )); otherwise, if w(e n+1 ) > w(e n+1 )), then e n+1 should have been considered before e n+1 and also chosen by Algorithm 1. Thus, To complete the proof, our goal is to charge the weight of the edges in P to the weight of the edges in the optimal solution based on the above inequality. However, note that an edge (i, j) ∈ P may appear in only one of the lists E(i) or E(j). Thus, for example, two edges in P , (i, j) and (i , j), may charge their weight to the same edge (i, i ) in the optimal solution. Clearly, this "double" charging can happen at most twice for each edge in the optimal solution, hence: In the following, we show that our analysis of the upper bound of 2 on the approximation factor (proved in the lemma) is asymptotically tight. Consider the example in Fig. A.1c. Let us assume we want to zero out one element in each row and column in the block of size 4 × 4 presented in Fig. A.1a using the 2-approximate algorithm (Algorithm 1). First, we need to convert the block into a bipartite graph (as suggested in Figure 4). This construction appears in Fig. A.1b. Next, we sort the the edges from light to heavy and go over the sorted list. In Fig. A.1c we show the seven iterations of the 2-approximate algorithm. All edges are added to the list of chosen edges P up until the 7th iteration. The algorithm stops at the 7th iteration, since after adding edge u 4 1 − → v 4 , every node is already "covered" by at least one edge (in other words, each row and each column has at least one entry chosen for pruning). Note that the optimal solution would choose the edges that correspond to the entries on the diagonal (i.e., u 1 , summing up to a total weight of 4. Hence, we get an approximation ratio of 7 4 . It is easy to see that when using the same construction for a general block of size M × M , we get an approximation ratio of 2M −1 M , asymptotically converging to 2 as M goes to infinity.

A.3 Min cost flow vs. 2-approximation run-time analysis
In this section we specify the complexity of different min-cost flow methods and compare them with the running time of our 2-approximation method. Ahuja et al. [1] specifies the running times of six min-cost flow algorithms, two of which have distinctively better performance for our construction compared to the others (see Ahuja et al. [1][pp. 396-397]). The running time of these two methods depends on the following parameters: number of nodes n, number of edges m, the largest weight coefficient W , and the flow demand U . The Goldberg-Tarjan algorithm and the double scaling algorithm have running times ofÕ(mn), whereÕ hides polylogarithmic factors. Thus, in our construction, for a block of size M × M the number of edges is M 2 + 2M , the number of nodes is 2M + 2, and the flow demand is 0.5M 2 . This boils down to running times ofÕ(M 3 ) for finding an optimal mask.The running time of the 2-approximation algorithm in comparison isÕ(M 2 ). In Table A.3 we show the running time overhead of ResNet50 training using 2:4 transposable mask with IP, min cost flow and 2-approximation algorithms over regular training. These overheads are smaller than what we measured for 4:8 (Table 2). These methods were implemented in a non-optimized way, therefore, we expect a further decrease of the overhead in the 2-approximation in an optimized algorithm.  The 7 iterations of the 2-approximation algorithm on the bipartite graph. Notice that we get an approximation ratio of 7 4 , since the optimal solution picks only the diagonal entries.

A.4 Experiments Setting
In all our experiments we use 8 GPU GeForce RTX 2080 Ti.
AdaPrune We used a small calibration set of 1000 images (one per-class). We run AdaPrune for 1000 iterations with batch-size of 100. For the results in the supplementary material, we kept the first and last layers dense.
N:M transposable sparsity mask from a pre-trained model We used torchvison [28] model-zoo as our pre-trained dense baseline. For all ResNet models we used the original regime as given by He et al. [16], i.e., SGD over 90 epochs starting with learning rate of 0.1 and decreasing it at epochs 30,60,80 by a factor of 10. For BERT-large and MaskRCNN we used the defaults scripts as in Nvidia [35].
N:M transposable sparsity mask from scratch We use the exact same setting as given by Zhou et al. [43].

A.5 N:M hardware requirements
For conventional hardware, Broadly, N:M sparsity requires adding an N+1 to 1 multiplexer (N+1:1)to the adder tree in the code of the matrix multiplication. engine. Thus switching from 2:4 fine grained sparsity to 4:8 requires 5:1 multiplexers instead of 3:1. The simplest implementation of a multiplexer is build of set of 2:1 multiplexers which means that the area required for the multiplexers scale logarithmicly with the number of zeros in the block (N).

A.6 Mask diversity Derivation
Let us consider W to be a block of size n × n from a weight tensor and our desired sparsity level to be N/M . Thus, the MD of unstructured sparsity consists of all possibilities to pick N values out of B (Eq. (2) (a)). The MD increases with the block size (B), which might explain the recent success of global pruning. Next we investigate, fine-grained N : M structured sparsity [36]. This approach requires us to zero out N values in each block of size M . Since we have T M blocks this results in Eq. (2) (b). If we wish to enforce the constraints on both row and columns of the matrix (i.e., N : M transposable structured) the diversity decreases. Let us first assume N = 1. The number of possibilities in each block of size M 2 is M !. Repeating this process for general N in all the B M 2 blocks results in Eq. (2) (c). A more constrained mask, is a fine-grained N : M mask with a sequential structure. Here we require that each M contiguous elements would contain N sequential zeros. In each block of size M 2 , there are M − N + 1 options of sequential zeros. Applying it on all the B M blocks results in Eq. (2)(d).

A.7 Mask diversity Experiments
In additional to the results in Section 3 we experimented in Fig. A.2 with ResNet50 over ImageNet dataset. In all our experiments we used one-shot pruning from dense model and applied the same regime as the original training as suggested by Nvidia [36].

A.8 2:4 transposable mask
In Table A.4 we show experiments with the 2:4 transposable mask in the "training from scratch" setting. Moreover, after we published the first version of our paper, researchers from NVIDIA [39] continued our work and demonstrated on a large set of models that one can achieve less than 1% degradation even with 2:4 transposable masks in the "training from a trained dense model" setting. As can be seen, 2:4 transpose mask can achieve high accuracy in part of the models. This results correlates with the shown MD, since 2:4 transpose mask has similar MD to 1:2 mask which already achieved high accuracy (Fig. A.2