Memory Efficient Dynamic Sparse Training
Authors: Mike Heddes
Narayan Srinivasa
Venue: Submitted to ICLR 2023 (2023)
Keywords: Dynamic Sparse Training
Sparse Neural Networks

Abstract: The excessive memory and energy consumption of modern Artificial Neural Networks (ANNs) is posing limitations on the machines that can run these models. Sparsification of ANNs is often motivated by time, memory and energy savings only during model inference, yielding no benefits during training. A growing body of work is now focusing on providing the benefits of model sparsification also during training. While these methods improve the energy efficiency during training, the algorithms yielding the most accurate models still have a peak memory usage on the same order as the dense model. We propose a Dynamic Sparse Training (DST) algorithm that reduces the peak memory usage during training while preserving the energy advantages of sparsely trained models. We evaluate our algorithm on CIFAR-10/100 using ResNet-56 and VGG-16 and compare it against a range of sparsification methods. The benefits of our method are twofold: first, it allows for a given model to be trained to an accuracy on par with the dense model while requiring significantly less memory and energy; second, the savings in memory and energy can be allocated towards training an even larger sparse model on the same machine, generally improving the accuracy of the model.

Under review as a conference paper at ICLR 2023
MEMORY EFFICIENT DYNAMIC SPARSE TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
The excessive memory and energy consumption of modern Artificial Neural Net- works (ANNs) is posing limitations the machines that can run these models. Sparsification of ANNS is often motivated by time, memory and energy savings only during model inference, yielding benefits during training. A growing body of work is now focusing on providing the benefits of model sparsification also during training. While these methods improve the energy efficiency during training, the algorithms yielding the most accurate models still have a peak mem- ory usage on the same order as the dense model. We propose Dynamic Sparse Training (DST) algorithm that reduces the peak memory usage during training while preserving the energy advantages of sparsely trained models. We evaluate our algorithm on CIFAR-10/100 using ResNet-56 and VGG-16 and compare it against range of sparsification methods. The benefits of our method are twofold: first, it allows for given model to be trained to an accuracy on par with the dense model while requiring significantly less memory and energy; second, the savings in memory and energy can be allocated towards training an even larger sparse model on the same machine, generally improving the accuracy of the model.
INTRODUCTION
Artificial Neural Networks (ANN) are currently the most prominent machine learning method be- cause of their superiority in broad range of applications, including computer vision (O'Mahony et al. 2019; Voulodimos et al. 2018 Guo et al. 201 natural language processing (Otter et al.,
2020
Young et 20,00 and reinforcement learning (Schrittwieser et al. 2020) Aruikumaran et al,
2017
among many others (Wang et al., 2020 Zhou al.) 2020 Liu et al. (217)) However, as ANNs keep increasing in size to further improve their representational power (Du et al. 2019) No-
vak al. 2018), the memory and energy requirements to train and make inferences with these
models becomes a limiting factor (Hwang) 2018 Ahmed & Wahed 2020).
The scaling problem of ANNs is most prominent in the fully-connected layers, the dense part of an ANN that includes multiplication with a weight matrix that scales quadratically with the number of units, making very wide ANNs infeasible. This problem exacerbated ANNs learn from high- dimensional inputs such as video and spatial data (Garcia-Garoia et al., 2018 Ma et al., 2019) and produce high-dimensiooal representations for many-classes classification or generative models for images and video (Mildenhall et al.) 202T Ramesh et al. 2021), all of which are gaining importance.
A large body of work has addressed the scaling problem (Reed] 1993 Gale al. 2019 Blalock al.
2020 Hoefler et al.) [021], many studies look into sparsity of the weight matrix as solution based on the observation that the weight distribution of dense model the end of training often has a peak around zero, indicating that the majority of weights contribute little to the function being computed (Han et al.] 2015). By utilizing sparse matrix representations and operations, the floating- poiint operations (FLOPS), and thus the energy usage, of a model can be reduced dramatically. Biological neural networks have also evolved to utilize sparsity, which is seen as an important property for
learning efficiency (Pessoa 2014 Bullmore & Sporns 2009 Watts & Strogatz 1998).
Early works in ANN sparsity removed connections, a process called pruming, of a trained dense model based the magnitude of the weights (Janowsky 1989: Ström 1997), resulting in a more efficient model for inference. While later works improved upon this technique (Guo et al. 2016b] Dong al. 2017 Yu et al. 2018), they all require least the cost of training a dense model, yielding

---

Under review as a conference paper at ICLR 2023
no efficiency benefit during training. This limits the size of sparse models that can be trained given machine by the largest dense model it can train.
In light of this limitation, the Lottery Ticket Hypothesis (LTH) (Frankle & Carbin 2018 surpris- ingly, hypothesized that there exists a subnetwork within a dense pvor-parameterized model that when trained with the same initial weights will result in a sparse model with comparable accuracy to that of the dense model. However, the proposed method for finding Winning Ticket within a dense model is very compute intensive, as it requires training the dense model (typically multiple times) to obtain the subnetwork. Morover, later work weakened the hypothesis for larger ANNs (Frankle) al. 2019). Despite this, was still an important catalyst for new methods that aim to find the Winning Ticket more efficiently.
Efficient methods for finding a Winning Ticket can be categorized as: pruning before training and Dynamic Sparse Training (DST). The trainig methods prune connections from randomly initialized dense model (Lee et al. 2018 Wang et al., 2019. Tanaka al.) 2020). In contrast, the DST methods start with randomly initialized sparse model and change the connections dynami- cally during training, maintaining the overall sparsity (Mocanu et al. 2018 MMostaaa & Wang 2019, Evei et al.) 2020). In practice, DST methods generally achieve better accuracy than the pruning before training methods (Wang et al., 2019). In addition, the DST methods do not need to represent the dense model at any point, giving them a clear memory efficiency advantage, important prop- erty for our motivation. The first DST method was Sparse Evolutionary Training (SET) (Mocanu et al.) 2018). SET removes the connections with the lowest weight magnitude, common pruning strategy (Mostafa & Wang 2019; Dettmers & Zettlemoyer 2019 Evei et al. (020), and grows new connections uniformly random. RigL (Evci et al.) 2020) improved upon SET by growing the con- nections with the largest gradient magnitude instead. These connections are expected to get large weight magnitudes as a result of gradient descent optimization.
magnitude
While these methods drastically reduce the FLOPS required to train sparse models, the pruning before training methods and RigL share an important limitation: they have peak memory usage during training on the same order as the dense model. This is because the pruning before training methods use the dense randomly initialized model, and Rigl. requires the periodic computation of the gradient with respect to the loss for all possible connections. We present DST algorithm that reduces the peak-memory usage to the order a sparse model while maintaining the improvements in compute and achieving the same accuracy RigL. We achieve this by efficiently sampling subset of the inactive connections using heuristic of the gradient magnitude. We then only evaluate the gradient this subset of connections. Interestingly, the size of the subset be the same order as the number of active connections, therefore reducing the peak memory to the order of the sparse model. We evaluate the accuracy of our method CIFAR-10/100 using ResNet-56 and VGG-16 models and compare it against a range of sparsification methods at sparsity levels of 90%, 95%, and 98%. The benefits of our method can be utilized in the following two ways:
1. It allows for given model to be trained to an accuracy on par with the dense model while requiring significantly less memory and energy.
2. The savings in memory and energy can be allocated towards training an even larger sparse model on the same machine, generally improving the accuracy of the model.
2 RELATED WORK
A variety of methods have been proposed that aim to reduce the size of ANNs, such as dimension- ality reduction of the model parameters (Jaderberg et al., 2014 Novikov et al. 2015), and weight quantization (Gupta et al. 2015)] Mishra et al.) 2018). However, we are interested in model sparsifi- cation methods because they reduce both the size and the FLOPS of a model. Following Wang et al. (201),, categorize the sparsification methods pruning after training, pruning during training, pruning before training, and Dynamic Sparse Training.
After training The first pruning algorithms operated on dense trained models, pruning the connec-
tions with the smallest weight magnitude (Janowsky 1989; Thimm & Fiesler 1995] Ström 1997
Han et al. 2015). This method was later generalized to first-order (Mozer & Smolensky 1988
Kamnin 1990] Molchanov et al. 2019a b) and second-order (LeCun et al.] 1989 Hassibi & Stork
2

