Differentiable Sparsification for Deep Neural Networks
Authors: Yongjin Lee
Venue: NeurIPS 2021 Submitted (2021)

Abstract: Deep neural networks have relieved the feature engineering burden on human experts. However, comparable efforts are instead required to determine an effective architecture. In addition, as the sizes of networks have over-grown, a considerable amount of resources is also invested in reducing the sizes. The sparsification of an over-complete model addresses these problems as it removes redundant parameters or connections. In this study, we propose a fully differentiable sparsification method for deep neural networks, which allows parameters to be zero during training with the stochastic gradient descent. Thus, the proposed method can simultaneously learn the sparsified structure and weights of networks in an end-to-end manner, which can be directly applies to modern deep neural networks and imposes minimum overhead to the training process. To the authors' best knowledge, it is the first fully [sub-]differentiable sparsification method that zeroes out components, and it provides a foundation for future structure learning and model compression methods.

Differentiable Sparsification for Deep Neural Networks
Anonymous Author(s) Affiliation Address email
Abstract
Deep neural networks have relieved the feature engineering burden on human experts. However, comparable efforts are instead required to determine effective architecture. In addition, as the sizes of networks have over-grown, a considerable amount of resources is also invested in reducing the sizes. The sparsification of an over-complete model addresses these problems as removes redundant parameters connections. In this study, propose fully differentiable sparsification method for deep neural networks, which allows parameters to be zero during training with the stochastic gradient descent. Thus, the proposed method simultaneously learn the sparsified structure and weights of networks in an end- to-end manner, which and imposes minimum overhead to the training process. To the authors' best knowledge, is the first fully jubbjdiiffreeniable sparsification method that zeroes out components, and it provides a foundation for future structure learning and model compression methods.
3
5
10
be directly applies to modern deep neural networks
11
12
13
14
Introduction
15
16
The success of deep neural networks has changed the paradigm of machine learning and pattern recognition from feature engineering to architecture engineering [6 neural networks have relieved the burden of feature engineering, comparable human efforts are instead required determine an effective architecture, such as the number of neurons or layers and the connections between nodes. In addition, deep neural networks have over-grown (even up to 10-68 million parameters) [8] [0] 15 [2], considerable effort is also being invested reducing existing model sizes and in meeting the demands of deploying such networks on constrained platforms at
17
14
22 32.. Although deep
19
21
23
inference time 26 25
24
These problems can be addressed by the sparsification of an over-complete model 20 A network structure can be carved out of an over-complete model by removing redundant blocks deleting unnecessary connections between nodes or blocks 2 18 30 which also reduces the network
25
29 or
26
27
size. Among several approaches, pruning has long been adapted 17 26 [9 [. It typically requires pre-trained model and several steps (select unimportant parameters of pre-trained model, delete
28
29 the parameters, and retrain the pruned model) and may repeat the process multiple times. Another
approach is sparsity regularizer with the proximal gradient 21 3 29 33 which shrinks redundant parameters to zero during training and requires no pre-trained model. Among the most popular ones individual parameter, it often produces unstructured 33 irregular models; thus, diminishes the benefit of parallel hardware computation, such as GPUs [29]. In order to obtain regular sparse structures, sparse regularization with 22- f2-morm 3 20 was adopted
31
l regularizer (28). However, it acts
35 on a group of parameters so that all parameters under the same group are either retained or zeroed- group level, the number of neurons layers can be automatically determined as a part of training. However, the optimization of regularization term is performed as separate step separately from the gradient descent- based optimization for prediction
together. By zeroing-out parameters
37
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

39 loss. The update rules should be implemented manually and the approach is limited to the cases where closed form solutions for the proximal operation are known.
40
41 In this work, we propose a fully (sub-Jdifferentiabl sparsification method for deep neural networks, which directly optimizes regularized objective function and allows parameters be exactly zero during training with the stochastic gradient descent. Thus, it can simultancously learn the sparsified structure and weights of deep neural networks an end-to-end manner. It leads to simpler implemen- lation and it does not require to manually code a pruning step or an update rule like soft-thresholding operator. can adopt various norms as a regularizer regardless of whether their closed form solutions for the proximal operator are known or not. Another ad advantage of the proposed method is that it building block; thus, it can produce a structured
43
44
45
46
47
48
can be easily applied on a group of parameters model and maximize the benefits of parallel hardware computation (e.g.. GPUs) and it well suits the
49
50
trend of a modularized design in deep learning [22
51
2
Related Work
2.1
Proximal Gradient
53 Our proposed method is related to sparsity regularization with the proximal gradient 21 A regular- ized objective function is written as
W) + AR (W),
(I)
where L denotes prediction loss, R is regularization term, D is set of training data, W is set 56 of model parameters, and À controls the trade-off between prediction loss and model complexity. The most popular regularizer is l-norm,
57
R (W)
Σ wsl
(2)
58 where wi is an individual element of W. To optimize the regularization term, parameter updating is performed with a proximal operator,
59
W; sign (w:) (wvl - m7))+ +
80 where + denotes an assignment operator, is learning rate, and (-)+ represents max(-, 0). As this
81 approach on individual parameter, it often produces unstructured irregular models. In order
82 to obtain regular sparse structures, the sparse regularization with 12, -norm can be adopted [3] 29)
63 All parameters the same group are either retained or zeroed-out together. The regularization with
64 2 norm is written as
R R(W)
Σ wo
Σ
Σ
g.
85 where W = {w,} and w, represents group of model parameters, The regularization term is optimized with proximal operator,
66
[[
gg.
Wg.d
[
When group has only one single parameter, it degenerates to the nooor regularization.
68 Another group regularization exclusive lasso with 4 norm 34
Rather than either retaining
69 or removing an entire group altogether, it promotes the competition or sparsity within group. The
70
regularization term is written as
R (W)
Σ 2
w
2
Σ
Σ
W
(6)
2
71 and its updating rule is derived as
Wgg sign (wg,e) (woar) - 7>/lw>l11

---

72
These proximal operators consist of weight decaying and thresholding steps, and they are performed every mini batch or epoch sperate step after the optimization of a prediction loss. It requires 74 some extra efforts to implement the update rules manually and applications are limited to the cases where closed form solutions for the proximal operator are known. In contrast, our approach optimizes
73
75
76 regularized objective function directly and allows parameters to be zero during training with the stochastic gradient descent. It leads to simpler implementations and it can employ various norms regardless of whether closed form solutions for proximal operators are known or not, for example p-norm with p <
77
79
80
2.2
Differentiable Approach
Similar to our work, previous differentiable approaches 2 18 learn the structure of a neural network by optimizing architecture parameters in a relaxed continuous domain, where architecture parameters represent the importance scores of building blocks or the connection strengths between 84 them. However, the architecture parameter magnitudes cannot be zero during training, the
81
82
85
85 top connections or components are stochastically or deterministically selected according to the architecture parameter values to derive a discretized architecture. Therefore, the approach may suffer 87 from the discrepancy between a learned architecture and a final discretized one. Moreover, the value of I should be pre-specified manually; thus, the same value is set for all blocks modules, which may be sub-optimal. Our approach drives the architecture parameters to zero by optimizing a regularized objective function. This can minimize the model discrepancy, and network can choose the different numbers of components or connections in each module through training.
89
91
3
Proposed Approach
93
3.1
Base Model
94
We assume that there are n components in a module. A component can be any building block for a deep neural network or its output. For example, it can be a channel layer of convolutional neural networks such as ResNet 7 and DenseNet layer [IO). It can also represent a node in a neural graph [30] or convolutional neural network [I]] A module represents composite of components, 96 such as group of channels or nodes. For illustration purposes, we assume that a module y can be written the linear combination of components f,:
96
99
y (x)
Σ offe (x),
(8)
100
where x denotes a module input, w; model parameters for component f, and a; an architecture parameter. Model parameters w, denote ordinary parameters, such as a filter in convolutional layer or weight a fully connected layer. The value of a; represents the importance of component and represents the connection strength between nodes in another context. Enforcing to be zero amounts to removing component or zeroing-out W;. Thus, by creating the competition between elements of and driving them to be zero, we can eliminate unnecessary components or connections. The sample model is simple, but we will show that it can be applied to various cases.
101
102
103
104
105
108
107
3.2
Differentiable Sparse Parameterization
108
First, we show how parameterize architecture parameters with non-negative constraints, which is useful for the attention mechanism with the softmax. To set up the competition between the elements
109
110
of a and allow them be zero, we parameterize the architecture parameters as follows:
2/ exp (as)
(9)
111
7: = (71 (B) 11T111))
(10)
112
7/
(11)
3

---

113
where 04 and 8 are unconstrained free parameters, (-) denotes a sigmoid function, and (.) rep- resents relu(-) = max(-, 0). When parameter is non-negative, the proximal operator of Eq. 7 reduced to Eq. (T).. Although the forms are similar, they have completely different meanings. The proximal operator is learning rule, whereas Eq. (TO) is the parameterized form of architecture parameters, which is part of a neural network.
114
115
116
117
118
We can easily verify that a; is allowed to be zero and is also differentiable from a modern deep learning perspective. The free parameters a; and are real-valued and they do not restrict a training process with the stochastic gradient descent. Thus, we can train ag through or and [.. The exponential function Eq. (9) ensures that the architecture parameters are non -eggniaaee.. Typically, a; cannot
119
120
121
122
be zero due to the exponential function of Eq. (9) However, 7/8 in Eq. (1O) can be zero by the thresholding operation; hence, a, can be zero well. The term o (5) 1 plays the role of threshold, and the thresholding operation is interpreted as follows: if the strength of component i a competition group is small compared to the total strength, it is dropped from the competition. Note that the scalar parameter 3 in Eq. (TO), which determines the magnitude of threshold, is not a parame,r,,,,er, but its value automatically determined through training. Mathematically, the thresholding operator is not differentiable, but this should not pose an issue considering the support of relu as a built-in differentiable function in a modern deep learning tool. Additionally, y is nen-negative; thus, its 1 norm is simply the sum of % (i.e., lee. = >n))
123
124
125
126
127
129
7)). The softmax of Eq. (11)
131
is also differentiable. The softmax is optional but useful when we need to promote the competition between components in the attention mechanism.
132
133
By relaxing the differentiability, singed architecture parameter can be similarly formed as a, = sign (a:) (axl - a (3)1
(12)
134
where a and 3 are free parameters. The gradient the sign function is zero almost everywhere, but it does not cause problem for modern deep learning tool. The equation can be rewritten as
135
(a: (3)]|all a, <0
a; =
(a. (3)]|e1I)+ otherwise,
138
where (-)_ = min(-.0). 0). The gradient can be computed separately according to whether its value negative or not. To the authors' understanding, sign function already taken care in the ex- plained manner by TensorFlow [.] and thus if..mah..iinn can be simply used without the manual
137
138
139
implementation of the conditional statement.
140
3.3
Sparsity Regularizer
141
In the proposed approach, an objective function written as
L (D, W, a) + XR (a).
(13)
142 where a denotes the vector of architecture parameters. Sparsifying a is equivalent to sparsifying deep neural network. Therefore, we can use the regularization term on a to encourage the sparsity of a. The proposed method is not limited to a particular norm and we can drive different sparsity patterns
143
144
145
depending on the types of norms. For example, the most popular choice for parameter selection is norm, but it is unsuitable a in Eq. (II) as it is normalized using the softmax. Its [ı-norm is always 1, i.e../aall = lail = Therefore, we should employ p-norm with p < 1:
147
n
R (a)
Σ
laj"
(14)
148
where the second equality holds as a; is always non non-negative. To the authors' best knowledge, a closed form solution for the proximal operator of p-norm with 1 is unknown, but the regularization term is differentiable almost everywhere as retu is. Thus, the proposed approach can directly optimize the regularized objective function and zero-out components with the stochastic gradient descent.
150
152
By simply switching one norm another one for a regularizer, different sparsity patterns can be derived. For example, an individual component can be removed with l7 -norm (Eq, 2 and a group of components or an entire module can be zeroed-out with (2,1 -norm (Eq. 4.. Note that we do not need to manually implement different updating rules as in the proximal gradient approach. We just need to rewrite a regularization term in the objective function. Examples codes and experiment results are 156
153
154
shown in the supplementary material.

---

158
3,4
Rectified Gradient Flow
159
n Eq. (10) or a, in Eq. (12) is less than the threshold, the gradient will be zero, and it will not receive learning signals. However, note that it does not necessarily mean that a component dies permanently once its importance score is less than the threshold. The component still has chance to recover because the threshold is adjustable and the importance scores of other components may decrease. Nevertheless, to ensure that the architecture parameters of dropped components continuously receive learning signals, we propose approximating the gradient of the thresholding function. As in [1] where the gradient of a step function was approximated using that of leaky relu or soft plus, suggest employing elu 4 as variant of the proposed method: relu is used in the forward pass, but elu is used in the backward pass.
180
161
162
163
164
185
167
168
This heuristic approach leads to a similar learning mechanism proposed in [30 where the gradient flows to dropped (or zeroed out) edges but does not flow through these dropped edges. The architecture parameters in our proposed method correspond to the edges in [30]. Note that our approach can be easily implemented, and does not require additional codes to control the gradient flow. The
189
170
171
172
implementation codes are shown in the appendix.
4
Application and Experiment
174
In this section, we show that the proposed approach can be applied reduce the size of a network as well as to learn the structure. Our aim is not to achieve state-of-the-ar performance but to validate the idea and the broad applicability of the proposed approach. In order show the broad applicability with limited computing resources, we perform experiments with relative small datasets such as
175
178
177
CIFAR- 10/100 [3. Our implementations closely follow those of baseline models, including model
178
179
structures and hhper-paramedt parameter settings.
180
4.1
Channel Pruning in Convolutional Network
Table
Performance on CIFAR-10, DenseNet-100-BC-K12
Sparsity
Top-1 Error(%)
Parmas
FLOPs
Model
Avg.
Std.
Avg.
Std.
Avg.
Std.
Avg.
Std.
Base
00.0
0.0
5.44
0.11
7.6 10
0.0
5.8 x 10a
0.0
NS
70.0
6.53
0.19
2.9 x 10
9.3 102
1.9 x 10
5.0 10
NS
80.0
0.0
8.39
0.28
2.0 x 10
2.0 10
1.4 x 10
3.4 x 10
DS
70.3
0.1
5.77
0.09
2.7 x 10
2.3 10²
1.8 x 10
1.6 10
DS
80.4
0.1
6.64
0.11
1.7 x 10
0.6 10
1.3 x 10
2.0 10
181
prunes unimportant channels in convolutional layers by leveraging the scaling factors in batch normalization. Let z; and be the input and output of batch normalization for channel and then the operation can be written
Network-Slimminn(NS) 20
182
183
+ a.I; + b..
184
where μ4 and d; denotes the mean and standard deviation of input activations, a and b are scale and shift parameters, is small constant for numerical stability. The scaling parameter can be considered as an importance score or an architecture parameter, and the affine transformation can be re- re-written
186
187
= a (ā:; + b.).
By pushing a, to be zero, corresponding channel can be removed. Network-slimming trains an initial network with I ly-reullarization on a to identify insignificant channels. After the training, channels with small values of pruned. To compensate the damage caused by pruning. a pruned network fine-tuned. In our approach, we parameterize the scaling parameter using Eq. (12) and train network with nnorr on using the stochastic gradient descent without pruning and fine-tuning.
189
191
182
193
We perform comparison experiments on CIFAR-10/10 I3
The training and test sets contain 50, 000 and 10, 000 samples respectively, and the final test error is reported at the end of training
5

---

195
on all training images. We adopt a standard data augmentation scheme (random shifting and flipping) as in 77. In nettork--slimingg À in Eq. 13 fixed to 10 but in our approach
196
197
we vary its value to induce different level of sparsity. DenseNet-BC-K12 with 100 layers [10 and network- network-slimming. pre-trained models are obtained by training networks for 160 epochs with the initial learning of 0.1. The learning
198
ResNet with 164 layers 7 & are employed as base networks.
199
200
rate is divided by 10 at 50% and 75% of the total number of training epochs. After the training, channels with small values of are pruned and slimmed network is fine-turned for another 160 epochs with the same setting as in the initial training. but learned weights are not re-initialized. In our approach, we train networks for 320 epochs without fine-ttning re- tr-triining. Network
202
204
initializes the scaling factor to be 0.5 and we set a = 0.5 (n + 1) /n and / = log (n² + n - 1) in
Eq. 12 so that starts with 0.5.
206
Table T shows experiment results on CIFAR-10 with DenseNet. More experiments, including ResNet and CIFAR-100, are given in the supplementary materials due to page limitation. The authors strongly urge readers to see the supplementary materials. We ran each experiments times and showed the average and the standard deviation. Our proposed method is denoted by Differentiable Sparsification (DS). We controlled the value of À such that similar pruning rate with that of the network-slimming approach. In the tables, sparsity denotes the number of removed channels in hidden layers. The experiments show that the proposed differentiable approach more effectively learns slimed models.
207
208
210
212
213
4.2
Discovering Neural Wirings
Table 2: Performance on CIFAR-10, Discovering Neural Wirings
Top-1 Error %))
Parmas
Mult-Adds
Model
Avg.
Std.
Avg.
Std.
Avg.
Std.
(xx0.2))
13.44
0.24
2.2 x 10
0.0
3.3 x 10
0.0
No Update( x 0.225)
13.86
0.27
2.2 x 10
3.7 x 10a
4.5 x 10
3.7 x 104
DNW(x0.225)
10.30
0.20
1.8 10
6.7 x 10
3.1 10
4.6 10*
PG-m--norm PG-l1,2-norm
12.17
0.44
2.1 10a
9.4 x 102
3.3 x 10
1.7 10
13.62
0.56
9.6 x 10
1.6 x 10a
3.4 x 10
8.6 x 10
DS-No Rectified Grad.
10.55
0.23
6.1 10
5.7 x 10"
3.4 10"
4.5 x 10*
DS-Rectified Grad.
9.36
0.27
4.7 10
8.4 x 102
3.3 x 10t
6.7 x 10*
Discovering Neural Wirings(DNW) [30 relaxes the notion of layers and treats channels nodes 215 in a neural graph. By allowing channels to learn connections between them, it jointly discovers the structure and learns the parameters of neural network. An input to node v, X., is expressed
y Σ Wa
(u.0)EE
where x,, denotes the state of proceeding node, E represents a edge set and Wa, is connection weight of an edge. The structure of a neural graph can be determined by choosing a subset of edges.
218
219 At each iteration of training, DNW chooses the top & edges with the highest magnitude, which is called a real edge set, and refers to the remaining edges as a hallucinated edge set. On the forwards pass or at inference time, real edges are only used. As DNW allows the magnitude of the weights in both sets to change throughout training, a hallucinated edge may replace real edge when strengthens enough. The weights of real edges are updated in an ordinary manner with the stochastic gradient descent, but those of hallucinated edges are updated by a specialized leaning rule: the gradient flows to hallucinated edges but does not flow through them.
220
222
224
226
The architecture parameters in our proposed method correspond to the edges in DNW. We parame- terize the edges using Eq. (12) and train a network with 1ı-norm on edges to induce sparsity. The rectified gradient leads to an update rule which similar to that of DNW: the rectified gradient
227
228
229
ensures that dropped architecture parameters continuously receive learning signals by approximating
230
the gradient of the thresholding function. However, we do not need to keep track of the real and hallucinated edge sets. We simply optimize the objective function with approximated gradients. The rectified gradient can be implemented in a couple of lines using modern deep learning tools and the
232
code is shown in the supplementary material.

---

Figure I: Left: Structure of a GCN block. Each block consists of shared adjacency, input feature, and a weight matrix. Each row and column an adjacent matrix are treated as groups to enable the learning of relationship between node (indexed by i) and its neighbors. Right: Row grouping creates the competition between in-coming nodes, and column grouping creates the competition between out-going nodes.
We perform experiments CIFAR-10/100 [3] The final test error is reported at the end of training without using separate validation data set. MobileNetV1 (x0.25) 99] is employed as a base model and our implementation closely follows that of DNW. We train for 160 epochs with initial learning rate 0.1. The learning rate is scheduled using Cosine Annealing. DNW chose the value of such that final learned model has similar Mult-Adds with the base model, and we also the value of À in the same manner.
235
237
238
239
Table 2 shows experiment results 10. We each experiments 5 times and showed the average and the standard deviation. Our proposed method is denoted by DS. DNW without the update rule corresponds to DS without the rectified gradient method. Even without the rectified gradient, the performance of the proposed method is close to that of DNW with the update rule. It validates the effectiveness of approach. We also performed experiments with the proximal gradients of E3. and Eq. 7). which is denoted by PG in Table PG-II-norm also uses the I -orm as a regularizer, but the learning is not effective
241
243
245
246
the update rule of Eq (7) whose shape is similar to our sparse parameterization Eq. (12). but the performance is worse than ours. More experiments, including CIFAR-100, given in the supplementary materials due page limitation.
ours. Similarly, PG-I, 1---ormm
247
DNW determines the size and the structure of network by choosing & edges. However, there is clear notion how to choose k for different stages (or blocks) and thus it uses the same pruning rate for all stages, which may be restrict because each stage may play different role and need different amount of resources. In contrast, our approach controls the model complexity by adjusting the value of X in the objective function, and different amount of resources is allocated for each stage through training. As shown in Table 2 the proposed method uses model parameters more efficiently.
251
253
255
4.3
Learning relationship between Nodes in Graph
257
In this section, we applied the proposed approach to learn the structure of an adjacency matrix in graph convolutional network (GCN). The purpose of this case study is to whether our approach can learn semantic structure from data rather than reducing the size of a neural network.
258
259
We adopted the model of (11), one of the most successful GCN models. A GCN block layer is defined (see Fig. as
281
H F (AH'W*
262
where A is an adjacency matrix; H' and W are an input feature and weight matrix for layer i, respectively; and
263
nonlinear activation function. general, is non-negative and shared across GCN blocks. It is obtained by normalization. For example, A = - or = -- AD ADD- where an unnormalized adjacency matrix; and δ a diagonal matrix, where D, = Σ, A
264
265
The adjacency matrix represents the connections or relationships between nodes on a graph and 286
usually given by prior knowledge. Learning the value of Ai,; amounts to determining the relationship between nodes and j. the value of As,j is zero, can be considered that the two nodes are unrelated.
288

---

Figure The gray lines represent 170 road links where the experimental data were collected.
270
As shown in Fig. I we defined each row and column as group. Row grouping creates the competition between in-coming nodes, whereas column grouping creates the competition between out-going nodes. Each row and column of unnormalized adjacency matrix A can be parameterized similarly as of in Eq. (10):
271
272
273
Tr.j = exp (Oss.))
274
A
Yi.j (8)) 11 (87)-1177l)
- (00))
The softmax normalization of Eq. (IT) is replaced with Sinkhorn normalization 23 24 12
to make
A is doubly-stochastic: each row and column sum up to 1. Initializing A with A, we can convert Á
276
277
into a doubly stochastic matrix by iteratively applying the following equations:
A D and A AD
where D, and De are diagonal matrices; [Dr], - E, A.j [De], =; Aij. Note that although the
278
279
normalization is iterative, it is differentiable. Balanced normalization is also possible by iteratively
280
applying
A A
We verified through numerical experiments that iteratively applying the above equation also makes À doubly stochastic, but could not find theoretical justification. We leave the mathematical proof as an open question for a future work. As competition groups are created in row- and column-wise approaches, regularized objective function can be written
281
283
N Σ
C(D, A) +
R (Ac.)+ + (A..))
where W [W'), N is the size of square matrix A, and Ai,, and A., denote ith row and column vector A, respectively. We employ 4,-normm Eq. 14 with = 0.5 for a regularizer.
286
287 To validate our purposed method, we applied a GCN to estimate future traffic speeds in road network. The traffic speed data were collected from 170 road segments. Thus, the sizes of adjacent matrix is
288
170 x 170. The map of the data area collected is shown in [ One-step ahead observation is estimated from eight past observations and an output layer generates 170 estimates, one for each road segment.
290
A prediction loss is measured using the mean relative error (MRE). More detailed specifications of the experimental data and our GCN model can be found in the supplementary material. prediction
292
loss is measured using the mean relative error (MRE).
294
Three baseline models were used: two were given the road connectivity and the other was For the first baseline, we set the value of As,y as constant such that At,; = n; if node (or road) i and are adjacent to each other (n: is the number of neighbors of node i), and A,, = 0 otherwise. The second baseline was taken in similar approach, but we set Å., exp (av..) if node i and were adjacent to each other to ensure that strengths of the connections were learned. For the third
295
296
298
baseline, the connectivity was not given. However, we set Å., = exp (as.)) for all í, regardless of the actual connections. For the proposed method, parameterized the adjacency matrix as in the
299

---

301 third baseline but applied the sparsification technique. The balanced normalization was applied to all
302 cases except the first baseline, for which the row sum is 1.
303 To measure the learned relationship between nodes, we propose the following scoring function:
N
(A A9
2N
where A' = - AD O denotes the element-wise product, and [M*] = if the
304
geodesic distance between node i and j is less than or equal to k. whereas [M 0 otherwise.
305
308
The maximum value is I, and the minimum is O. For example, the first and second baselines always
have the maximum value because their adjacency matrices have exactly the same structure of _
307
308
We calculated the scores for & and 2. Note that we used A" and A instead of because sparsified matrix is not guaranteed to be doubly stochastic even if the original Sinkhorn normalization
309
310
adopted.
Table Traffic speed prediction with GCN
L.R.(x 100)
L.R. 100)
Model
#N.Z.
MAPE(%)
#N.Z.
MAPE(%)
k =
k
= 1
= 2
878
5.6623
100.00
100.00
0.050
1,220
5,4744
87.06
89.94
II
878
5,5160
100.00
100.00
0.075
1,009
5,4957
88.62
91.39
III
28,900
5.6343
13.76
20.87
0.100
835
5.5336
89.79
92.13
Bascline models
(b) Proposed method
The performance of the baseline models is shown in Table 4a We ran each experiment five times and selected the median among the five lowest validation errors. For the first and second baselines, the road connectivity is given, and the number of non-zero elements of the adjacent matrices is 878. Note that the value of the Iearned relationship for Baselines and constant, but we show for reference. The road connectivity is not given for the third baseline, and the number of non-zero elements of the adjacent matrix is 28, 900(= 170 x 170). The performance of the proposed model is shown in Table 4b The experiment of Baseline III shows that GCN finds nonlinear mapping between input and target values simply in the way of reducing the prediction loss without learning the semantic relationships between nodes, but the proposed approach finds actual relationships between nodes. We
312
314
316
318
319
320
further compared the proposed method with the proximal gradient method. The experimental results reported in the supplementary material due page limitation.
Scope and Limitation
322
323
Our aim is not to achieve state-of-the oftthe-rttttttto performance but to validate the idea and the broad applicabil- ity of the proposed approach. To the authors' best knowledge, is the first fully [sub- (sub-Jdifferentiable sparsification method that zeroes out components, and we wish our work would provide a foundation
324
325
326
for future structure learning and model compression methods. The limitation of our approach is that sparsity rate cannot be explicitly specified before training as in conventional pruning approaches. If specific sparsity rate is required, it should be obtained by try-and-error, The rectified gradient is effective as shown in the experiments of discovering neural wirings, but it is not clear in which cases is effective or not. need more theoretical analysis and leave it for a future work.
327
328
329
330
Conclusion
In this study, we proposed fully differentiable sparsification method that can simultaneously learn 333
the sparsified structure and weights of deep neural networks. Our proposed method is versatile that
it can be scamlessly integrated into different types of neural networks and various problems.

---

Checklist
335
1. For all authors...
337
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
338
(b) Did you describe the limitations of your work? [Yes] See the scope and limitation
340
section.
341
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
342
(d) Have you read the ethics review guidelines and ensured that your paper conforms to
343
them? [N/A]
344
2. If you are including theoretical results...
345
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
346
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
348
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] Main Codes are included in the supplemental material and a snippet is also given in the appendix(pdf supplemental material)
319
350
351
352
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
353
354
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We ran each experiment five times and gave the mean and the standard deviation.
355
357
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] However, readers may easily estimate required resources because we used well-known data and models in most experiments.
358
360
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
382
(a) If your work uses existing assets, did you cite the creators? [N/A]
383
(b) Did you mention the license of the assets? [N/A]
384
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
385
386
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
367
388
(c) Did you discuss whether the data you are using/curating contains personally identifiable
389
information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
371
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
373
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
374
375
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
378
References
377
378
[1] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp. Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jazefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens. Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large- scale machine learning on heterogeneous systems, 2015. htl.pst:::: //www. tensorflow org/ Software available from tensorflow.org.
379
380
381
382
385
385
10

