Sparsifying Networks via Subdifferential Inclusion
Authors: Sagar Verma
Jean-Christophe Pesquet
Venue:  (2021)
Keywords: neural networks
pruning after training
weight pruning
proximal operator
fixed point iteration

Abstract: Sparsifying deep neural networks is of paramount interest in many areas, especially when those networks have to be implemented on low-memory devices. In this article, we propose a new formulation of the problem of generating sparse weights for a neural network. By leveraging the properties of standard nonlinear activation functions, we show that the problem is equivalent to an approximate subdifferential inclusion problem. The accuracy of the approximation controls the sparsity. We show that the proposed approach is valid for a broad class of activation functions (ReLU, sigmoid, softmax). We propose an iterative optimization algorithm to induce sparsity whose convergence is guaranteed. Because of the algorithm flexibility, the sparsity can be ensured from partial training data in a minibatch manner. To demonstrate the effectiveness of our method, we perform experiments on various networks in different applicative contexts: image classification, speech recognition, natural language processing, and time-series forecasting.

Under review as a conference paper at ICLR 2021
SPARSIFYING NETWORKS VIA SUBDIFFERENTIAL IN- CLUSION
Anonymous authors Paper under double-blind review
ABSTRACT
Sparsifying deep neural networks is of paramount interest in many areas, especially when those networks have to be implemented on low-memory devices. In this article, we propose new formulation of the problem of generating sparse weights for a neural network. By leveraging the properties of standard nonlinear activation functions, we show that the problem is equivalent to an approximate subdifferential inclusion problem. The accuracy of the approximation controls the sparsity. We show that the proposed approach is valid for a broad class of activation functions (ReLU, sigmoid, softmax). We propose an iterative optimization algorithm to induce sparsity whose convergence is guaranteed. Because of the algorithm flexibil- ity, the sparsity can be ensured from partial training data in a minibatch manner. To demonstrate the effectiveness of our method, we perform experiments on various networks in different applicative contexts: image classification, speech recognition, natural language processing, and time-series forecasting.
INTRODUCTION
Deep neural networks have evolved to the state-of-the-art techniques in wide array of applications:
computer vision (Simonyan & Zisserman, 2015; He et al., 2016; Huang et al., 2017), automatic speech recognition (Hannun al., 2014; Dong et al., 2018; Li et al., 2019; Watanabe et al., 2018; Hayashi et al., 2019; Inaguma et al., 2020), natural language processing (Ture et al., 2019; Radford al., 2019; Dai et al., 2019b; Brown al., 2020), and time series forecasting (Oreshkin et al., 2020). While their performance in various applications has matched and often exceeded human capabilities, neural networks may remain difficult to apply in real-world scenarios. Deep neural networks leverage the power of Graphical Processing Units (GPUs), which are power-hungry. Using GPUs to make billions of predictions per day, thus comes with substantial energy cost. In addition, despite their quite fast response time, deep neural networks are not yet suitable for most real-time applications where cemmory-llmited low-cost architectures need to be used. For all those reasons, compression and efficiency have become topic of high interest in the deep learning community.
Sparsity in DNNs has been an active research topic generating numerous approaches. DNNs achieving the state-of-the-art in given problem usually have large number of layers with non-uniform parameter distribution across layers. Most sparsification methods are based on a global approach, which may result in sub-optimal compression for a reduced accuracy. This may occur because layers with a smaller number of parameters may remain dense, although they may contribute more in terms of computational complexity (e.g., for convolutional layers). Some methods, also known as magnitude pruning, use hard or soft- woft-theesholding to remove less significant parameters. Soft thresholding techniques achieve a good sparsity- accuracy trade-off at the cost of additional parameters and increased computation time during training. Searching for hardware efficient network is another area that has been proven quite useful, but requires huge amount of computational resources. Convex optimization techniques such as those used in (Aghasi et al., 2017) often rely upon fixed point iterations that make use of the proximity operator (Moreau, 1962). The related concepts are fundamental for tackling nonlinear problems and have recently come into play in the analysis of neural networks (Combettes & Pesquet, 2020a) and nonlinear systems (Combettes & Woodstock, 2020).
This paper shows that the properties of nonlinear activation functions can be utilized to identify highly sparse subnetworks. We show that the sparsification of a network can be formulated as approximate

---

Under review as a conference paper at ICLR 2021
subdifferential inclusion problem. We provide an iterative algorithm called subdifferential inclusion for sparsity (SIS) that uses partial training data to identify a sparse subnetwork while maintaining good accuracy. SIS makes inference FLOPs than the haselines. For example, SIS for 90% sparse MobileNetV3 on ImageNet- K achieves 66.07% top-1 accuracy with 33% fewer inference FLOPs than its dense counterpart and thus provides better results than the state-of-the-art method RigL. For non-convolutional networks like Transformer-XL trained on WikiText-103, SIS is able to achieve 70% sparsity while maintaining 21.1 perplexity score. We evaluate our approach across four domains and show that our compressed networks can achieve competitive accuracy for potential use on commodity hardware and edge devices.
amall-parameter layers sparse, resulting in models with significantly lower
2 RELATED WORK
2.1 INDUCING SPARSITY POST TRAINING
Methods inducing sparsity after dense network is trained involve several pruning and fine-tuning cycles till desired sparsity and accuracy are reached (Mozer Smolensky, 1989; LeCun et al., 1990;
Hassibi et al., 1993; Han et al., 2015; Molchanov et al., 2017: Guo et al., 2016; Park et al., 2020). (Renda et al., 2020) proposed weight rewinding technique instead of vanilla fine-tuning post-pruning. Net-Trim algorithm (Aghasi et al., 2017) removes connections at each layer of trained network by convex programming. The proposed method works for networks using rectified linear units (ReLUs). Lowering rank of parameter tensors (Jaderberg et al., 2014; vahid et al., 2020; Lu et al., 2016), removing channels, filters and inducing group sparsity (Wen et al., 2016; Li et al., 2017; Luo et al., 2017; Gordon et al., 2018; Yu et al., 2019; Liebenwein et al., 2020) are some methods that take network structure into account. All these methods rely on pruning and fine-tuning cycle(s) often from full training data.
2.2 INDUCING SPARSITY DURING TRAINING
Another popular approach has been to induce sparsity during training. This can be achieved by modifying the loss function to consider sparsity as part of the optimization (Chauvin, 1989; Carreira- Perpiñán & Idelbayev, 2018; Ullrich et al., 2017: Neklyudov et al., 2017). Dynamically pruning during training (Zhu& & Gupta, 2018; Bellec et al., 2018; Mocanu et al., 2018; Dai et al., 2019a; Lin et al., 2020b) by observing network flow. (Mostafa & Wang. 2019; Dettmers & Zettlemoyer, 2020; Evei et al., 2020) computes weight magnitude and reallocates weights at every step. Bayesian priors (Louizos et al., 2017), Lo. L, regularization (Louizos et al., 2018), and variational dropout (Molchanov al., 2017) get accuracy comparable to (Zhu & Gupta, 2018) but at cost of 2 memory and 4x computations during training. (Liu et al., 2019; Savarese et al., 2020; Kusupati et al., 2020; Lee, 2019; Xiao et al., 2019; Azarian et al., 2020) have proposed learnable sparsity methods through training of the sparse masks and weights simultaneously with minimal heuristics. Although these methods are cheaper than pruning after training, they need at least the same computational effort as training a dense network to find a sparse sub-network. This makes them expensive when compressing big networks where the number of parameters ranges from hundreds of millions to billions (Dai et al., 2019b; Li et al., 2019; Brown et al., 2020).
2.3 TRAINING SPARSELY INITIALIZED NETWORKS
(Frankle & Carbin, 2019) showed that it is possible to find sparse sub-networks that, when trained from scratch, were able to match or even outperform their dense counterparts. (Lee et al., 2019) presented SNIP, a method to estimate, at initialization, the importance that each weight could have later during training. In (Lee et al., 2020) the authors perform a theoretical study of pruning at initialization from signal propagation perspective, focusing on the initialization scheme. Recently, (Wang et al., 2020) proposed GraSP, a different method based on the gradient norm after pruning, and showed significant improvement for moderate levels of sparsity. (Ye et al., 2020) starts with a small subnetwork and progressively grow it to a subnetwork that is as accurate as its dense counterpart. (Tanaka et al., 2020) proposes SynFlow that avoids flow collapse of a pruned network during training. (Jorge et al., 2020) proposed FORCE, an iterative pruning method that progressively removes a small number of weights. This method is able to achieve extreme sparsity at little accuracy expense. These
2