---

Under review as a conference paper at ICLR 2023
Taylor polynomials of the loss with respect to the weights. These methods can be interpreted as calculating an importance score for each connection based on how its removal will effect the loss (Guo et al. 2016b; Dong al. 2017 Yu et al. 2018).
1992)
During training Gradual pruning increases the sparsity of the model during training till the de- sired sparsity is reached (Zhu & Gupta 2017; Liu et al.) (021a). Kingma et al. (2015) introduced variational dropout which adapts the dropout rate of each unit during training. Molchanov et al. (017)) showed that pruning the units with the highest dropout rate is an effective way to sparsify a model. [ooizoo al. (2018) propose a method based on the reparameterization trick that allows to directly optimize the -nrmo,, which penalizes the number of non-zero weights. Alternatively, DeepHoyer is a differentiable regularizer with the same minima the L"-norm Yang al. 2019
Before training The Lottery Ticket Hypothesis (LTH) (Frankle & Carbin 2018 Frankle et al. 2019) started a line of work that aims to find sparse model by pruning dense model before training (Liu et al. 2018). SNIP (Lee et al. 2018) uses the sensitivity of each connection to the loss as the importance score of a connection. GraSP (Wang et al., (019) optimizes gradient flow to accelerate training, however, Lubana & Dick (2200) argue that preserving gradient flow instead is a better approach. Tanaka et al. (2020) highlight a problem in the aforementioned methods: they suffer from layer collapse in high sparsity regimes, that is, during the pruning phase all the connections of layer can be removed, making the model untrainable. They propose SynFlow, which prevents layer collapse by calculating how each connection contributes to the flow of information using a path regularizer (Neyshabur al. 2015b), similar to (Lee et al. 2019).
Dynamic Sparse Training The methods in this last category, including ours, maintain the same sparsity throughout training but periodically rewire a fraction of the active connections. This in- volves periodically pruning fraction of active connections, followed by growing the same number of inactive connections. SET (Mocanu et al. 2018) was the first method and used simple magni- tude pruning and random growing of connections. DeepR (Bellec et al. 2018) assigns a fixed sign to each connection at initialization and prunes those connections whose sign would change during training. DSR (Mostafa & Wang 2019) prunes connections with the lowest global weight mag- nitude and uses random growing, allowing the connections to be redistributed over the layers and used in layers where they contribute the most. SNFS (Dettmers & Zettlemoyer 2019) improves upon the previous methods by using an informed growing criteria: it grows the connections with the largest gradient momentum magnitude. RigL (Evci et al. (0200) makes this more efficient by only periodically calculating the gradient with respect to all possible connections. We propose another efficiency improvement by only calculating the gradient periodically on a subset of the connections.
3 METHOD
While RigL (Evci et al. 2020 is currently the best DST method in terms of accuracy and efficiency, it has an important limitation: it evaluates the gradient magnitude with respect to the loss for every possible connection during the growing step. This means that it requires enough memory to store a gradient for every possible connection, which is the same as the memory requirement for storing the dense model. This is important because the memory requirements dictate the machine that can train a model. Our main contribution is a more efficient growing algorithm in terms of compute and memory. Specifically, we only calculate the gradients on a subset S C W of all possible connections W. illustrated in Figure I] Periodically, the subset is randomly sampled during each growing step from probability distribution based on a heuristic of the gradient magnitude. In this section we explain which heuristics were considered and how to efficiently sample from their distributions in the case of aally-oonnected layers. We provide discussion in Appendix C on how to apply these heuristics to convolutional layers.
Perhaps the simplest heuristic is to sample the subset S from a uniform distribution over the inactive connections W A. where A denotes the set of active connections. A connection E W is fully specified by the input and output units it connects, i.c., (a, b) = e. Thus, to ensure an efficient sample connections at random by independently sampling from distribu- tions over the input and output units of a layer, which is equivalent to a joint probability distribution over all the connections in the layer. This ensures that the probability of sampling each connection
sampling process,
3

---

Under review as a conference paper at ICLR 2023
S
IP
P
A
S
G
G
W
W
The illustrated set sizes of pruning and growing round in RigL (left) and method (right). Where W is the set of all possible connections, the set of active connections, the set of pruned connections, G the set of grown connections, and & the subset of inactive connections. The gray solid filled area becomes the set of active connections at the next time step.
Figure 1:
never explicitly represented, only the probability of sampling each unit is represented, which is more efficient. Formally, create the subset sample from the discrete uniform distributions over the input and output units of layer such that the sampled connections are not active connections:
0g ~ 1,.,......"111 n b, ~ 1=.1......n
s.t. (a:, b.) $ A
(1)
where nl denotes the number of units in the (-th layer. Note that abuse the notation of the various connection sets to be per layer or global interchangeably. Interestingly, sampling the subset uniformly random in this way be is equal to the size of the set of grown connections |G] it simplifies to SET and when [S] is equal to the number of possible connections |W| it simplifies to RigL.
the interpolation between SET and RigL. when
In general, we sample the endpoints of the connections in the I-th layer from the discrete probability distributions a; { and 6; gl!ll such that the sampled connections are not active connections. In this general setting, the distributions and g don't 't need be uniform, might instead be useful to bias the subset towards connections that are more likely to have large gradient magnitude and therefore serve as better heuristic. To this end, we investigate two other distributions: the first uses the gradient of synaptic flow which measures how much an inactive connection would contribute to the overall connectivity of the model; and the second uses an upper bound of the gradient magnitude. In Section 4.2 we assess which of these heuristics is most appropriate for training sparse models.
3.1 SYNAPTIC FLOW (SYNFLOW)
First introduced by Neyshabur et al. 2015b),, the path regularizer measures the contribution of each connection to the overall synaptic flow, for example, a given connection contributes more when has strong afferent and efferent connections, even though its weight might not be particularly large. used train unbalanced ANNs
This regularizer the context of model sparsification, Tanaka et al. (2020) used the path regularizer R()) in Equation 2 Their pruning before training algorithm, named SynFlow, prunes connections using generalization of the weight magnitude M (0) with the goal of preventing layer collapse. We use f to denote all the parameters and use d!4l as the notation for the sparse weight matrix of the 1-th layer.
effectively (Neyshabur et al.) (0155)). In
R(0) 1"
II 0 )1,
M(0)
OR(0)
2
a0
Our motivation differs from that of Tanaka et al. (2020). We are interested in SynFlow because the connectivity unit can be used as a heuristic the gradient magnitude. Intuitively, a connection with strong synaptic flow to its input unit and from its output unit is more likely to have a large gradient magnitude. This due to the gradient information propagating over those same strong connections. From the perspective of a single layer, we sample an input unit proportionally to its afferent synaptic flow and an output unit proportionally to efferent synaptic flow as follows:
1
(0()))
( |00|
g
(3)
1 [T [144
4

---

Under review as a conference paper at ICLR 2023
The SynFlow heuristic only requires single forward and backward pass to evaluate the afferent and efferent synaptic flow for all layers. This is achieved by creating a copy of the model whose weights take the absolute value of the original weights and passing it an all ones input vector. In addition, the nonlinearities of this model copy need to be linear in the positive domain.
3.2 GRADIENT MAGNITUDE UPPER BOUND (GRABO)
Since we are ultimately interested in finding the inactive connections with the largest gradient mag- nitude, sampling connections with probability proportional to their gradient magnitude would be an ideal heuristic. The gradient magnitude for a single connection can be expressed as follows:
B Σ
Vola
(1 8
vol 0.b
h
(4)
where h and 8t are the activation and gradient of the loss at the output units of the 1-th layer, respectively. This simplifies to then be used to sample connections efficiently according to:
1.b
when the hatch size B is 1. The simplified expression
1--1 !]
! 1 1T
g
(5)
h
This induces a joint probability distribution that is proportional to the gradient magnitude only when the batch size is 1. In practice, however, training samples come in mini batches during gradient descent in order to reduce the variance the gradient. This means that Equation 5 does not induce the correct distribution.
Instead, we sample connections proportionally to the following upper bound of the gradient magni- tude which enables efficient sampling, even with mini batches:
B
v
=
12
80
Σ
[-=1]] he
Σ
6!!!!
(6)
The proof for Equation 6 involves the triangle inequality and is provided in Appendix D tions are then sampled from the following probability distributions:
Connec-
B
[-1]]
Σ
1
I
g
Σ
Σ
B
This particular upper bound has the property that Equation simplifies to Equation when = 1. The implementation of this heuristic has the advantage that it does not require any modifications to the model, as is the case with the SynFlow heuristic. Yet it still only requires single forward and backward pass evaluate the distributions.
EXPERIMENTS
At this point, the foremost question is: what is the minimum size the subset that maintains the maximum accuracy? We answer this question in Section 4.2 and then compare the accuracy of our method against other sparsification methods the relation between the width of a model and its accuracy while keeping the number of active connections constant across all model widths by increasing the sparsity of wider models.
Section
Lastly, in Section 4.4 we explore
4.1 EXPERIMENT SETUP
We evaluate method and compare it to baselines the CIFAR-10 and CIFAR-100 datasets (Krizhessky et al. 2009). To establish how each method compares across model architectures we experiment with ResNet-56 (He et al. 2016) and 4 times downscaled version of VGG-16

---

Under review as a conference paper at ICLR 2023
(Simonyan & Zisserman 2014) such that both models have roughly the same number of parameters. The bias and batch- satch-norm norm parameters are kept dense since they only contribute marginally to the size of the model. We repeat each experiment times across different seeds and report the mean and plot the 95th percentile. We adopt the implementation of the baselines based on their available code.
All experiments the same optimization settings in order to isolate the differences in sparsifi- cation. Similar to Evci et al. (2220) and Lubana & Dick (2020), we use SGD with a momentum coefficient of 0.9, an L regu reguulariattonn coefficient of 0.0001, and an initial learning rate of 0.1 which is dropped by a factor of 10 at epochs 80 and 120. We use a batch size of 128 and train for a max- imum of 200 epochs. Training stops early when the loss does not improve for 50 epochs. We also apply standard data augmentation to the training data, including random flips and crops.
The LTH procedure described by Frankle & Carbin (2018), denoted Lottery in the results, uses iterative pruning with iterations at 0%, 50%, 75%, 90%, 95% and 98% sparsity. The gradual pruning method by Zhu & Gupta (2017). denoted as Pruning in the results, reaches the target sparsity the second learning rate drop and prunes connections every 1000 steps. The pruning before training methods use one iteration over all the training data to prune the dense model to the target sparsity. All the DST methods use the same update schedule: the connections are updated every 1000 steps, and similar to Evci et al. (2020), the fraction of active connections that is pruned is cosine annealed from 0.2 to 0.0 at the second learning rate drop. This is because Liu al. (2021a) showed that DST methods struggle to recover from pruning when the learning rate low.
It is important to note, given motivation, that the DST methods initialize the sparse model in way that does not require to represent or store the dense model at any time. In particular, each layer initialized random bipartite graph using the Erdös-Rényi G(n, M) random graph generation algorithm (Erdös & Rényi 1959). The weights of the random sparse model are initialized using the procedure proposed by Evci et al. (2019) which adapts standard weight initialization take into account the actual fan-in of each unit in order to properly scale the weight distribution for each unit.
Although the sparsity at initialization assigned uniformly all the layers, the pruning and grow- ing procedures are applied globally. This means that the pruned connections are dynamically redis- tributed across layers throughout training, maintaining the overall sparsity. This approach generally outperforms local, layer-wise sparsity (Mostafa & Wang 2019). To ensure stable training we found that it is important to sample the subset layer-wise, i.e., the subset size of a layer is proportional to the size of W of that layer. The grown connections are then taken globally again as the connections among all subsets that have the largest gradient magnitude.
4.2 SIZE OF THE SUBSET
First, want to determine how the size of the subset affects the accuracy. In addition, interested in comparing the accuracy obtained by the three heuristics. The size of the subset is set proportionally to the number of pruned connections [P/, with S being {1, 2, 4, 6, 8, 10) times IP]. Note that when [$] = |P| [G], i.e., when the multiplier is one, our method is identical to SET in the case of the random heuristic. The results are shown in Figure 2
w where the size of the subset is expressed as fraction of |W] instead. The results include the bascline accuracy of SET and RigL. The extended results in Appendix show the same trends and include 90% and 95% sparsity.
Rigl Ref.
SET Ref.
Random
SyuFoow
GiaBo
ResNet-36 on CIFAR-10
CIFAR-IU
ResNet-56 CIFAR-
VGG-16 CIFAR-100
0.825
0.365
0.375
0.600
0.775
0.750
0.46
0.225
0.44
0.275
Fruction of connections
Praction of connections
Praction of connectious
Fraction of connections
Figure 2: The accuracy of the heuristics while increasing the subset size S as a fraction of [W]. Showing ResNet-56 and VGG-16 models trained on the CIFAR-10/100 datasets with 98% sparsity.