---

387
[2] Karim Ahmed and Lorenzo Torresani. Connectivity learning in multi-branch networks. CoRR, abs/1709.09588 2017. URL hett::t/taaiiii// www.://gggbbbb.///eo/oo 1709.0905500
388
389
[3] Jose M. Alvarez and Mathieu Salzmann. Learning the number of neurons in deep networks. In NIPS, 2016.
[4] Ajórk-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). In ICLR, 2016.
392
388
[5] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In /CLR, 2019.
395
[6] Babak Hassibi, David G. Stork, and Gregory J. Wolff. Optimal brain surgeon and general network pruning, In ICNN, 1993.
396
397
[7] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
398
399
[8] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In ECCV, 2016.
[9] Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andrectto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. CoRR, 7b4/1704.04861,, 2017. httpsstss://axx
402
404
brg/abs/1704.000 04861
405
[10] Gao Huang, Zhuang Liu, and Laurens van der Maaten. Densely connected convolutional networks. CVPR, 2017.
408
407
[1I] Thomas N. Kipf and Max Welling. Semi-super classification with graph convolutional networks. In ICLR, 2017.
408
409
[12] P. A. Knight. The sinkhorn- algorithm: convergence and applications. SIAM Journal on
410
Matrix Analysis and Applications, 30(1), 2008
411
[13] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical Report, 2009.
[14] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolutional neural networks. In NIPS, 2012.
414
415
[15] Gustav Larsson, Michael Maire, and Gregory Shakhnarovich. Fractalnet: Ultra-deep neural networks without residuals. In ICLR, 2017.
417
[16] Y. LeCun, Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel. Backpropagation applied to handwritten zip code recognition. Neural Computation, 1(4): 541-551, Dec 1989. ISSN 0899-7667. doi: 10.1162/neco. 1t22/eeco.199911... 1989.1.4.541.
419
420
[17] Yann LeCun, John S. Denker, and Sara A. Solla. Optimal brain damage. In NIPS, 1989.
421
[18] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. In ICLR, 2019.
[19] Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang Learning efficient convolutional networks through network slimming. In ICCV, 2017.
424
425
[20] Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. In ICLR, 2019.
426
427
[21] Neal Parikh and Stephen Boyd. Proximal algorithms. Found. Trends Optim., 1(3):127-239, January 2014. ISSN 2167-3888. doi: 10. 10.1561/2400000003. URL htt.htt://dx...o..oggg... (5510/400000003
428
429
430
[22]
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2015.