---

Under review as a conference paper at ICLR 2021
methods are not usable for big pre-trained networks and expensive as multiple training rounds required for different sparse models depending on deployment scenarios (computing devices).
2.4 EFFICIENT NEURAL ARCHITECTURE SEARCH
Hardware- NAS methods (Zoph al., 2018; Real et al., 2019; Cai et al., 2018; Wu et al., 2019; Tan et al., 2019; Cai et al., 2019; Howard et al., 2019) directly incorporate the hardware feedback into efficient neural architecture search. (Cai et al., 2020) proposes learn single network composing of a large number of subnetworks from which hardware aware subnetwork can be extracted in linear time. (Lin al., 2020a) proposes a similar approach wherein they identify subnetworks that can be run efficiently on microcontrollers (MCUs).
Our proposed algorithm applies to possibly large pre-trained networks. contrast with methods presented in Section 2.1, ours can use small amount of training data during pruning and fewer epochs during fine-tuning. As we will see in the next section, key feature of our approach is that is based on a fine analysis of the mathematical properties of activation functions, so allowing the use of powerful convex optimization tools that offer sound convergence guarantees.
PROPOSED METHOD
3.1 VARIATIONAL PRINCIPLES
basic neural network layer can be described by the relation:
R(Wx b)
(1)
where RM is the input, y R- the output. W N is the weight matrix, RV the bias vector, and R is nonlinear activation operator from RRN to R.N. A key observation is that most of the activation operators currently used in neural networks are proximity operators of convex functions (Combettes & Pesquet, 2020a;b). We will therefore assume that there exists proper lower-semicontinuous convex function ff from R to I U {+oo] such that R = prox q. We recall that is proper lower-semicontinuous convex function if the overs its graph, its epigraph {v. E RN x R f(y) & E). is a nonempty closed convex set. For such a function the proximity operator of at z E R (Moreau, 1962) is the unique point defined as
prox prox)(=) argmin =l==- + PER
follows from standard subdifferential calculus that Eq. (1) can be re-expressed the following inclusion relation:
Wx + b y e afly),
(3)
where ay)) is the Moreau subdifferential of y defined
0f(y) (t R² (Vz {*))(=)) > f(y) + (t|22))))
(4)
The subdifferential constitutes a useful extension of notion differential, which is applicable to nonsmooth functions. The set (5()) is closed and convex and, if satisfies Eq. (1), it is nonempty.
The distance to this set of a point E R. is given by
(2) inf || Cl]. rElf(w)
(5)
We thus see that the subdifferential inclusion in Eq. (3) is also equivalent to
darly) (Wa + y) = 0.
(6)
Therefore, a suitable accuracy measure for approximated values of the layer parameters (W, b) is dar (War b y).
3

---