---

Under review as a conference paper at ICLR 2023
Remarkably, it is enough for the subset to contain only 3% of all the connections and still consis- tently achieves the accuracy of RigL. This is on the same order of connections as the number of active connections, thus reducing the peak memory usage to that the order of the sparse model. The same trend appears among all the heuristics, but in general the GraBo heuristic reaches the max- imum accuracy smaller subset sizes. The SynFlow heuristic, in turn, outperforms the Random heuristic, indicating that our method indeed benefits from using informed heuristics. Interestingly, with ResNet-56 our method outperforms RigL when the subset size contains 4% of all the connec- tions, however, this trend is not present for VGG- 16 nor does it appear at lower sparsity levels where the accuracy of our method on par with RigL.
4.3 COMPARISON WITH RELATED WORK
We also compare our method to a broad range of sparsification methods in Table The Random method denotes training a static random sparse model, and SynFlow (Tanaka et al. 2020 is the pruning before training method, not to be confused with our method and the SynFlow heuristic. The other baselines are Lottery (Frankle & Carbin 2018), Pruning (Zhu & Guptal 2017). SNIP (Lee) jet al. 2018), GraSP (Wang et al. 2019). GraSP] (Lubana & Dick] 2020). SET (Mocanu et al., 2018 and RigL (Evci et al. 22200) ) Our results in Table use the GraBo heuristic with the subset size being 10 times the number of pruned connections.
Table Top-1 accuracy of ResNet-56 and VGG-16 on CIFAR-10 and CIFAR-100
Dataset
CIFAR-10
CIFAR-100
Model
ResNet-56
VGG-16
ResNet-56
VGG-16
Dense
91.87
89.31
68.80
62.50
Sparsity
90%
95%
98%
90%
95%
98%
90%
95%
98%
90%
95%
98%
Lottery
89.18
87.90
84.40
87.82
86.12
82.42
61.58
57.44
48.82
53.67
48.10
38.36
Pruning
90.20
89.09
86.71
88.52
87.70
86.20
66.62
63.77
57.13
57.89
55.20
45.93
Random
88.85
86.88
73.98
83.11
77.59
58.95
60.68
51.64
31.43
46.83
37.39
21.29
SNIP
89.89
88.29
84.67
87.15
84.19
72.78
62. 15
56.33
43.48
52.80
45.85
16.09
GraSP
87,48
86.58
81.8 8.88
85.97
84.58
80.24
58. 13
52.78
37.83
51.56
46.45
35.19
GraSP]
89.19
87.51
82.04
85.89
82.10
34.73
42.60
22.38
11.74
52.04
44.25
01.00
SynFlow
89.70
88.42
85.14
87.72
85.78
80.03
61.79
54.06
35.27
53.04
47.25
35.02
SET
89,89
88.29
84.67
86.10
83.34
73.12
63,90
58.04
45.91
52.77
44.82
29,82
Rigl.
90.55
89.29
85.62
88.33
86.24
81.09
64.91
59.88
49.00
54.82
49.01
37.16
Ours
90.56
89.29
86.08
87.80
86.14
80.58
64.72
60.05
49.14
54.76
48.68
37.17
Among the sparse training methods (from Random downwards in T our method and RigL out- perform the other methods consistently over all datasets, sparsities, and model architectures. While at 90% sparsity all the methods achieve comparable accuracy, at the extreme sparsity rate of 98%, differences between methods become more evident. We see that gradually pruning connections dur- ing training (Pruning) can improve the accuracy quite significantly. especially in the extreme sparsity regimes. However, this comes at the cost of training the dense model, thus requiring significantly more memory and energy. We see this as motivation for research into sparse training methods which further increases their accuracy while preserving their efficiency advantage.
4.4 THE VALUE OF DIMENSIONS
In our final experiment we investigate how the width of the model affects the accuracy when the number of active parameters is kept constant. The width is used to multiply the number of filters in convolution layers and units in fully-connected layers. The results are presented in Table
While basic machine learning theory tells us that the complexity of function is directly related to the number of parameters, the results indicate that there are ways to use a certain parameter budget more effectively. Another classical example of this is the convolutional layer, its success stems from its parameter efficiency by consistently outperforming tully-connected layers with the same number of parameters in vision tasks. However, important distinction with sparse methods is that there is
7

---

Under review as a conference paper at ICLR 2023
Table Effect of network width on CIFAR-100
Model
ResNet-566
VGG-16
Width
|W|
Sparsity
Top-1 acc.
W
Sparsity
Top-1 acc.
1.0
0.9M
0%
68.80
0.9M
0%
62.50
1.5
1.9M
55%
71.46
2.1M
55%
65.86
2.0
3.4M
75%
72.07
3.8M
75%
67.18
5.3M
84%
72.56
5.9M
84%
67.86
3.0
7.6M
89%
72.21
8.4M
89%
68.37
3.5
10.4M
92%
72.75
11.5M
92%
68.32
4.0
13.6M
94%
72.70
15.0M
94%
68.45
no inherent bias from human design, i.c., the active connections are found as result of the training process and hand crafted the case with convolutional layers.
Moreover, the results indicate that enabling training of larger models on the same machine because of the memory and compute savings of our method translates increased accuracy (up to a certain sparsity level). These findings are similar to those from Zhu & Gupta (2017), however, our method enables sparse model be trained whose dense version would not fit on given machine, enabling any given machine to train more accurate models.
DISCUSSION
We conjecture that the higher accuracy achieved by gradual pruning (Zhu & Gupta 2017) is, at least partly, because considers the entire connection search space, whereas method and RigL use greedy exploration algorithm, the gradient magnitude. This topic has been investigated by Liu et al. (222aa b), who improve the performance of RigL by increasing the search space. We consider these extensions orthogonal to our work as they benefit from incorporating our method as well.
Mocanu et al. (2018) and Evei al. 2020) differentiate between three sparsity distribution strate- gies: uniform, Erdos Rényi, and Erdös Rényi-Kernel, The later two are for fully-connected and convolutional layers, respectively, and assign a relative higher sparsity to layers with many possible connections. For simplicity, our experiments use uniform sparsity distribution but we note that our method works with any of the improved sparsity distributions.
Like many other methods, we use magnitude pruning throughout training. With pruning before training. layer collapse has been observed as a result of magnitude pruning when a model pruned to high levels of sparsity. Tanaka al. (2020) investigated layer collapse and found that the training process is implicitly regularizing the magnitudes of the connections which minimizes the risk of layer collapse during DST. In addition, magnitude pruning is also very efficient, finding the top-k among a set of weights has complexity of O( log [P]).
Like Dettmers & Zettlemoyer (2019), implementation is build using PyTorch and uses masked weights to simulate sparse neural networks. This because support for sparse matrix operations in machine learning frameworks is currently incomplete. We therefore cannot provide any concrete measurements on memory savings. We leave it to follow up studies to implement our method in an efficient sparse manner evaluate the practical memory savings of our method. Our work focuses on the theoretic and algorithmic aspects of more memory efficient dynamic spare training method.
Lastly, we provide plots of the layer-wise sparsity of every method on each model, dataset, and at sparsity levels of 90%, 95%, and 98%. This information provides insight into how each method distributes the available connections over the layers of a model. Since this data is not essential the conclusion of our paper we provide them supplementary material in Appendix
CONCLUSION
We present a dynamic sparse training algorithm that reduces the peak memory during training while maintaining the same accuracy the current best methods. This is achieved by only evaluating the
8