---

432
[23]
R. Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices. The annals of mathematiicllssaiistiss.. 35(2):876-88) 879, 1964.
433
434
[24] R. Sinkhorn and P. Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2), 1967.
[25]
Huizi Mao Song Han and William J. Dally. Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding. ICLR, 2016.
437
438
[26]
John Tran Song Han, Jeff Pool and William Dally. Learning both weights and connections for efficient neural network. In NIPS, 2015.
439
440
[27] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In CVPR, 2016.
442
443
lasso. Journal of the Royal [28] Robert Tibshirani. Regression shrinkage and selection Statistical Society. Series B (Methodological), 58(1):267-285 1996.
299
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. NIPS, 2016.
446
447
[30] Mitchell Wortsman, Ali Farhadi, and Mohammad Rastegari. Discovering neural wirings. In NeurIPS, 2019.
448
449
[3] Xia Xiao, Zigeng Wang. and Sanguthevar Rajasekaran. Autoprune: Automatic network pruning by regularizing auxiliary parameters. In NeurlPS, 2019.
[32] Saining Xie, Ross Girshick, Piotr Dollar, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In CVPR, 2017.
452
459
[33] Jaehong Yoon and Sung Ju Hwang. Combined group and exclusive sparsity for deep neural networks. In /CML, 2017.
455
[34] Yang Zhou, Rong Jin, and Steven Chu-Hong Hoi. Exclusive lasso for multi-task feature selection. In AISTATS, 2010.
456
12