Under review as a conference paper at ICLR 2021
3.2 OPTIMIZATION PROBLEM
Compressing network consists of sparsification of its parameters while keeping a satisfactory accuracy. Assume that, for a given layer, training sequence of input/output pairs available which results from forward pass performed on the original network for some input dataset of length K. The training sequence is split minibatches of size T so that K JT. The j-th minibatch with j E (1, (1.....J J} is denoted by (Zz,t, I+ In order to compress the network, we propose to solve the following constrained optimization problem.
Problem 1 We want to
minimize g(W,b) (W.JECC
(7)
with
C (WW E RNM R (Vj (I....,))
Σ Cos (Waz, + b vz.)) & Tn) (8)
where g is a sparsity measure defined on N x RRN and rj E [0, +o0 is some accuracy tolerance.
Since, for every j E J), the function (W,b) + Exs Beros.) Waze + b Uj.c) is continuous and convex, C is closed and convex subset of RNXM R. In addition, this set nonempty when there exist W E NxN and E TRN such that, for every j E (1,..., J/} and t E (l...., Th, de ((ss))) (W æjjt + Mj,1 = 0. As we have seen in Section 3.1, this condition is satisfied when [W. b) are the parameters of the uncompressed layer. Often, the sparsity of the weight matrix is the determining factor whereas the bias vector represents small number of parameters, so that we can make the following assumption.
Assumption For every W E RNXM and b E R., g(W,b) h(W) where h is func- tion from I NM to I U {+oo}, which is lower-semicontinuuus, convex, and coercive (i.c. limp h(W) = +oc). In addition, there exists (W, b) E C such that h(W) < +oo and there exists (j*,t") E (1....,,J (I....,T) such that yz- . lies the interior of the range of R.
Under this assumption, the existence of solution to Problem is guaranteed (see Appendix A). A standard choice for such function is the f--nrrm of the matrix elements, h = || I|1- but other convex sparsity measures could also be easily incorporated within this framework, e.g. group sparsity measures. Another point worth being noticed is that constraints other than (8) could be imposed. For example, one could make the following alternative choice for the constraint set
= ((Wbb) E N X N
sup JE JE11....)
das(us.) (W + y5.e) & V
(9)
Although the resulting optimization problem could be tackled by the same kind of algorithm as the one we will propose, Constraint (8) leads to a simpler implementation.
3.3 OPTIMIZATION ALGORITHM
standard proximal method for solving Problem the Douglas-Rachford Rachford algorithm (Lions & Mercier, 1979; Combettes & Pesquet, 2007). This algorithm alternates between proximal step aiming at sparsifying the weight matrix and a projection step allowing a given accuracy to be reached. Assume that solution Problem exists. Then, this algorithm reads as shown the top of the next page.
The Douglas-Rachfort algorithm parameters 7 ]0, +oo and (An)eNN in 10,2 2 such that EnEN Av, 2 - Xx) = +oo. Throughout this article, projs denotes the projection onto a nonempty closed convex set S. Under these conditions, the sequence (W,, b, meN generated by Algorithm is guaranteed to converge to solution to Problem if there exists (W. b) E C such W is point in the relative interior of the domain of & Combettes & Pesquet (2007) (see illustrations in Appendix E).
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Gouglas-Rachforrt algorithm for network compression
Initialize Wo E RNN and by RM
for n = 0,1,... do
W, prox (W,) (w))
(W bn) = projo Wns bn)
Wn+1 Wn An (W,, wn)
bat1= = bn + (bn bn)-
The proximity operator of function yh has closed-fore for standard choices of sparsity measures' For example, when h = || II this operator reduces to a soft-thresholding (with threshold value y) of the input matrix elements. In turn, since the convex set C' has an intricate form, explicit expression of projc does not exist. Finding an efficient method for computing this projection for large datasets thus constitutes the main challenge in the use of the above Douglas- Rachford strategy, which we will discuss in the next section.
3.4 COMPUTATION OF THE PROJECTION ONTO THE CONSTRAINT SET
For every mini-batee index j E {I...., J}. let us define the following convex function:
(4(W, E NXM x R c,, T
(Waj, (W + b- Vz,c) - Tn.
(10)
==
Note that, for every j E J]. function ej is differentiable and its gradient at (W, E
RNXM x RN is given by
(e,(W,b) (Wwe, (b,)(,,)),,
(11)
where
T (w, =2 Σ 3 Vbc = Σ 6zPt
(12)
with
(Vt (I....,,T} T}) = = WIja + Vj.1 projas(us.s) (WIj, + b- Mj.r).
(13)
A pair of weight/bias parameters belongs to C' if and only if it lies in the intersection of the 0-lower level sets of the functions (cy)ısıEJ. To compute the projection of some (W, E RNN R.V onto this intersection, we use Algorithm 2 (I) || denotes here the Frobenius norm).
This iterative algorithm has the advantage of proceeding in a minibatch manner. allows us to choose the mini-batch index ju at iteration in a quasi-cyclic manner. The simplest rule is to activate each minibatch once within J successive iterations the algorithm so that they correspond to epoch. The proposed algorithm belongs to the family of block-iterative outer approximation schemes for solving constrained quadratic problems, which was introduced (Combettes, 2003). The convergence of the sequence (Wn, b,, meN generated by Algorithm 2 to projo b) is thus guaranteed. One of the main features of the algorithm is that it does not require to perform any projection the O-lower level sets of the functions Cj. which would be intractable due their expressions. Instead, these projections are implicitly replaced by subgradient projections, which are much easier to compute in our context.
3.5 DEALING WITH VARIOUS NONLINEARITIES
For any choice of activation operator R. we have to calculate the projection onto 0f(y) for every vector y satisfying Eq. (1). This projection is indeed required in the computation of the gradients of functions (c)), as shown by Eq. (13). Two properties may facilitate this calculation. First, if f is differentiable at y, then 0f(y) reduces to singleton containing the gradient (.()) of
Inttp://prox// mi tyw.yyyoooo.....oo
5

---

Under review as a conference paper at ICLR 2021
Algorithm 2: Minibatch algorithm for computing proje (W, b)
Initialize: Wo = W and by = b
for n 0....... do
Select a batch index in E J} if ej, (W,, bn) > then
Compute Vweg, (Wn, bn) and Vbeg, (Wn, bn) by using Eq. (12) and Eq. (13)
own- Vwaga.n (W (W (., 1
(W..b.) (.,)) Vwei, (W.,b,)
(W
56, = I1Wesn. (W..bn 11l +1 Vors, (Wn.b))11
Sn (W,.da) VEesn (Wn.ba)
T tr( W
n
SW,) + (bg bn) 5bn
pan - 1W Wn
2
bbo
ba
Pn 18W, +
18b
Sn = Mn x
if Sn and Tn 0 then
W Wn+1 Wn 8Wn
bn+1 = b, öbn
else if S, > and nT u 2 6, then
W Wn+1 Wo (1+ Ez joW,
bn+1 bo (1 + In jôbn
else
W Wn+1 = Wn + ve (nn(Wo - Wn) - k,,
in
bn+1 = b, + Sn (n (bo bn.) Mn ob..)
else
Wn+1 Wn
bn+1 bn
at y, so that, for every E RN,, projar() = vf(y). Second, R is often separable, i.c. consists of the application argument. According to our assumptions, there thus exists proper lower-semicontinuuus convex function from I to R U {+0 such that p prox, and, for every = (5 IECENN E RN, f(=) Di=n (((())). This implies that, for every = (C(
scalar activation function p: - E to each component of its input
RR,, projas()(=)) = (proja (((t))) IEKEN, where the components of y denoted by (v(t)) Based on these properties, a list of standard activation functions is given in Table 1, for which we provide the associated expressions of the projection onto 0p. The calculations detailed in Appendix B.
An example of nen-sepaaable activation operator frequently employed in neural network architectures the softmax operation detined as: (Vz (( IEKEN (((R)
RR R(2)) ΣN exp(c())
exp(c("))
IEKEN
It is shown in Appendix C that, for every y (v( JEEKEN in the range of R.
(Vz E R projar(y) = Q(1) + 1T(2 - Q(v)) 1.
(14)
N
where 1 [I....,1]7
1j N and Q(v) (1) + 1- -x(()))))))))))))))) (((())))))))) ISSEN.
3.6 SIS ON MULTI-LAVERED NETWORKS
Algorithm 3 describes how we make use of SIS for a multi-layered neural network. We use a pretrained network and part of the training sequence extract layer-wise input-output features. Then apply SIS each individual layer by passing n, layer parameters (W(,88 and extracted input-output features (I-1) (0) to Algorithm 1. The benefit of applying SIS to each layer independently is that we can apply SIS on all the layers of network in parallel. This reduces the time required to process the whole network and compute resources are optimally utilized.

---

Under review as a conference paper at ICLR 2021
Name
p())
projar(w)(S)
Sigmoid (1+0-9)-12
In(v 1/2) in(u-1/2)
Arctangent
(2/T) arctan(()
(an(Tv/2)
0 if <> 0 O < 2
ReLU max(<.0)
is otherwise
( if <> ac otherwisc
0 (1/a- 1)e otherwise
0
Leaky ReLU
if (v= and Ç 0)
Capped ReLU ReLUu.())
(v and Ç 0)
otherwise
cc (x(ex)(<) 1)
if < otherwisc
if > 0
ELU
In
p+a
otherwise
v = and Ç & -a v cjO, or (u and ( ax) otherwise
(5 (G+)))eLU2.1( +a)
v av a
QuadReLU
4a
a
Table 1: Expression of projastui(S (S) for Ç R and v in the range p. for standard activation functions a is positive constant.
Algorithm 3: Parallel SIS for multi-layered network
Input: input sequence X e M compression parameter 77 0, weight matrices (1)) ..... W(4), and bias vectors 6(1), ...., (...,,(4)
6(")...,,
(0) - X
for 1 1, .,.... do
Y R& (1-11) + b(1))
W ((0) SIS W b((), (1), (((-1))
Output: W (()) and B()) ....., (()
EXPERIMENTS
In this section, conduct various experiments to validate the effectiveness of SIS in terms of the test accuracy vs. sparsity and inference time FLOPs vs. sparsity by comparing against RigL. (Evci et al., 2020). We also include SNIP (Lee et al., 2019), GraSP (Wang al., 2020), SynFlow (Tanaka et al., 2020), STR (Kusupati et al., 2020), and FORCE (Jorge et al., 2020). These methods start training from a sparse network and have some limitations when compared to methods that prune a pretrained network Blalock et al. (2020); Gale et al. (2019). For fair comparison we also include LRR (Renda et al., 2020) which uses a pretrained network and multiple rounds of pruning and retraining by leveraging learning rate rewinding. The experimental setup is described in Appendix D.
4.1 MODERN CONVNETS ON CIFAR AND IMAGENET
We compare SIS with competitive baselines on CIFAR- for three different sparsity regimes 90%, 95%, 98%, and the results are listed in Table 2. It can be observed that LRR, RigL and SIS are able to maintain high accuracy with increasing sparsity. LRR performs better than both RigL and SIS for VGG19 CIFAR-10 at 90% and 95% sparsity. When compared SNIP, our method achieves impressive performance for VGG19 on CIFAR-100 (58.46 -> 71.17). the case of ResNet50, SIS outperforms all the other methods for CIFAR-10/100 except for CIFAR-100 90%.
7

---

Under review as a conference paper at ICLR 2021
Dataset
CIFAR-10
CIFAR-I00
Pruning ratio
90%
95%
98%
90%
95%
98%
VGG19 (Baseline)
94.23
74.16
SNIP (Lee et al., 2019)
93.63
93,43
92.05
72.84
71.83
58.46
GraSP (Wang ct al., 2020)
93.30
93.04
92.19
71.95
71.23
68.90
SynFlow (Tanaka et al., 2020)
93.35
93,45
92.24
71.77
71.72
70.94
STR (Kusupati et al., 2020)
93.73
93.27
92.21
71.93
71.14
69.89
FORCE (Jorge al., 2020)
93.87
93.30
92.25
71.9
71.73
70.96
LRR (Renda et al., 2020)
94.03
93.53
91.73
72.12
71.36
70.39
RigL (Evci et al., 2020)
93.47
93.35
93.14
71.82
71.53
70.71
SIS (Ours)
93.99
93.31
93.16
72.06
71.85
71.17
ResNet50 (Baseline)
94.62
77.39
SNIP (Lee et al., 2019)
92.65
90.86
87.21
73.14
69.25
58.43
GraSP (Wang al., 2020)
92.47
91.32
88.77
73.28
70.29
62.12
SynFlow (Tanaka et al., 2020)
92.49
91.22
88.82
73.37
70.37
62.17
STR (Kusupati et al., 2020)
92.59
91.35
88.75
73.45
70.45
62.34
FORCE (Jorge et al., 2020)
92.56
91.46
88.88
73.54
70.37
62.39
LRR (Renda et al., 2020)
92.62
91.27
89.11
74.13
70.38
62.47
RigL (Evei et al., 2020)
92.55
91.42
89.03
73.77
70.49
62.33
SIS (Ours)
92.81
91.69
90.11
73.81
70.62
62.75
Table 2: Test accuracy of sparse VGG19 and ResNet50 on CIFAR-10 10 and CIFAR-100 datasets.
Sparsity
60%
80%
90%
96.5%
Top-1 Acc(%)
Top-1 Acc(%)
Top-1 Acc(
Top-1 Acc(%)
FLOPs
FLOPs
FLOPs
FLOPs
SNIP (2019)
73.95
1.88G
69.67
941M
65,30
409M
54.70
292M
GraSP (2020)
74.02
1.63G
72.06
786M
68.14
470M
51.31
290M
SynFlow (2020)
74.13
1.61G
72.18
776M
68.26
465M
60.14
288M
STR (2020)
76.82
1.59G
75.29
705M
74.13
341M
67.20
117M
FORCE (2020)
73.71
1.39G
70.96
685M
69.78
455M
59.00
276M
IRR (2020)
77.10
2.04G
76.61
918M
75.92
584M
72.13
371M
RigL (2020)
76.50
1.79G
75.10
920M
73.00
515M
72.70
257M
SIS (Ours)
77.05
1.34G
76.96
647M
76.31
298M
73.11
101M
Table 3:
Test Top-1 accuracy and inference FLOPs of sparse ResNet50 on ImageNet where baseline accuracy and inference FLOPs are 77.37% and 4.14G, respectively.
Sparsity
75%
90%
LRR
RigL
SIS (Ours)
LRR
RigL
SIS (Ours)
VI (70.90)
68.79
69.97
70.11
66.59
67.10
67.15
FLOPs (569M)
498M
461M
367M
401M
331M
284M
V2 (71.88)
68.83
69.60
69.83
64.17
65.23
65.11
FLOPs (300M)
267M
211M
182M
192M
174M
162M
V3 (72.80)
68.97
70.21
70.47
64.32
65.13
66.07
FLOPs (226M)
187M
198M
172M
185M
167M
151M
Table 4: Test accuracy and inference FLOPs of sparse MobileNet versions using RigL and SIS on ImageNet, baseline accuracy and inference FLOPPs shown in brackets.
Due to its small size and controlled nature, CIFAR- may not appear sufficient to draw solid conclusions. We thus conduct further experiments on ImageNet using ResNet50 and MobileNets. Table 3 shows that, in the of ResNet50, LRR performs marginally better than SIS at 60% sparsity.
8

---

Under review as a conference paper at ICLR 2021
At 80%, 90%, and 96.5% sparsity SIS outperforms all other methods. For all sparsity regimes, SIS achieves least inference FLOPs. RigL achieves these results in same training time as SIS with less training time FLOPs. This may be related to the fact that SIS achieve better compression in the last layer before SoftMax. MobileNets are compact architectures designed specifically for cssource-oonstrained devices. Table 4 shows results for Rigl. and SIS Mobile We observe that SIS outperforms all MobileNet versions at 75% sparsity level. For a 90% sparsity level, SIS outperforms RigL for MobileNet VI and V3 whereas, for MobileNetV2, RigL performs slightly better than SIS at 90% sparsity level. In all the cases, we can see that the resulting SIS sparse network uses fewer FLOPs than RigL. possible explanation for this fact is that SIS leverages activation function properties during the sparsification process.
4.2 SEQUENTIAL TASKS
Network
JASPER
Transformer XL
N-BEATS
WER
FLOPs
PPL
FLOPs
SMAPE
FLOPs
Dense
12.2
4.53G
18.6
927.73G
8.3
41.26M
SNIP (Lee et al., 2019)
14.3
2.74G
24.6
398.92G
10.1
21.45M
LRR (Renda et al., 2020)
13.7
2.61G
23.1
339.21G
9.3
14.47M
RigL (Evci al., 2020)
13.9
2.69G
22.4
326.56G
10.2
15.13M
SIS (Ours)
13.1
2.34G
21.1
290.38G
9.7
14.21M
Table 5: Test accuracy and inference FLOPs of JASPER, Transformer-Xe and N-BEATS at 70% sparsity.
Jasper on LibriSpeech. Jasper is a speech recognition model that uses 1D convolutions. The trained network is 333 million parameter model and has word error rate (WER) of 12.2 on the test set. We apply SIS on this network and compare with RigL and SNIP in terms of sparsity. Table reports WER and inference FLOPs for all three methods. SIS marginally performs better than SIS on this task in terms WER and FLOPs for 70% sparsity. The main advantage of our approach lies in single pre- mre-trained Jasper network and achieve different sparsity level for
the fact that different types of deployment scenarios with less computational resources than Rigl..
Transformer-XI. on WikiText-103. Transformer-XL. a language model with 246 million param- eters. The trained network on WikiTexxt100 has perplexity score (PPL) of 18.6. Table 5, we see that SIS performs better than SNIP and RigL in terms of PPL and has 68% fewer inference FLOPs. This is due the fact that large language models can be efficiently trained and then compressed easily, but training sparse sub-network from scratch is hard (Li et al., 2020), as is the case with SNIP and RigL.. SNIP uses one-shot pruning to obtain a random sparse sub-network, whereas RigL able to change its structure during training, which allows it to perform better than SNIP.
N-BEATS M4. N-BEATS is very deep residual fully-connected network to perform forecasting in univariate time-series problems. is a 14 million parameter network. The Symmetric Mean Absolute Percentage Error (SMAPE) of the dense network the M4 dataset is 8.3%. We apply SIS on this network and compare its performance with respect to RigL and SIS. SIS performs better than both methods and results 65% fewer inference FLOPs.
5 CONCLUSION
In this article, we have proposed a novel method for sparsifying neural networks. The compression problem for each layer has been recast as the minimization of a sparsity measure under accuracy constraints. This constrained optimization problem has been solved by means of advanced convex optimization tools. The resulting SIS algorithm is i) reliable in terms of iteration convergence guarantees, ii) applicable to wide range of activation operators, and iii) able to deal with large datasets split into mini-batches. Our numerical tests demonstrate that the approach is not only appealing from theoretical viewpoint but also practically efficient.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alireza Aghasi, Afshin Abdi, Nam Nguyen, and Justin Romberg. Net-trim: Convex pruning of deep neural networks with performance guarantee. In NeulPS, 2017.
Kambiz Azarian, Yash Bhalgat, Jinwon Lee, and Tijmen Blankevoort. Learned threshold pruning. arXiv preprini arXiv:2003.00075, 2020.
Heinz H. Bauschke and Patrick L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2019.
Guillaume Bellec, David Kappel, Wolfgang Maass, and Robert Legenstein. Deep rewiring: Training very sparse deep networks. In ICLR, 2018.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? In I. Dhillon, D. Papailiopoulos, and V. Sze (eds.), Proceedings of Machine Learning and Systems, volume 2, pp. 129 146, 2020. URL https: /ttp///oooeddeeeecoooooooooee iig. mlsys. org/ httpppaper/202/// File/eeaieeee /2dd//ddddaaa/// 8 f006 8 62 wetee223eeddeedeeeeeeeee Patsss-pppppppppe
Tom B. Brown, Benjamin Pickman Mann, Nick Ryder, Melanie Subbiah, Jean Kaplan, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 14165, 2020.
Han Cai, Jiacheng Yang, Weinan Zhang, Song Han, and Yong Yu. Path-level network transformation for efficient architecture search, arXiv preprint arXiv:1806.0200 02639, 2018.
Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct neural architecture search on target task and hardware. In ICLR, 2019.
Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. Once-for-all: Train one network and specialize for efficient deployment. In ICLR, 2020.
Miguel Á. Carreira-Perpiñánn and Yerlan Idelbayev. "Leaming- CoamringCCompressioon" algorithms for neural net pruning. In CVPR, 2018.
Yves Chauvin, A back paopaproongntion algorithm with optimal use of hidden units. In NeurIPS. 1989.
Patrick Louis Combettes. A block-iterative surrogate constraint splitting method for quadratic signal recovery. IEEE TSP, 2003.
Patrick Louis Combettes and Shan-Chrittophe Pesquet. A Rauhlos-Rachford splitting approach to nonsmooth convex variational signal recovery. IEEE JSTSP, 2007.
Patrick Louis Combettes and lean-Christophe Pesquet. Deep neural network structures solving variational inequalities. SVVA, 2020a.
Patrick Louis Combettes and Jean-Christore Christophe Pesquet. Lipschitz certificates for layered network structures driven by averaged activation operators. SIMODS, 2020b.
Patrick Louis Combettes and Zev Woodstock, A fixed point framework for recovering signals from nonlinear transformations. arXiv preprint axXiv:2003.0/260, 2020.
Xiaoliang Dai, Hongxu Yin, and Niraj K. Jha. NeST: A neural network synthesis tool based grow-and prune paradigm. JEEE TC, 2019a.
Zihang Dai, Zhilin Yang, Yiming Yang. Jaime Carbonell, Quoc Le, et al. Transformer-XL: Attentive language models beyond a fixed-length context. In ACL, 2019b.
Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance. arXiv preprint arXiv: 2020.
Linhao Dong, Shuang Xu, and Bo Xu. Speech-transformeet A no-recurrence sequence-to-ssquuence model for speech recognition. In ICASSP, 2018.
Utku Evci, Erich Elsen, Pablo Castro, and Trevor Gale. Rigging the lottery: Making all tickets winners. In ICML,, 2020.
10

---

Under review as a conference paper at ICLR 2021
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In ICLR, 2019.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv 2019, URL pestts://arxie org/ abs /100/199..00 09574.
e-prints,
Ariel Gordon, Elad Eban, Ofir Nachum, Bo Chen, Hao Wu, et al. Morphnet: Fast simple resource- constrained structure learning of deep networks. In CVPR, 2018.
Yiwen Guo, Anbang Yao, and Yurong Chen. Dynamic network surgery for efficient dnns. In NeurIPS, 2016.
Song Han, Jeff Pool, John Tran, and William J. Dally, Learning both weights and connections for efficient neural networks. In NeurIPS, 2015.
Awni Hannun, Carl Case, Jared Casper, Bryan Catanzaro, Greg Diamos, Erich Elsen, al. Deep- speech: Scaling up end-to-end speech recognition. arXiv preprint arXiv:1412.5567, 2014.
Babak Hassibi, David G. Stork, and Gregory Wolff. Optimal brain surgeon and general network pruning. In ICNN, 1993.
Tomoki Hayashi, Ryuichi Yamamoto, Katsuki Inoue, Takenori Yoshimura, Shinji Watanabe, al. ESPnet-TTH Unified, reproducible. and integratable open source end-to-end text-to-speech toolkit. arXiv preprint 1910..9900000 2019.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, Quoc Le, and Hartwig Adam. Searching for mobilenetv3. In ICCV, 2019.
Gao Huang, Zhuang Liu, and Kilian Q. Weinberger. Densely connected convolutional networks, In CVPR, 2017.
Hirofumi Inaguma, Shun Kiyono, Kevin Duh, Shigeki Karita, Nelson Enrique Yalta Soplin, et al. ESPnet-ST: All-in-one speech translation toolkit. arXiv preprint arXiv:2004.10234 2020.
Max Jaderberg, Andrea Vedaldi, and Andrew Zisserman. Speeding up convolutional neural networks with low rank expansions. In BMVC, 2014.
Pau Jorge, Amartya Sanyal, Harkirat Behl, Philip Torr, Grégory Rogez, and Puneet Dokania. Pro- gressive skeletonization: Trimming more fat from a network initialization. arXiv preprint wwXiv:2006.09081, 2020.
Aditya Kusupati, Vivek Ramanujan, Raghav Somani, Mitchell Wortsman, Prateck Jain, Sham Kakade, et al. Soft threshold weight reparameterization for learnable sparsity. In ICML, 2020.
Yann LeCun, John S. Denker, and Sara A. Solla. Optimal brain damage. In NewrIPS, 1990.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. SNIP: Single-shot network pruning based connection sensitivity. In ICLR, 2019.
Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip S. Torr. A signal propagation perspective for pruning neural networks at initialization. In ICLR, 2020.
Yognjin Lee. Differentiable sparsification for deep neural networks. arXiv preprint 1rXiv:1110.03201, 2019.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for
efficient convnets. In ICLR, 2017.
Jason Li, Vitaly Lavrukhin, Boris Ginsburg, Ryan Leary, Oleksii Kuchaiev, Jonathan M. Cohen, Huyen Nguyen, and Ravi Teja Gadde. Jasper: An end-to-end convolutional neural acoustic model. In Interspeech, 2019. 2019.
11

---

Under review as a conference paper at ICLR 2021
Zhuohan Li, Eric Wallace, Sheng Shen, Kevin Lin, Kurt Keutzer, Dan Klein, et al. Train large, then compress: Rethinking model size for efficient training and inference of transformers. arXiv preprint arXiv:2002.11794, 2020.
Lucas Liebenwein, Cenk Baykal, Harry Lang. Dan Feldman, and Daniela Rus. Provable filter pruning for efficient neural networks. In ICLR, 2020.
Ji Lin, Wei-Ming Chen, Yujun Lin, John Cohn, Chuang Gan, and Song Han. Mcunet: Tiny deep learning on iot devices. In NeurIPS, 2020a.
Tao Lin, Sebastian U. Stich, Luis Barba, Daniil Dmitriev, and Martin Jaggi. Dynamic model pruning with feedback. In ICLR, 2020b.
Pierre-Louis Lions and Bertrand Mercier. Splitting algorithms for the sum of two nonlinear operators. SIAM Journal on Numerical Analysis, 1979.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell, Rethinking the value of network pruning. In ICLR, 2019.
Christos Louizos, Karen Ullrich, and Max Welling. Bayesian compression for deep learning. In NeurIPS, 2017.
Christos Louizos, Max Welling, and Diederik P. Kingma, Learning sparse neural networks through lo regularization. In ICLR, 2018.
Zhiyun Lu, Vikas Sindhwani, and Tara N. Sainath. Learning compact recurrent neural networks, In ICASSP, 2016.
Jian-Hao Luo, Jianxin Wu, and Weiyao Lin. Thinet: A filter level pruning method for deep neural network compression. In ICCV, 2017.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In ICLR, 2017.
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H. Nguyen, Madeleine Gibeseu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature Communications, 2018.
Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Variational dropout sparsifies deep neural networks. In ICML, 2017.
Jean-Jacques Moreau. Fonetions convexes duales points proximaux dans espace hilbertien. Comptes rendus hebdomadaires des séances de l'Académie des sciences, 1962.
Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterizztion. In ICML, 2019.
Michael C. Mozer and Paul Smolensky. Skeletonization: A technique for trimming the fat from a network via relevance assessment. In NeurlPS, 1989.
Kirill Neklyudov, Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov. Structured bayesian pruning via log-normal multiplicative noise. In NeurlPS, 2017.
Boris N. Oreshkin, Dmitri Carpov, Nicolas Chapados, and Yoshua Bengio. N-BEATS: Neural basis expansion analysis for interpretable time series forecasting. In ICLR, 2020.
V. Panayotov, G. Chen, D. Povey, and S. Khudanpur. Librispeech: An ASR corpus based on public domain audio books. In ICASSP, 2015.
Sejun Park, Jacho Lee, Sangwoo Mo, and Jinwoo Shin. Lookahead: A far-sighted alternative of magnitude-based pruning. In ICLR, 2020.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models unsupervised multitask learners. 2019.
12

---

Under review as a conference paper at ICLR 2021
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V. Le. Regularized evolution for image classifier architecture search. In AAAI, 2019.
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. In ICLR, 2020.
Pedro Savarese, Hugo Silva, and Michael Maire. Winning the lottery with continuous sparsification. arXiv preprint arXiv:arXiv: /912.04499/104 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. ICLR, 2015.
Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc V. Le. Mnasnet: Platform-aware neural architecture search for mobile. In CVPR, 2019.
Hidenori Tanaka, Daniel Kunin, Daniel Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. arXiv preprint arXiv:2006.05667, 2020.
2019. Iulia Ture, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Well-read students learn better:
On the importance of pre-training compact models. arXiv preprint
Karen Ullrich, Edward Meeds, and Max Welling. Soft weight-sharing for neural network compression. In ICLR, 2017.
Keivan Alizadeh vahid, Anish Prabhu, Ali Farhadi, and Mohammad Rastegari. Butterfly transform: An efficient fft based neural architecture design. In CVPR, 2020.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In ICLR, 2020.
Shinji Watanabe, Takaaki Hori, Shigeki Karita, Tomoki Hayashi, Jiro Nishitoba, et al. Espnet: End-to-end speech processing toolkit. In Interspeech, 2018.
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. In NeurIPS. 2016.
Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang, Fei Sun, Yiming Wu, et al. FBNet: Hardware-aware efficient convnet design via differentiable neural architecture search. CVPR, 2019.
Xia Xiao, Zigeng Wang, and Sanguthevar Rajasekaran. Autoprune: Automatic network pruning by regularizing auxiliary parameters. In NeurlPS. 2019.
Mao Ye, Chengyue Gong, Lizhen Nie, Denny Zhou, Adam Klivans, and Qiang Liu. Good subnetworks provably exist: Pruning via greedy forward selection. In JCML, 2020.
Jiahui Yu, Linjie Yang, Ning Xu, Jianchao Yang, and Thomas Huang. Slimmable neural networks. In ICLR, 2019.
Michael Zhu and Suyog Gupta. To prune, or not to prune: Exploring the efficacy of pruning for model compression. In ICLR, 2018.
Barret Zoph, Vijay Vasudevan, Jonathon Shiens, and Quoe V. Le.. Learning transferable architectures for scalable image recognition. In CVPR, 2018.
13

---

Under review as a conference paper at ICLR 2021
APPENDICES
A EXISTENCE OF A SOLUTION TO PROBLEM UNDER ASSUMPTION
Under Assumption 2, Problem is equivalent to
minimize h(W) (W,))EC
(15)
with
C= ((Wb) NNM RR- max (W(W,) & <0).
(16)
JE(I....))
where the functions (c))) are defined in Eq. (10). These functions being convex, +
mI...( Cj is convex (Bauschke & Combettes, 2019, Proposition 8.16). We deduce that
inf NNN ( b) also convex function (Bauschke Combettes, 2019, Proposition 8.35).
Since + 3 TTT V is finite valued. It is thus continuous on R.VxMM (Bauschke & Combettes, 2019, Corollary 8.40). Let us now consider the problem:
minimize 1(W) W Weleeago V
(17)
where le v is the O-lower level set of y defined
levgo V (W E RNX
((W)) < 0),
(18)
V being both convex and continuous, lo V is closed and convex. According Assumption 2, there exists (W, b) E N TR- such that h(W) +00 and ((W, b) 0, which implies that I (W) < O. This shows that leveu V has nonempty intersection with the domain of h. By invoking now the coercivity property of h, the existence solution W to Problem (17) is guaranteed by standard convex analysis results (Bauschke & Combettes, 2019, Theorem 11.10).
To show that (W, b) solution (15), sufficient show that there exists E ER such that Φ(W b) (W). This is equivalent to prove that there exists solution b to the problem:
minimize BER
+ (WW,D) b).
(19)
We know that 4(W,) .) is continuous function. In addition, we have assumed that there exists (j", (²") E [I......}} x (1......7 T) such that .j-.e" is an interior point of R(R"), which is also equal to the domain of 0f and subset of the domain of Since is continuous the interior of its domain, (5(μ), is bounded (Bauschke & Combettes, 2019, Proposition 16. 7(i)). Then das(u)e..>) .-) is coercive, hence cy- (W, is coercive, and so is ( 2 Cj- (W,)). The existence of b thus follows from the Weierstrass theorem.
B RESULTS IN TABLE
The results are derived from the expression of the convex function &o associated with each activation function p (Combettes Pesquet, 2020a, Section 2. (Combettes & Pesquet, 2020b, Section 3.2).
Sigmoid
1 (52 (52 1144
(C+
+ (n1//22 -
2
(AC E RR) p(()
if [c| 1/2
(20)
1/4
if |<| = 1/2
+00
if |<] > 1/2.
The range of the Sigmoid function is 1/2 and the above function is differentiable on this interval and its derivative at every E| - 1/2, is
('(v) In(u + 1/2) - In(v 1/2) v.
(21)
We deduce that, for every Ç E R, projap(u) (S) ('()).
14

---

Under review as a conference paper at ICLR 2021
Arctangent
2 cos In -
22 if <<
(AÇ IR p(()
(22)
+00,
if k
By proceeding for this function similarly to the Sigmoid function, have, for every p(R)
]
1.16
(VC E IR) proiap(u) = x0 (v) = lan(Tu/2)) v.
(23)
ReLU
0
if f 0 otherwise.
(VS E IR)
x0()
(24)
+oc
For every E ((R) = [0, +ool, we have
{0}
if >
0G(()= =
(25)
[1 00,0
if v = 0.
We deduce that
0
if vシ 0or
(AC R) projac(e)(()
(26)
l
otherwise.
Leaky ReLU
(VC IR) ((() = 00
(1/a- ((1)=(11a-
if <>0 0
(27)
(E0.
Since this function is differentiable on R, for every IR,
if v3>0 projap(e)(S) = ((())) = (1/a-1)v otherwise.
0
(AC E R)
(28)
Capped ReLU
0
if [0,a] otherwise.
(VC E R)
p(()
(29)
+o0
We have thus for every U E a).
{0}
if u E |00, af
0p((v)
] 00, 0]
u = 0
(30)
10, 00
if u =
This leads
{
s if (u 0 and ( < 0)
SA) E R)
proja (9)
(v= and ( > 0)
(31)
otherwise.
ELU
0
if Ç > 0; if a <<<
(5 + a:) In (<a) - -
(AÇ E IR)
+(()
2
(32)
a :
if ( -a
+00,
if << aa.
This function being differentiable on p(R) =] a, +00%. we have for every E| ax, +00l,
if .ッ0 1ba - otherwise.
(VC E IR)
projac (C) = =p'(v) = In
(33)
15

---

Under review as a conference paper at ICLR 2021
Quad Unlike the previous ones, this function does not seem to have been investigated before. can be seen as a surrogate to the hard swish activation function, which is not a proximal activation function. Let define
if ç
SAC E R)
((() =
+ Va - ac ac
if ç E [0,
(34)
2
+
í > a.
+p is lower-semicontimmuus convex function whose subdifferential is
- 00, -a]
if u = 0 if E|0,a]
(Vu +oo
ap(u)=
{-v 22 -
(35)
{v a}
if a.
From the definition of the proximity operator, for every (v. () E IR, we have u (S) if and only if
< E 00, a|
if = 0 if v e]0, a] if v
Ç E u 0p(u)
+
= avu a
2u
if ( E] x0, -a]
v
((+a)?
if E] - a, a)
(36)
4a
Cta
if > a.
2
This shows that (C) = (4a) (4a) + a ReLU2a(U + a). In addition, for every u E [0, +oo it follows from Eq. (35) that the projection onto 0f(v) is
v = 0 and ( < -a
- U + 2v av av0aa a
if v E|0, a]
(VC E R) projas( (S)
(37)
(v 0 and <> -a)
v > a.
C SOFTMAX ACTIVATION
Let C' denote the closed hypercube [0, 1| let V be the vector hyperplane defined as
N
V = { = (5(x) JICKEN ERN
Σ
(K) =
(38)
and let A be the affine hyperplane defined
N A = f= (C)) ERN
Σ ( = 1 = V 4
(39)
1=1
where u = [l,..., T 1/N E N If R the Softmax activation operator, the convex function f such that prox, (Combettes & Pesquet, 2020a, Example 2.23):
[(z) { EM (((()))
if EnA otherwise,
(Vz ((())))
(40)
+00
where
= (in)- E
(VC E [0, +ool)
(41)
2
(with the convention 0l 0). The latter function can be extended on RR say by quadratic function on] co, 0j, yielding convex function & which is differentiable on R. We have then
N
(vz = (5 E R f(z) = Σ (() + (ona(z),
(42)
16

---

Under review as a conference paper at ICLR 2021
where tona denotes the indicator function of the intersection of C and A (equal to 0 this set and +00 elsewhere). It then follows from standard subdifferential calculus rules that, for every y = (v(H) TR..
0f(y)= = MIRRE Nc(y) Na(v),
(43)
where şă' is the derivative of q and No denotes the normal cone to a nonempty closed convex set D, which is defined
(D( = E (Vz E D) (1 | = y) < 03-
(44)
Thus (1) = Nv (v) is the orthoooal space V of V. Let us now assume that y E R(R cjo, 1( Then, since y is an interior point of C, Ny) {0).
We then deduce from Eq. (43) that
0f(y) = Q(v) + V
(45)
where Q(v) = (66' (s DICKEN = (In +1 ((()) EgENN follows that, for every 2 TR:
(r Q(v) projy (2 Q(v)).
(46)
By using the expression of the projection projy = ld projy onto hyperplane V, we finally obtain
= Qvy) + T (2 - Q(1)) (z)
1.
(47)
N
D EXPERIMENTAL SETUP
PyTorch is employed to implement our method. We use and extend SNIP and RigL code available here", LRR GraSP SynFlow", STR,, and FORCE'. In order to manage our experiments we use Polyaxon on Kubernetes" cluster and use five computing nodes with eight V100 GPUs each. Floating point operations per second (FLOPs) is calculated as equal to one multiply-add accumulator using the code
SIS has the following parameters: number of iterations of Algorithm 1, number of iterations of Algorithm 2, step size parameter y in Algorithm 1, constraint bound parameter 7) used to control the sparsity, and relaxation parameter An X of Algorithm 1. In our experiments, the maximum numbers of iterations of Algorithm and Algorithm 2 are set to 2000 and 1000, respectively. À is set to 1.5 and is set to 0.1 for all the SIS experiments. value depends on the network and dataset. With few experiments, we search for a good 1) value that gives suitable sparsity and accuracy.
VGG19 and ResNet50 on CIFAR-10/100. We train VGG19 on CIFAR-10 for 160 epochs with batch size of 128, learning rate of 0.1 and weight decay of 5 x 10-4 applied at epochs 81 and 122. A momentum of 0.9 is used with stochastic gradient descent (SGD). We make of 1000 images per training class when using SIS. We fine-tune the identified sparse subnetwork for 10 epochs at a learning rate of 10-3, For CIFAR-100 we keep the same training hyperparameters as for CIFAR-10. When applying SIS to the dense network, we use 300 images per class from the training samples. We fine-tune the identified sparse subnetwork for 40 epochs on the training set with learning rate of 10 3 ResNet50 employs the same hyperparameters as VGG19, except the weight decay that we set to 10 When applying SIS to train dense ResNet50, we use the same partial training set and the same hyperparameters during fine-tuning. In case of VGG19 for CIFAR-10 and CIFAR-100, we found that 7) values in range (1.5, 2) works best for sparsity range (90%, 98%). In case of ResNet50, 7) values in range (1, (1 is used.
otter/////////hhboooooooooooooor http://hhwh.../ooopppooooooo///a vis iasiia//ppu-rrr/offiiiaalll
/nttps://github.
Pattps//Albernttee.i///.
17

---

Under review as a conference paper at ICLR 2021
ResNet50 on ImageNet We use the weights of ResNet50 pre- pre-trained on ImageNet available at PyTorch hub" When applying SIS to the dense pre-trained network we use 20% samples per class from the training set. We fine-tune the identified sparse subnetwork for 40 epochs on the training set with a learning rate of 10-1 We use different y values in range (0.7, 1.5) for sparsity range We found that 1j 2.3 achieves 96.5% sparsity.
(0%).
MobileNets on ImageNet We use MobileNetVI dense pre- trainaiieed model from here" and Mo- bileNetV2 from PyTorch hub 13 In case of MobileNetV3, we replace the hard swish activation function used in the original paper Howard et al. (2019) with our QuadReLU function (see the last row of Table 1). We use hyperparameters provided the original paper to train MobileNetV3. When use 20% samples per class from the training set. We fine-tune the identified sparse subnetwork for 30 epochs on the training set with a learning rate of 10-4, 4, For MobileNets, we search values in range (0.6, 1.75) for sparsity range (75,90) 90).
applying SIS to the dense pre-trained MobileNets,
Jasper on LibriSpeech A BxR Jasper network has B blocks, each consisting of R repeating sub-blocks, Each sub-block consists of ID-Convolution, Batch Normalization, ReLU activation, and Dropout. The kernel size of convolutions increases with depth. The network has one convolution block at the beginning and three at the end. We train network of 13 encoding blocks and one decoding block, having 54 ID-Convolution layers on the LibriSpeech dataset. The total number of parameters in our trained network is 333 million. Jasper network is trained on train-clean- 100, train-clean-360. and train-other-500 splits of the LibriSpeech dataset (Panayotov et al., 2015). The training configuration can be found here" 14 We use train-clean- 100 when using SIS. We fine-tune the identified sparse sub-network on the completed training set for ten epochs with learning rate of 10-4. We use 1) values in range (0.6, 1.75) for sparsity range (70, 90).
Transformer-XI. on WikiText-103 We train the Transformer-Xi XL network (Dai al., 2019b) on the base version of WikiText- 103 (Merity et al., 2017). We use the training configuration available here!5. We use 10% of the training set articles when using SIS. We use 1) values in range (0.5, 0.75) for sparsity range 70).
N-BEATS on M4 We train the interpretable architecture network of N-BEATS on the M4 dataset. The trained network has six residual blocks. Each block consists of four fulny-comnected layers and two linear projection layers. With 24 fully-comected layers, this network has 14 million trainable parameters. To compare different methods, we only train a single network a 48-hour window instead of 180 networks on different timescales. We use the training configuration available here 16 The training set has 50K time-series samples. We use 10K training samples generate sparse sub-network using SIS. We use values in range (0.75, 1.5) for sparsity range (70,90).
E EMPIRICAL CONVERGENCE ANALYSIS
We illustrate the convergence of our method on LeNet-FCN trained on MNIST. LeNet-FCN is a fully-connected network having four layers with 784-300-1000 1000-300-00 nodes (two 300 nodes and one 1000 node hidden layers). Figure shows the convergence of SIS when applied to dense LeNet-FCN. We observe that the convergence is smooth and SIS finds a global solution for the first (ReLU activated) and last (softmax) layer cases. This fact is in agreement with our theoretical claims. SIS attains sparsity of 99.21 % at an error of 1.86%. The trained dense network has an error of 1.65%. This result is obtained at 7) = 2.
toml http:///wwmaaccceollllleeeeee//r
ementA
interpretable.gin
18

---

Under review as a conference paper at ICLR 2021
6000
5590
5000
5600
4500
4500
4000
4000
2500
2500
0.00
2000
200
4.00
600
200
400
6.0
5000
10000
15000
Iterattonn
Iterations
Iterations
(
(b)
(C)
150
2500
2000
1.00
70
1000
60
500
Baratioon
Baertions
Iteraionss
(d)
(c)
(f)
Figure Convergence of SLIC: Top row shows the first layer (ReLU activated) and bottom row shows the last layer (softmaxed) in LeNet-FCN. (a) and (d) shows the evolution of the maximum value Cmax of the constraint functions (cy) (b) and (e) shows the evolution of |[]]] in Algorithm iterations. (c) and (f) shows [W]] evolution in Algorithm 2.
100
100
90
95
Sparsity (%)
Accuracy (%)
80
90
70
85
60
-50
80
0.0
0.5
1.0
1.5
2.0
2.5
3.0
n
Figure 2: Effect of on LeNet-FCN
The 7 parameter our algorithm controls the accuracy tolerance. The higher, the more tolerant are on the loss of precision and the sparser the network is. Thus. this parameter also controls the network sparsity. The choice of this parameter should the result of accuracy-sparsity trade-off. This is illustrated in Figure 2.
19


Reviews:
[{"review_id": "rBN5QqNMOS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper propose a network compression algorithm by exploiting a reformulation of activation function as proximity operator. The latter is an optimization problem whose optimality condition reveals constraints on the weight matrix W of the neural net. The main idea is then to \"biasedly\" select W as a minimizer of a sparsity inducing penalties under a relaxation of the previous optimality conditions. The authors provide details on solving such problem as well as numerical experiments that leads to similar results than competitors.\n\n- The proposed algorithm does not significantly improves the accuracy of estimators (eg convNet in Cifar) when compared with actual methods.\n\n- The claim in the conclusion \"SIS is reliable in term of convergence guarantee\" is not supported by clear evidence. I did not find any such convergence proof in the paper. Once the SIS compression is used, it unclear that the same accuracy than the non-compressed NN is preserved.\n\n- The core optimization problem (7) is solved approximately with Douglas-Rachford iterations. Neither the effect of the optimization error nor the selection of eta is clearly discussed.\n\n- Should be nice if the authors can provide a pseudo-code of the overall SIS strategy in a practical deep neural net (not only one layer). As stated, the main idea is lost in the technical details for solving (7) (where there is few or no new contribution).", "extra_scores": {}, "extra_text": {}}, {"review_id": "f1TE2IKKj3j", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe authors propose a new algorithm for inducing sparsity in the weights of neural networks after training. The proposed algorithm exploits the properties of commonly used activation functions to cast the sparsification problem as the minimization of a sparsity measure subject to approximation accuracy constraints. The proposed problem can be solved using convex optimization.\n\nPros:\n\nThe authors’ insights about popular activation functions and the approach used to cast the sparsification problem as a convex optimization problem are clever and interesting. The authors presented experiments on a wide range of deep learning models and tasks.\n\nCons:\n\nSome of the details of the authors experiments are not clear or potentially misleading:\n1. Some results presented for existing techniques are from those techniques’ original papers, but some results were re-run by the authors. For example, consider the ResNet-50 results on ImageNet (table 3, left). The RigL authors did not present results at 60% sparsity, and Appendix D does not include details on how this number was generated beyond the authors using the released code with RigL. The numbers at 80% and 90% sparsity are taken from the RigL paper. However, these numbers were achieved with 5x the number of training steps which was enabled by the reduced number of FLOPs used by RigL during training because it maintains a constant level of sparsity throughout the training process. They also use non-uniform distributions of sparsity across the layers of the network which affects the number of FLOPs in the resultant network. The author’s of this paper report a lower top-1 accuracy at 60% sparsity than the RigL paper reports at 80% sparsity, which leads me to believe that the training conditions (time, sparsity distribution) are not the same. Similarly, all of the RigL results for MobileNet family models (table 3, right) appear to have been run by the authors and the training setup details are not clear. For these results generated by the authors of this paper, they should also detail the amount of hyperparameter tuning performed for these baseline, as this can make a large difference in accuracy. I focused here on RigL because it appears to be the most commonly used baseline by the authors of this paper, but it seems likely that these observations apply to other techniques as well.\n2. Using RigL as the “state-of-the-art” baseline for most comparisons is not entirely fair given it has additional capabilities (i.e., the ability to enable sparse training by maintaining a constant number of parameters across training) compared to the authors’ proposed post-training sparsification algorithm. Sparse training (i.e., sparse-to-sparse training) is known to be a more difficult problem than dense-to-sparse training [1] or post-training sparsification. It is good to include RigL for comparison, but this distinction should be made clear and other techniques that have comparable ability to the proposed technique should be included as well.\n\nMy suggestion to the authors are the following:\n1. All results should be reported as accuracy with a given parameter count and accuracy with a given FLOP count. Ideally, these tradeoff curves should be plotted across a range of accuracies and FLOP counts. This helps to avoid many of the pitfalls in the comparisons of model compression approaches details by [2] and [3].\n2. Make it clear that some algorithms under comparison have additional capabilities compared to the proposed approach (e.g., RigL with sparse training).\n3. Add comparisons with other algorithms of similar capability to the proposed approach. The magnitude pruning approach of Zhu & Gupta [1] would be ideal for this I believe.\n\nComments:\n\nThe brackets are backwards in the last paragraph on page 4. I would encourage the authors to explain more of the background of their approach (proximal operators, convex optimization, etc.) in sections 3 and 4. Many of those working in model compression who would be interested in this work will not be familiar with these topics.\n\nReferences:\n\n1. https://arxiv.org/abs/1710.01878\n2. https://arxiv.org/abs/1902.09574\n3. https://arxiv.org/abs/2003.03033 \n\n[original score: 3 (clear rejection)]\n11/24: Updated score based on updates from the authors. The addition of FLOP counts and more baselines in the experiments section greatly improved the paper. The proposed approach appears to achieve excellent FLOP-accuracy tradeoffs relative to existing approaches.\n\n[2nd score: 6 (marginal acceptance)]\n11/30: Updated score based on updates from the authors. The discrepancy with some baseline numbers has been resolved and the authors added clarifying information to the paper regarding the counting of FLOPs.", "extra_scores": {}, "extra_text": {}}, {"review_id": "c5orApcaLtc", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper the authors propose a new model compression method based on subdifferential inclusion. The key idea is to make the outputs of the neurons in the sparse and dense networks at the same input close enough. They rewrite the activation function as the proximity operator of a proper convex function and finally formulate the compression problem into a constraint minimization problem using the technique of subdifferential inclusion. They conduct a series of experiments to evaluate the performance of their proposed methods.\n\nPositive aspects:\n1.\tThe idea of this paper makes sense. \n2.\tThe experiment results show that the proposed method can achieve better performance than the baselines under this paper’s experimental setting. \n3.\tThis paper is well written and easy to follow. \n\nMy concerns are:\n\n1. In the proposed model, we need to choose proper value of $\\eta$ for each layer, which is the required accuracy of the neuron’ output after compression. I understand that as reported by the authors in this paper, only in few experiments, they need to search for a good $\\eta$. However, I think it is non-trivial to find proper value for $\\eta$. I mean that different layers could have different tolerances on accuracy.  Since our goal is to achieve high test accuracy in the compressed network instead of the accuracy of the neuron’ output after compression, if we can find better values for $\\eta$ we could achieve higher test accuracy. In other words, as it is challenging to find  near optimal $\\eta$ for each layer, we could not reduce the network into very small size. \n\n2. Because of my above concern, I recommend the authors to give more results of compressing networks into much smaller sizes. For example, in RigL, the size of ResNet50 on ImageNet is compressed by more than 97%.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "VxTDcltfegt", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nThe authors pose sparsification as a subdifferential inclusion problem, a novel formulation that results in quite meaningful results on established benchmarks/tasks. The paper overall is very well-written with a detailed overview of current sparsification techniques and how the proposed method differs.\n\n## Pros\n* Very comprehensive analysis and proofs (which seem correct, although not thoroughly verified)\n* Empirical results justify this novel approach across the board\n\n## Suggestions\nThe computational characteristics of using SIS has not been characterized in the manuscript; it is no very clear what the complexity of training a large model is using the proposed approach. The authors suggest their training approach is efficient, but do not provide any empirical results or further justification. For example, all of the results in Table 3 and Table 4 can have an additional column that characterizes the time to train. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I have serious concerns about how experiments are reported in this paper. Most methods tried to compare at an iteration complexity of roughly 100 epochs because it is known more computation improves performance very significantly but the computational resources are limited for many researchers, especially in academia. While this convention may not be the ideal way to compare different methods, for fairness, this practice has been followed in most of previous papers. 

Unfortunately this paper disregarded this practice, and on Imagenet the reported results from previous works were mixed at 100 epochs (e.g. STR) and at 500 epochs (rigL — which was explicitly marked to be 5x in the original paper) without any clarification, and the only other method in the table showing comparable performance to the proposed method, LRR,  also requires many more than 100 epochs. Moreover, the authors did not explicitly disclose the equivalent epochs of their algorithms in the Imagenet experiments, and this is not acceptable. Based on the information inferred from the current writing, it is extremely likely that significant unfair advantages were given to the proposed algorithms. 

Since the authors did not report experiments appropriately,  this paper cannot be accepted in its current form regardless of other potential merits of the proposed methods. I hope the authors view this outcome positively, and proactively fix the problem. If in revised versions, the experiments are reported according to the common practice, I am sure the work would become publishable.

Decision: Reject