---

Under review as a conference paper at ICLR 2023
gradient for subset of the connections instead of all possible connections. Our method achieves the same accuracy while evaluating the gradient for only 3% of the connections at 98% sparsity. The connections in the subset are sampled proportionally to heuristic of the gradient magnitude. We compare three heuristics: uniform, the gradient of synaptic flow, and the upper bound of the gradient magnitude. We find that the upper bound of the gradient magnitude generally reaches the maximum accuracy at smaller subset sizes. In addition, the GraBo heuristic is also easier to implement as doesn't I require model copy, like the SynFlow heuristic, therefore we conclude that the GraBo heuristic is the most appropriate for sparse training. Lastly, we show that the savings in memory and compute can be allocated towards training even wider models to achieve better accuracy. Our method reduces the peak memory usage to the order of sparse gradient update, enabling given model to be trained on a machine with less memory.
REPRODUCIBILITY
To ensure reproducability used standard model architectures and stated any modifications in Section 4.1 We used the CIFAR-10/100 datasets with their train and test split as provided by the Torchvision library. The optimizer settings are stated in Section 4.1 The data normalization and augmentation settings are specified in Appendices A and B respectively. We provide proof of the gradient magnitude upper bound used in Section 3.2 in Appendix D The procedure for sampling the subset in convolutional layers is described in Appendix C. Additional implementation details are provided in Appendix G Our aim is to open source the code for the experiments but as of the paper deadline this is pending legal approval.
REFERENCES
Nur Ahmed and Muntasir Wahed. The de-democratizzatin of ai: Deep learning and the compute divide artificial intelligence research. arXiv preprint arXiv:2010. 2222000..558... 1558I, 2020.
Kai Arulkumaran, Mare Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. Deep rein- forcement learning: A brief survey. IEEE Signal Processing Magazine, 34(6):26-38, 2017.
Guillaume Bellec, David Kappel. Wolfgang Maass, and Robert Legenstein. Deep rewiring: Training very sparse deep networks. In International Conference on Learning Representations, 2018.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? Proceedings of machine learning and systems, 2: 121-9144, 2020.
Ed Bullmore and Olaf Sporns. Complex brain networks: graph theoretical analysis of structural and functional systems. Nature reviews neuroscience, 10(3):186-199) 2009.
Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance. arXiv preprint 1rXiv: 00000004444 2019.
Xin Dong, Shangyu Chen, and Sinno Pan. Learning to prune deep neural networks via layer-wise optimal brain surgeon. Advances in Neural Information Processing Systems, 30, 2017.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pp. 1675- 1685. PMLR, 2019.
Paul Erdös and Alfréd Rényi. On random graphs i. Publicationes Mathematicae Debrecen, 6:290, 1959.
Utku Evei, Fabian Pedregosa, Aidan Gomez, and Erich Elsen. The difficulty of training sparse neural networks. arXiv preprint arXiv:1906. 10732, 2019.
Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference Machine Learning, pp. 2943-2952. PMLR, 2020.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference Learning Representations, 2018.