Reviews:
[{"review_id": "yXcPHuBtr8R", "reviewer": "Reviewer_mu5S", "summary": "This paper proposes a new differentiable sparsification method to learn sparse structure in neural networks in an end-to-end manner. This objective is straightforward and well-motivated. However, the execution is not novel, comparisons to the SOTA is lacking, reasons for design choices were unsubstantiated with experiments and would thus require additional ablation analysis.\n", "questions": "", "limitations": "", "rating": 4, "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": "## Strengths\nThis paper proposes differentiable sparsification for CNNs and GCNs. The method is straightforward. A potentially novel improvement when compared to DARTS [18] is the inclusion of the proximal operator into the architecture parameter as shown in equation (10) and the evaluation of the backward pass with non-zero surrogate gradients to avoid dead neurons. \n\n## Weaknesses\nTo begin, Section 2 related work is missing a large chunk of alternative methods that can also sparsity neural networks with end-to-end training. For instance, stochastic networks with policy gradients [b,c], other differentiable approaches to sparsity [d,g], and other more modern baselines for comparison, e.g. for pruning [e,f,h,i]. \nThe majority of Section 2.1 “proximal gradient” bears low relevance to the method proposed in the paper, and should be simplified. How does your method compare to proximal-gradient-based pruning such as [a]?\nSection 2.2 has only two references. This subsection require substantial rewrite to include relevant works such as the ones mentioned earlier.\n\nThe experiments on CNNs are lacking. The paper has many magical design choices and could necessitate additional ablation and sensitivity analysis. For instance, the choices of $\\alpha$ and $\\beta$ in Line 204 seem arbitrary. The GCN results are confusing (see Minor issues below), and the reviewer cannot judge its quality in its current presentation.\n\n## Minor issues\n* Line 38: “performed as a separate step separately” repetition.\n* Line 133: “singed” -> “signed”.\n* Line 197: “In network-slimming, λ in Eq. 13 is fixed to $10^{−5}$, but in our approach we vary its value to induce different level of sparsity” It is not clear how this varies the level of sparsity, as in NS the sparsity is mostly determined by $k$ as we keep the top-$k$% of all channels.\n* Line 275: grammatical error.\n* Table 3: The columns are unexplained. What do you mean by “#N.Z”, “MAPE” and “L.R.”? It is also not clear to the reviewer what models I, II and III mean or how they were defined even after reading the appendix.\n* Line 311: Table 4a -> Table 3a.\n* Line 317: Table 4b -> Table 3b.\n\n## References:\n```\n[a]: Li, Yawei et al., Group Sparsity: The Hinge Between Filter Pruning and Decomposition for Network Compression, CVPR 20.\n[b] Louizos et al., Learning sparse neural networks through L0 regularization, ICLR 18. \n[c] Guo, Shaopeng et al., DMCP: Differentiable Markov Channel Pruning for Neural Networks, CVPR 20.\n[d] Kang, Minsoo et al., Operation-Aware Soft Channel Pruning using Differentiable Masks, ICML 20. \n[e] Zhuang et al., Neuron-level Structured Pruning using Polarization Regularizer, NeurIPS 20.\n[f] Li et al.,  EagleEye: Fast Sub-net Evaluation for Efficient Neural Network Pruning, ECCV 20.\n[g] Ning et al., DSA: More Efficient Budgeted Pruning via Differentiable Sparsity Allocation, ECCV 20.\n[h] Chin et al., Towards Efficient Model Compression via Learned Global Ranking, CVPR 20.\n[i] Guo et al., Multi-Dimensional Pruning: A Unified Framework for Model Compression, CVPR 20.\n```\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of the paper is sufficiently discussed in the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "XNzQULLidoe", "reviewer": "Reviewer_bkKy", "summary": "This paper proposes a component-wise network sparsification framework based on proximal gradient descent. In the proposed method, each component is associated with a learnable coefficient which is further regularized through a regularizer. The coefficients learning, based on proximal gradient methods, will be projected/thresholded to zero, indicating the component is dropped. Authors also adopt some tricks to relax the backward gradient flow to ensure the components are not dead always. The experiments show some analysis of the proposed method on channel pruning, discovering neural wirings, and graph structure learning.", "questions": "", "limitations": "", "rating": 5, "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": "originality:\nThe proposed method in the paper is a quite straightforward extension of previous works which use proximal gradient descent to perform network sparsification. The main difference is that the target variable to be regularized is changed to some component coefficients.\n\nquality:\nThe proposed method should be technically sound. However, it seems that there are several potential concerns\n- Although the authors mention that normal sparsification would lead to irregular structures, it seems that there are no experiments to validate that irregular structures could potentially cause some problems. Neural networks are normally randomly initialized with each weight potentially swappable. It's hard to see how this dropping component intuition would be very different/useful in network sparsification.\n- The component size also needs to be specified in prior manually, which introduces another limitation in the proposed method.\n\nclarity: The paper's writing is pretty clear. A small typo: line 133 \"singed\"\n\nsignificance: The proposed method is a simple application of proximal gradient-based sparsification. Doesn't seem like this is a significant method for related fields.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No obvious potential negative societal impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5 - 2 hours (including reading related works)"}, "extra_text": {}}, {"review_id": "WfAZwnVP-qt", "reviewer": "Reviewer_XHsq", "summary": "This study proposes a method that enables differentiable sparsification for deep neural network and can be applied into model compression and architecture learning tasks. Experiments on small datasets are conducted to demonstrate the effectiveness of reducing network sizes and learning network architectures. ", "questions": "", "limitations": "", "rating": 5, "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": "The proposed method is simple. The paper has a clear demonstration. However, this study lacks novelty. The core contribution is an engineering practice composed of the three steps in Eq. 9 - Eq. 11, and the regularization term in Eq. 14. There are variant ways to achieve differentiable zero weights. What is and how to verify the superiority of the proposed method in Eq. 9 – Eq. 11? In experiments, only analytical experiments on small datasets are conducted. There is no comparison with other model compression or architecture search methods on challenging tasks. Therefore, the potential applicability of this study is not convincing. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have no concern with the limitations and societal impact of the study. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "1KHKUMknOwr", "reviewer": "Reviewer_6Lqs", "summary": "This paper presents a network sparsification method. It represents a network as a linear combination of different components, and the weights for different components are parameterized by some unconstrained parameters. By enforcing the Lp norm on the weights of different components, all parameters can be learnt in an end-to-end manner. Then the proposed method is applied to three applications: channel pruning in CNN, Discovering Neural Wirings, and Learning relationship between nodes in Graph. Experiments validate the effectiveness of the proposed solution. ", "questions": "", "limitations": "", "rating": 5, "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": "+The idea of representing the network as a linear combination of different components and sparsify the weights of different components is interesting. \n+The idea of parameterize the weights with unconstrained parameters is interesting. \n+The paper is readable and easy to follow. \n\n\n- The proposed method imposes an Lp norm on the weights. However, in the first application (Channel Pruning), p is set to 1. while in the third application, p is set to 0.5. As stated in the section 3.3, the line before equation 14, p should be less than one. Then why you use p=1 in the first application? Then how different p's affect the final performance?\n- Regarding the baselines in Channel pruning, there are many state-of-the-art methods, however, only NS is compared and it is a relative out-of-date method. More recent methods should be compared.\n- Regarding the first and second applications, only a small dataset is used. More challenging dataset, like ImageNet should be used to further validate the performance of different methods. As reported in previous work, the performance of different methods on different datasets sometimes is not consistent. \n- As  lambda in equation 13 is an important factor for evaluating the sparsity of the network. Then please show how different lambda's affect the performance in the first and second applications. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"ethical_concerns": "No. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method based on sub-differential to sparsifying a network parameters during training. Although this paper contains novel interesting ideas, the results are not convincing nor significant enough to convince the reviewers. The reviews unanimously suggest the quality and significance of this paper is below the standard of the conference. The AC agrees with their recommendations. 
Decision: Reject