---

Under review as a conference paper at ICLR 2023
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Stabilizing the lottery ticket hypothesis. arXiv preprint arXiv:1903.01611 2019.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint (rxxiv:902.009777 2019.
Alberto Garcia-Garcia, Sergio Orts-Escolano, Sergiu Oprea, Victor Villena-Martinez, Pablo Martinez- Gonzalez, and Jose Gardia-Rodriguez. A survey on deep learning techniques for image and video semantic segmentation. Applied Soft Computing, 70:41-65, 2018.
Yanming Guo, Yu Liu, Ard Oerlemans, Songyang Lao, Song Wu, and Michael S Lew. Deep learning for visual understanding: A review. Neurocomputing, 187:27-48, 2016a.
Yiwen Guo, Anbang Yao, and Yurong Chen. Dynamic network surgery for efficient dnns. Advances in neural information processing systems, 29, 2016b.
Suyog Gupta, Ankur Agrawal. Kailash Gopalakrishnan, and Pritish Narayanan. Deep learning with limited numerical precision. In International conference machine learning, pp. 1737-1746. PMLR, 2015.
Song Han, Jeff Pool, John Tran, and William Dally, Learning both weights and connections for efficient neural network. Advances in neural information processing systems, 28, 2015.
Babak Hassibi and David Stork. Second order derivatives for network pruning: Optimal brain surgeon. Advances in neural information processing systems, 1992.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. J. Mach. Learn. Res., 22(241):1-124, 2021.
Tim Hwang. Computational power and the social impact of artificial intelligence. arXiv preprint arXiv: 180.:0898 2018
Max Jaderberg, Andrea Vedaldi, and Andrew Zisserman. Speeding up convolutional neural networks with low rank expansions. arXiv preprint 1405.33605 2014.
Steven A Janowsky. Pruning versus clipping in neural networks. Physical Review A, (9(12):600,, 1989.
Ehud D Karmin. A simple procedure for pruning back-propagation trained neural networks. 1EEE Iransactions on neural networks, 1(2):239 2422, 1990.
Durk P Kingma, Tim Salimans, and Max Welling. Variational dropout and the local reparameteri- zation trick. Advances in neural information processing systems, 28, 2015.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
Namhoon Lee. Thalaiyasingam Ajanthan, and Philip HS Tor. Snip: Single-shot network pruning based on connection sensitivity. In International Conference on Learning Representations, 2018.
Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip HS Torr. A signal propagation perspective for pruning neural networks initialization. In International Conference Learning Representations, 2019.
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Zahra Atashgahi, Lu Yin, Huanyu Kou, Li Shen, Mykola Pechenizkiy, Zhangyang Wang, and Decebal Constantin Mocanu. Sparse training via boosting pruning plasticity with neuroregeneration. Advances in Neural Information Processing Systems, 34:9908-9922. 2021a.
10

---

Under review as a conference paper at ICLR 2023
Shiwei Liu, Lu Yin, Decebal Constantin Mocanu, and Mykola Pechenizkiy. Do actually need dense over- paee-aaratterizaaioon in-time paramatrtttniiniaooonn in sparse training. In International Conference on Machine Learning, pp. 6989-7000. PMLR, 2021b.
Weibo Liu, Zidong Wang, Xiaohui Liu, Nianyin Zeng, Yurong Liu, and Fuad E Alsaadi. A survey of deep neural network architectures and their applications. Neurocomputing, 234:11 1-22,, 2017.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. In International Conference Learning Representations, 2018.
Christos Louizos. Max Welling, and Diederik P Kingma. Learning sparse neural networks through 1.0 regularization. In International Conference on Learning Representations. 2018.
Ekdeep Singh Lubana and Robert Dick. A gradient flow framework for analyzing network pruning. In International Conference on Learning Representations, 2020.
Siwei Ma, Xinfeng Zhang, Chuanmin Jia, Zhenghui Zhao, Shiqi Wang, and Shanshe Wang. Image and video compression with neural networks: review. IEEE Transactions on Circuits and Systems for Video Technology, 30(6):1683-106) 2019.
Ben Mildenhall, Pratul P Srinivasan, Matthew Tancik, Jonathan T Barron, Ravi Ramamoorthi, and Ren Ng. Nerf: Representing scenes as neural radiance fields for view synthesis. Communications of the ACM, 65(1):99-106, 2021.
Asit Mishra, Eriko Nurvitadhi, Jeffrey J Cook, and Debbie Marr. Wrpn: Wide reduced-precision networks. In International Conference on Learning Representations, 2018.
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connec- tivity inspired by network science. Nature communications, 91):1-12, 2018.
Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational dropout sparsifies deep neural networks. In International Conference Machine Learning, pp. 2498 2507. PMLR, 2017.
P Molchanov, S Tyree, T Karras, T Aila, and J Kautz. Pruning convolutional neural networks for resource efficient inference. In Sth International Conference on Learning Representations, ICLR 2017-Conference Track Proceedings, 2019a.
Pavlo Molchanov, Arun Mallya, Stephen Tyree, luri Frosio, and Jan Kautz. Importance estimation for neural network pruning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11264-1 1172, 2019b.
Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In International Conference on Machine Learning, pp- 4646-4655. PMLR, 2019.
Michael C Mozer and Paul Smolensky. Skeletonization: A technique for trimming the fat from network via relevance assessment. Advances in neural information processing systems, 1, 1988.
Behnam Neyshabur, Russ R Salakhutdinov, and Nati Srebro. Path-sgd: Path- normalzzdd optimiza- tion in deep neural networks. Advances in neural information processing systems, 28, 2015a.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401. PMLR, 2015b.
Roman Novak, Yasaman Bahri, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl- Dickstein. Sensitivity and generalization in neural networks: empirical study. arXiv preprint 1rXiv:1802.08860, 2018
Alexander Novikov, Dmitrii Podoprikhin, Anton Osokin, and Dmitry P Vetrov. Tensorizing neural networks. Advances in neural information processing systems, 28, 2015.
Daniel W Otter, Julian R Medina, and Jugal K Kalita. A survey of the usages of deep learning for natural language processing. IEEE transactions on neural networks and learning systems, 32(2): 604 624, 2020.
11

---

Under review as a conference paper at ICLR 2023
Niall O' O'Mahony, Sean Campbell, Anderson Carvalho, Suman Harapanahalli, Gustavo Velasco Her- nandez, Lenka Krpalkova, Daniel Riordan, and Joseph Walsh. Deep learning vs. traditional com- puter vision. In Science and information conference, pp. 128-144. Springer, 2019.
Luiz Pessoa. Understanding brain networks and brain organization. Physics of life reviews, 11(3): 400-435, 2014.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot exi-to-image generation. International Conference on Machine Learning, pp. 8821-8831. PMLR, 2021.
Russell Reed. Pruning algorithms-a survey. IEEE transactions on Neural Networks, 4(5):740-747, 1993.
Julian Schritwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):004-609 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
Nikko Ström. Sparse connection and pruning in large dynamic artificial neural networks. In Fifth European Conference on Speech Communication and Technology. Citeseer, 1997.
Hidenori Tanaka, Daniel Kunin, Daniel Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. Advances in Neural Information Pro- cessing Systems, 33:6377-665 6389, 2020.
Georg Thimm and Emile Fiesler. Evaluating pruning methods. In Proceedings of the International Symposium Artificial neural networks, pp. 20-25, 1995.
Athanasios Voulodimos, Nikolaos Doulamis, Anastasios Doulamis, and Eftychios Protopapadakis. Deep learning for computer vision: brief review. Computational intelligence and neuroxcience, 2018, 2018
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by
preserving gradient flow. In International Conference on Learning Representations, 2019.
Xizhao Wang, Yanxia Zhao, and Farhad Pourpanah. Recent advances in deep learning. International Journal of Machine Learning and Cybernetics, 1 114):7477770, 2020.
Duncan J Watts and Steven H Strogatz. Collective dynamics of amalll-orldd networks. nature, 393 (6684):440 442, 1998.
Huanrui Yang, Wei Wen, and Hai Li. Deephoyer: Learning sparser neural network with differen- tiable inaleiinvariant sparsity measures. In International Conference on Learning Representa- tions, 2019.
Tom Young, Devamanyu Hazarika, Soujanya Poria, and Erik Cambria. Recent trends in deep learn- ing based natural language processing. ieee Computational intelligenCe magazine, 13(3):55-75, 2018.
Ruichi Yu, Ang Li, Chun-Fu Chen, Jui-Hsin Lai, Vlad Morariu, Xintong Han, Mingfei Gao, Ching- Yung Lin, and Larry S Davis. Nisp: Pruning networks using neuron importance score propagation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 9194- 9203, 2018
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. AI Open, 1:57-81, 2020.
Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression. arXiv preprint arXiv: 2017.
12

---

Under review as a conference paper at ICLR 2023
A DATA NORMALIZATION
We normalize all the training and test data to have mean of O and standard deviation of 1. The dataset statistics that we used are specified below, where μ is the mean and the standard deviation. Each value corresponds to color channel of the images.
A.1
CIFAR-10
=
(0.4914,
= (0.2470, 0.2435, 0.2616
A.2 CIFAR-100
1 = (0.5071,0.4865)) 0.4409), a = (0.2673, 0.2564, 0.256,,,,,,))77))
B DATA AUGMENTATION
We used standard data augmentation as part of our training data pipeline. The specific augmentation techniques are specified below.
B.1
CIFAR-10
We use a random horizontal flip of the image with a probability of O.5. We then pad the image with 4 black pixels all sides and randomly crop section of 32 by 32 pixels.
B.2 CIFAR-100
We pad the image with 4 black pixels on all sides and randomly crop section of 32 by pixels. We then randomly flip the image horizontally with probability of 0.5. Lastly, we randomly rotate the image between 15 degrees clockwise and counter clockwise.
C CONVOLUTIONAL LAYER SUBSET SAMPLING
While in cully-connected layers weight is specified by the input and output units that connects, weight in a 2D convolutional layer is specified by the input channel, output channel, and its and coordinate the kernel. This means that it requires four discrete probability distributions to sample a weight of 2D convolutional layer, instead of two for fully-connectoo layers.
With the uniform heuristic these four distributions simply discrete uniform distributions between and the number input channels, output channels, kernel width, and kernel height. With the SynFlow heuristic, we sample input channel proportional to the over the input channels and an output channel proportional to the sum of efferent synaptic flow over the output channels. With the GraBo heuristic, of activity over the input channels and an output channel proportional to the sum of the gradient over the output channels. The and coordinate on the kernel more challenging sample efficiently with the informed heuristics, therefore we decided to keep sampling those uniformly.
of afferent synaptic flow
sample input channel proportional the sum
D GRADIENT MAGNITUDE UPPER BOUND PROOF
Lemma D.I. The gradient magnitude of the loss with respect to the parameters of fully-connected layer has the following upper bound:
1Ol!
<
Σ
h
[1-1]
1)
Σ
8!!
13

---

Under review as a conference paper at ICLR 2023
h E IR Bx and 811)_ BBBxa are the sparse weight matrix, activa- tion and gradient of the loss at the oulput units of the 1-th layer, rexpectively. The number of units in the 1-th layer is denoted by nlll N+ and B N+ is the batch size.
where 0l4 "lln"
Proof. The proof starts with the definition of the gradient of the fully-connected layer, which is calculated during back propagation as the activations of the previous layer multiplied with the back propagated gradient of the output units of the layer. We then write this definition for single con- nection in the weight matrix and use the triangle inequality to specify the first upper bound. In Equation T0 we rewrite the upper bound of Equation as all the cross products between the batch dimensions minus all the non-identical cross terms. Not that all the non-identical cross terms are positive because of the absolute, therefore we get another upper bound by removing the non-identical cross terms which we then write in matrix form in Equation
VOl
(
T
80
B
B
V0 0,b
h
11-18
5/1 i.b
S
h
11-1|
(9)
2,a
i,a
2,6
t=1
Σ
h 11-1/
h
[1-1]
h
|l
Σ
g!1
(10)
i,a
1.b
i,a
i.b
1,a7r
T
B
V -
Σ
Σ
5!!
(11)
E SUBSET MULTIPLIER
The extended results on the affect of the size of the subset are shown in Figure 3
F LAYER-WISE SPARSITY
We show the sparsity of each layer obtained with the various methods at the end of training in Figure 4
G IMPLEMENTATION NOTES
The implementation of the SynFlow heuristic required the usage of double floating point precision and normalization of the output criteria in order to prevent the values from overflowing. This is one additional disadvantage of using the SynFlow heuristic, in addition to its requirement to make copy of the model, making it consume three times the memory of GraBo.
14

---

Under review as a conference paper at ICLR 2023
Rigl.
SynPlow
90% sparsity
95% sparsity
98% sparsity
ResNet-So on CIFAR-10
ResNet-56 on CIFAR-10
ResNer-56 on CIFAR-10
0.910
0.90
Accuracy
0.905
0.900
0.88
0.895
0.05
0.10
0.15
0.20
0.025
0,050
0.075
0.100
0.01
0.02
0.03
0.04
VGG-16 on CIFAR-10
CIFAR-10
CIFAR-I0
0.86
Accuncc
0.87
0.84
ResNet- 56 CIFAR-100
ResNet-56 CIFAR-100
ResNet-5e CIFAR 100
Accuracy
0.65
0.60
0.475
0.64
0.63
0.05
0.10
0.15
0.20
0.025
0.050
0.075
0.100
0.01
0.02
0.03
0.04
VGG-16
CIFAR-100
VGG- 16 CIFAR. 100
VGG- 16 on CIFAR-10 100
0.56
Accuracy
0.48
0.35
0.54
0.46
0.05
0.10
0.15
0.20
0.025
0.050
0.075
0.100
0.01
0.02
0.03
0.04
Fraction of connections
Fraction of connections
Fraction of connections
Figure 3: The accuracy of the heuristics while increasing the subset size $ fraction of |W] Showing ResNet-56 and VGG-16 16 models trained on the CIFAR- 10/100 datasets with 90%, 95%, and 98% sparsity.
15

---

Under review as a conference paper at ICLR 2023
90.0
95.0
98.0
CIFAR-10
CIFAR- 100
ResNet-56
VGG-16
ResNet-56
VGG-16
Lottery
Lottery
Lottery
Lottery
1.0
1.0
1.0
1.0
Spansty
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
25
50
10
15
0
25
50
5
10
15
Pruning
Pruning
Pruning
Pruning
1.0
1.0
1.0
Sparsiy
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
25
10
5
155
Random
Random
Random
Random
1.0
Sparsity
0.5
0.5
0.0
0.0
0.0
SNIP
SNIP
SNIP
SNIP
1.0
Spanity
25
50
10
5
1.
GraSP
GraSP
GmaPP
1.0
1.0
1.0
1.0
Spaniity
0.5
0.5
0.5
0.5
0.0
25
50
10
15
25
50
5
15
[GrSPP]
[GraPP]
GraSPI
GraSP)
1.0
1.0
1.0
1.0
Sparsity
0.5
0.5
0.5
0.5
0.0
0.0
25
30
10
15
0
25
50
5
10
15
Layer
Layer
Layer
Layer
Figure 4: (Part 1) The layer-wise sparsity resulting from each method at the end of training. Showing ResNet-56 and VGG-16 models trained on the SIFAR-10/100 datasets with 90%, 95%, and 98% sparsity.
16

---

Under review as a conference paper at ICLR 2023
90.0
95.0
98.0
CIFAR-10
CIFAR-100 100
ResNet-56
VGG-16
ResNet-56
VGG-16
SynFlow
SynFlow
SynFlow
SynFlow
1.0
1.0
1.0
1.0
Spansty
0.5
0.5
0.5
0.5
0.0
25
10
5
SET
SET
SET
SET
1.0
Spursity
0.5
0.5
0.5
0.5
0.0
0.0
25
50
10
15
0
25
50
5
15
Rigl.
Rigl.
Rigl.
Rigl.
1.0
Spunaity
0.5
0.5
0.0
0.0
0.0
0.0
50
10
5
15
Random subect
Random subset
Random subses
Random
1.0
1.0
1.0
1.0
Sparsiy
0.0
0.0
0.0
0.0
SynlFlow subset
SynFlow subset
SynFlow subset
SynFllow subset
1.0
1.0
1.0
Spurdit
0.5
0.5
0.5
0.5
0.0
25
50
10
15
25
50
5
15
Graßo subset
Graßo subset
Graßo subset
Graßlo subset
1.0
Sparsity
0.5
0.5
0.5
0.5
0.0
0.0
0.0
25
30
10
15
0
25
50
5
10
15
Layer
Layer
Layer
Layer
Figure 4: (Part 2) The layer-wise sparsity resulting from each method at the end of training. Showing ResNet-56 and VGG-16 models trained on the CIFAR-10/100 datasets with 90%, 95%, and 98% sparsity. For our method [S] 10[IP].
17


Reviews:
[{"review_id": "hdWeun7JHEJ", "reviewer": "Reviewer_qDT4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Dynamic sparse training (DST) has been proposed to sparsify models during training. However, all the previously published method still required similar amounts of memory to train the sparsified model and the dense model. This paper describe a new technique that overcomes this limitation. Specifically, they contribute:\n* a new sampling strategy used to identify a set of pruned connections that should be activated in the next training iteration.\n* an empirical evaluation of the approach that compares its impact on model accuracy against a comprehensive set of alternative approaches.", "summary_of_the_review": "The authors tackle a problem of great importance, namely decreasing the peak memory usage of deep learning. However, I feel that the evaluation of their approach needs to be improved to support the authors claims of reducing memory usage and meeting the performance of existing DST approaches.", "strength_and_weaknesses": "The stated benefit of this paper is to reduce peak memory usage during training a model. However, there is no measurement or estimation of the memory saved by this new approach saves. The authors blame the lack of comprehensive support for sparse operations in PyTorch, but the authors could have simply sparsified/densified tensors on the fly as needed to work around the limitations of PyTorch (though at the cost of some overhead due to the temporary storage of a dense version of each tensor). This is a major limitation that prevents a proper assessment of the value of the work.\n\nThe evaluation is performed on only two CNNs: VGG-16, and ResNet-56. Since the approach is a heuristics, its evaluation needs to be performed on a broader set of DNNs to ensure that it's broadly applicable. For example, I would have liked to see different neural network architectures, such as vision transformers, and different application domains, such as speech, natural language, generative models, etc... PyTorch is shipped with a comprehensive list of models that can be quickly leveraged to strengthen the evaluation.\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "PaNm1fXui3", "reviewer": "Reviewer_WdYk", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The authors propose a new DST algorithm that utilizes only sampled connections to reduce peak memory usage while previous DST algorithms rely on computing gradients of all connections. For some selected models, the proposed method can obtain similar model accuracy using only 4% as a size of sampled connections compared to the case of DST cases that investigate all connections.", "summary_of_the_review": "- Practical discussions on reduced memory footprint, energy consumption, and the overall training time are missing.\n- Model selections are not practical.\n", "strength_and_weaknesses": "*Strength\n- The authors empirically show that sampled connections can achieve a similar model accuracy compared to the case of DST algorithms using all connections.\n- Various methods to obtain sampled connections, such as Random, SynFlow, and GraBo, are presented and compared (as shown in Figure 2)\n- For a given subset size (i.e., the number of unpruned connections), the authors show that scaling up widths of a model can improve model accuracy.\n\n*Weakness\n- Even though a major contribution of this manuscript is from memory saving during training, discussions and practical analysis of memory saving are missing.\n- The authors discuss energy consumption saving as a gain to apply the proposed DST algorithm. However, convergence and the overall training time are not analyzed in the manuscript. A thorough and detailed analysis on the overall training results (including training and valid loss graphs) need to be presented.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GJYzXfmCmU", "reviewer": "Reviewer_ghDx", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "In this paper, the authors propose a new weight level sparse training method for deep neural networks. Its motivation is to reduce the peak memory cost during training. The idea is to sample a subset of inactive in each iteration and optimize the loss over these weights. The authors conduct some experiments to evaluate the performance of their method. However,  the proposed method also hasn’t been evaluated properly.  More importantly, the idea of this paper is unreasonable as for convolutional neural networks, most of the memory during training is spent by the activations instead of the weights. ", "summary_of_the_review": "1. The idea of the proposed method is unreasonable. \n\n2. The proposed method hasn’t been evaluated properly. \n", "strength_and_weaknesses": "Strength:\n\n1. This paper is well written and easy to read. \n\nWeaknesses:\n\n1. The idea of the proposed method is unreasonable. For convolutional neural networks, most of the memory cost in training is spent in storing the activations, which would be scaled up by the mini-batch size, insteads of the weights. In the proposed method, the activations are unlikely to be pruned, therefore the memory cost cannot be saved effectively. \n\n2. The proposed method hasn’t been evaluated properly. The authors need to show the memory cost during the whole training process instead of the size of the sparse model. \n\n3. The authors also need to conduct experiments with large datasets, such as ImageNet, which is a standard dataset for sparse training/pruning studies. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "-l_o2JHMgc", "reviewer": "Reviewer_U17z", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper introduces a method for dynamically pruning connections during training based on a heuristic of the gradient magnitude. The goal is to reduce peak training memory consumption while maintaining accuracy. The method is evaluated on CIFAR10 & CIFAR100 using ResNet-56 & VGG-16. ", "summary_of_the_review": "I think reducing training memory is important, but I have several major concerns regarding the novelty, experiments, and practical value of the proposed method (see Strength And Weaknesses). ", "strength_and_weaknesses": "Given that large deep learning models are becoming popular, reducing the training memory cost of deep neural networks is an important topic and has high practical value. However, I have several major concerns:\n1. Dynamically pruning neural networks during training to reduce the training memory is not new. As far as I know, [1] has explored the same problem. \n2. Current experiments are only done on small datasets and neural networks. However, in practice, we only need such memory-saving techniques when using large datasets and large neural networks. \n3. It seems that the proposed method prunes connections in a fine-grained manner. If so, there is no saving on common training hardware platforms (e.g., GPU). In the experiments, I did not find any results showing the real memory saving of the proposed method.  \n\n\n[1] Dynamic sparse graph for efficient deep learning, ICLR 2019", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject