Reducing the number of neurons of Deep ReLU Networks based on the current theory of Regularization
Authors: Jakob Heiss
Alexis Stockinger
Josef Teichmann
Venue:  (2021)
Keywords: Reduction
Compression
Regularization
Theory
Pruning
Deep
Interpretability
Generalization

Abstract: We introduce a new Reduction Algorithm which makes use of the properties of ReLU neurons to reduce significantly the number of neurons in a trained Deep Neural Network. This algorithm is based on the recent theory of implicit and explicit regularization in Deep ReLU Networks from (Maennel et al, 2018) and the authors.

We discuss two experiments which illustrate the efficiency of the algorithm to reduce the number of neurons significantly with provably almost no change of the learned function within the training data (and therefore almost no loss in accuracy).

Under review as a conference paper at ICLR 2021
REDUCING THE NUMBER OF NEURONS OF DEEP RELU NETWORKS BASED ON THE CURRENT THEORY OF REGULARIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce new Reduction Algorithm which makes use of the properties of ReLU neurons reduce significantly the number of neurons in a trained Deep Neural Network. This algorithm is based on the recent theory of implicit and explicit regularization in Deep ReLU Networks from (Maennel et al, 2018) and the authors.
We discuss two experiments which illustrate the efficiency of the algorithm to re- duce the number of neurons significantly with provably almost change of the learned function within the training data (and therefore almost no loss in accu- racy).
INTRODUCTION
1.1 MOTIVATION
In this work, investigate particular type of deep neural network. Its architecture (see section 2 can be better understood, thanks to the previous work on wide shallow neural networks: Neyshabur let (2014)) ( et al. (2019); { Savarese al, :2019]|[illiann) Heiss et al. (2019) and unpublished work of the authors on deep neural networks (with arbitrarily many inputs and outputs).
al. (2019); Maennel (2018);
These results state that f2 weight regularization on parameter space is equivalent to L1-typed P- functionals on function space under certain conditions. This implies that the optimal function could also be represented by finitely many neurons (Rosset et al. 2007).
With the knowledge of these properties, we were able to design reduction algorithm which can reduce infinitely wide (in practice: arbitrarily wide) layers in our architecture to much smaller layers. This allows us to reduce the number of neurons by 90% to 99% without introducing sparsity (which allows more efficient GPU- "PU-implemmenttionn (Gale et al.) 2020)) and with almost no loss in accuracy.
This can be of interest for deploying neural networks on small devices or for making predictions which are computationally less costly and less energy consuming.
1.2 LITERATURE / LINK TO OTHER RESEARCH
Many papers have been written on the subject of reducing neural networks. There the approach of weight pruning, by removing the least salient weights (LeCun et al., 1990; Hassibi & Stork
1993 Han et al. 2015 Tanaka et al. 2020). different technique pruning neurons Mariet & Sra 2215 He et al. (2014); SSrinivas & Babu (2015), which does not introduce sparsity in the network by removing single weights, but reduces the number of neurons. For CNNs there are ways to prune the filters (Li al. 2016). In transfer learning, one can prune the weights with decreasing magnitude Sanh et al. 2020 All these techniques require the same steps: train a large network, prune and update remaining weights neurons, retrain. And for too much pruning, the accuracy of the pruned models drops significantly, also might not always be useful to fine-tune the pruned models (Liu
al. 2018).

---

Under review as a conference paper at ICLR 2021
Another approach is knowledge distillation (Hinton et al. 2013 Ba & Caruana 2014) where one establishes a teacher/student relation between a complex and simpler network.
The lottery ticket hypothesis (Frankle & Carbin 2018) states that "a aundomly-nitializee dense neural network contains a subnetwork that is initialized such that-when trained in isolation match the test accuracy of the original network after training for at most the same number of iterations".
In this work, the method can be related neuron pruning, in that already-trained network. We are, however, trying to preserve the learned function contrary to the cited techniques which focus the loss function and where pruning results in different learned function. Therefore, in our algorithm, the neurons are not only pruned but rather condensed, put together into new neurons which contain all the information learned during training. Our method, hence, does not require retraining. But it is beneficial to further retrain the network, and reduce it again, in an iterative process.
working directly large
2 DESCRIPTION OF THE ARCHITECTURE
Starting from traditional Shallow Neural Network with ReLU activation function (see fig. T (which contains a single hidden layer) and is & regularized, we will define two variants One Stack Network. First, by adding direct (or skip) connection between the input layer and the output layer (see fig. 2). one can obtain the simplified One Stack Network.
Second, by adding layer in the middle of this direct (skip) connection, Network (see fig. B). This new layer contains neurons with a linear activation function (the identity function multiplied by constant). It contains many neurons the minimum between the number of neurons in the input layer and the number of neurons in the output layer, it also has no bias.
get One Stack
Furthermore, call it the affine layer and the weights before and after it the affine weights. These new weights can also be & regularized, but typically by different hyperparameter than the non-linear weights.
ReLU
RcLU
Input
RaLU
Inpux
Output
Lincar
Figure 2:
Schematic repre-
Figure 1: Schematic repre- sentation of Shallow Neural Network
Figure/ Schematic repre-
sentation of a Shallow Neural Network with a skip connec- tion
sentation of One Stack
The architecture that we are going to study can be described as a sequence of stacks, or a Deep Stack Network. We repeat the pattern described above (see figs. [nd Since the output layer is at the end of the architecture, we call all intermediate layers related to the output layers as introduced earlier (typically containing few neurons dy): bottlenecks. The bottlenecks contain neurons with linear (identity) activation function. For every stack, all parameters are regularized except for the biases in the bottleneck.
2

---

Under review as a conference paper at ICLR 2021
RAUI
LiNEO
Figure 4: Schematic representation of sim- plified three-stacked network
Schematic representation of three-stacked network which will be studied in more detail in the following work
Figure 5:
We recommend using higher learning rate for the affine weights. In experiments, used ten-times higher learning rate for the affine weights.
For every stack j. the weights and biases connecting the previous input the (infinitely-wide My oo) ReLU layer written VG) Rayxd and b(1) R",, the ones connecting to the bottleneck written WG) Rd,x,, and clt) E Rd.
Remark 2.1. (ordinary fully connected deep neural network) Note that algorithm could also be applied to an ordinary fully connected deep ReLU neural network and would output neural network with skip connections. But if every second layer is much wider (dj < ny), we have much better theoretical understanding of what is happening and typically we can get better test accuracy with fewer neurons. We don't use ReLUs the bottlenecks for easier interpretation. The compression-rate would not suffer if we apply our algorithm on architectures without affine weights.
CONSEQUENCES FROM P-FUNCTIONAL REGULARIZATION THEORY
If we choose the numbers ny of hidden nodes sufficiently large for each stack while we keep finite bottleneck dimensions dj the authors have shown an unpublished paper that solution of the optimization problem
NN g-x with d e arg min (I() x11012
can be characterized as the solution of a much easier to interpret optimization problem
NN 8-x E arg min (L + AP(f))
(2)
where we optimize over all continuous functions so we do have care about repre- sentable as a neural network
According to the unpublished paper by the authors (similarly to the work by Neyshabur et al. (201)); Ongie et al. (2019); (Savarese et al. (2019); Williams et al. (2019); Heiss et al. (2019)), we can obtain the P-functional P of the deep stacked neural networks from the P-functional P, of a single stacks,
inf P()) freasse f= froutt o (Pi(1) PP(()) .... Posacks (fistccss)
For some functions P(f) oc. E.g. idga R2 IR2 results in P(idza) if one of the bottlenecks has dimension less than E {1,..., #stacks 1} :d

---

Under review as a conference paper at ICLR 2021
For single wide shallow neural network ge
(Lee L
|ea(r)" g(r)
P=(f))= =
min CER
dr ds + 11c112 where (4)
13
gdg
as
a (x(r) = 0
&o E C(RR, (() vs E S0-1,
lim (r(()) = and lim m 7-0-00
+ Ör
handles the boundary condition, S denoted the (d di-diennsinn unit sphere and have a weighing function ((()) v For the other types of stacks shown Figures 2 and the corresponding P-functionals would only need minor modifications. If one would not regularize the affine weights (skip connections) the theory would drastically change because P would assign to many highly oscillating functions if #stacks 2 2, but in practice implicit regularization would weaken this effect. For this paper, the most important aspect of eqs. (3) and (4) is that there is Il-ll2 (instead of 11 inside the integral, which reminds very much an I1-nomm Therefore the function optimizing eq. (2) can be represented by finite number of neurons (Rosset et al., 2007]. Similarily Maennel et al. (2018) found that also without explicit regularization gradient decent favours solutions which could represented by much smaller networks well.
In the following we observe that this finite numbers ny can be very low in practice.
4 REDUCTION ALGORITHM
We will now consider a one-stack network according to the description of the architecture given above (see fig. 3). Therefore, we can fix j and write W := WD) for example in this case. Then, the reduction be applied similarly every stack.
4.1 REMOVING AND REPLACING OUTSIDE NEURONS
The main idea of this step is to combine the information of all the non-linear (ReLU) neurons whose kink positions outside the convex hull of the previous stack's representation of the training data into the affine neurons.
We define the outside neurons those neurons that will always return positive numbers for all training data points. Therefore we find two cases. Either the activation function the outside neuron acts as zero function in which case we can simply remove from the ReLU layer as it makes no contribution to the learned function, or the activation function of the outside neuron acts as identity function. In the latter case, the contribution of the neuron the leameed function is affine and we can add it to the affine weights and remove it from the ReLU layer. In order to do this, we will define W Watine and Callin-
always return strietly
Since p. (r)" can be distribution instead of an function we integration-es e.g. fe [|l(a,, B) 6o(r)]], dr Va² + 32. More generally we redefine these integrals fa h (Il)(r))la) dr = lime-sot Sa ([]f(r)) (eesello)ll)) dr with the help of a convolution which in- finitesimally smoothens the function distribution f. This results for example in fg [1 dr = co and
generalized notion of
max (0.(1 1
fx
dr
g(r)
'I the biases (5) not regularized one could omit the weighting function in theory, but because of implicit regularization would still observe the qualitative phenomena that second derivative gets expensive far away from the origin.
'If V and b were fixed randomly and only W (and were trained, there would be square in the integral (Heiss al. 2019.
4

---

Under review as a conference paper at ICLR 2021
Walline
Wk 2k
KEM
(5)
Cafline
by Wk:
KEM
where M is the set of outside neurons whose activation function is positive for all training data points. Note that out any replacement since they do not contribute to the learned function. Note as well that are column vectors and U2 are row vectors and their multiplication in that order gives matrix. There- fore, Watine is the result of sum of matrices and Cafline is vector, both summarize the contributions of all outside neurons the learned function.
remove the neurons whose activation function acts
function with-
We are now finally able to remove the outside neurons and add their contributions to the affine weights. The question we ask ourselves now how do we determine which neuron is an outside neuron?
We decided loop through every ReLU neuron, then check their prediction for every training data point. If the prediction was always zero or always strictly positive, we could be sure that we found an outside neuron. Of course such a method is also computationally expensive, and would hence be very impractical if we had many neurons and many training data points. But we observed empirically that it was not necessary to loop through every training data point (more on this in the experimentation chapter).
Remark 4.1. I. Exactly speaking, the learned function will not the same as before. In fact, will be different outside of the convex hull of the training data. But these changes further smoothen the extrapolation behavior of the learned function without affecting training accuracy. Removing the outside neurons does change the function on the training data and it does not change the stack's function inside the convex hull of the previous stack's 's representation of the training data.
4.2 REMOVING THE WEAKEST NEURONS
The main idea of this step is to prune the neurons which do not add much to the learned function.
This can be done by calculating the quantity / ||
1|2 + 12 ||wxll for each neuron k. We sort these quantities and remove the weakest ones whose sum is less than certain tolerance. Determining this tolerance also serves as hyper-parameter tuning.
4.3 CLUSTERING THE REMAINING NEURONS
The main idea of the clustering step is to combine the information of the remaining neurons into fewer neurons. This would not work that well without the steps before.
We first group the neurons according to their rinkesepresnntttiion, using (weighted) k-means cluster- ing. up to us to determine the number of clusters, and hence the final number of neurons after reduction, because for every cluster we will define one neuron summarizing all the information. The kink-represeentation of every neuron is computed as following: concatenation of by and u Tvalla"
[|0g 11
and are weighted according to: || ll ||wxll2-
First, the new kink position will be determined according to this formula:
Σx
[w 1
<
(6)
Ee lo0k 12
'Now we can add Catine to the biases of the output (or bottlencck!) layer. Singular Value Decomposition is going to be applied to Watine and we obtain three matrices U, Σ and V, which allows to update the affine
weights by adding U VE to the affine weights hetween the affine and the output (or bottleneck!) layer. Note that v E represents the component-wise square root computation of the diagonal matrix Y.
affine weights between the input and affine layer, and by adding vI V
5

---

Under review as a conference paper at ICLR 2021
We define the strength:
Σ we 1luxl12
Finally define the new v, b, and wt
w Ex wk 110x l12
V 9(5)
0 En | ll2 uk
(8)
V (E)
>> |lakk
Mell22
b = - |0||2
With ((5) v and the index of the neurons in a selected cluster. The new v, 6, and w can then be assigned to new single neuron which will replace all the neurons contained in the same cluster.
5 EXPERIMENTS
We performed two experiments. First, one-dimensional easy to visualize example. Second, train the architecture on the MNIST dataset (handwritten digit recognition).
5.1 COMPOSITE SINUS
At first, we perform simple experiment on artificially-generaii data We create a map : RT æ + f(x) == 3Trinn (1.....7 from a one-dimensional input to a multi-dimensional output. All the outputs are functions of the sine the (scaled) input.
We choose architecture with three stacks (sce fig. 5), and d, 1 neuron in each bottleneck. We train the network at first without regularization, and then with some regularization. The plots are given before and after reduction in figs. [6 and The green curves show the function learned by the stacks themselves, while the red curves show the composition of the function learned by the network up that stack. The yellow, red and blue points visualize the contribution of every neuron by taking the kink-positions & -by as z-axis and we uu We and (Lg(EN) respectively all neurons. vk
ez
One can observe that the intermediate (or hidden) stacks learn the inside function (the sine, see figs. 66a and 6b), and that the last stack learns the composite functions square function, the cubic function, etc. see figs. 7c 7e for example)
top of the sine (the
There is almost difference of the plots after reduction, except of course for the yellow, red and blue points which are less numerous, and are at the right places: at the nonlinearities, where the contributions of the neurons left essential.
The number of ReI.U neurons in each stack and the MSE at every step of the algorithm is presented in Table
Steps
112
17.3
Train MSE
Test MSE 0.0290
Full (wide) network
1024
1024
1024
0.0195
Replacing outside neurons
287
117
0.0195
0.0290
Removing weak neurons
194
29
3
0.0196
0.0271
Clustering
9
6
0.0198
0,0271
Table 1: Number of neurons for each stack and accuracy at every step of the Reduction Algorithm
Some noise was added to data, it was taken from normal distribution scaled by 0.05.
"Of course all these functions can have different scaling, can be shifted and mirrored horizontally and vertically, and will he more regularized with respect P which can lead different extrapolation behavior.

---

Under review as a conference paper at ICLR 2021
First stack
(b) Second stack
(c) Reduced first stack
(d) Reduced second stack
Figure 6: The first two plots correspond to the deep network before reduction, respectively the last two plots correspond network after reduction
(a) One kink
(b) Absolute value
(c) Square
(d) Sign Function
WM
HMAA
(e) Cubic
Sine
Exponential
(h) Reduced kink
(i) Reduced absolute value
Reduced Square
(k) Reduced sign function
Reduced cubic
(m) Reduced sine
(n) Reduced exponential
Figure 7: The first seven plots correspond to the deep network before reduction, respectively the last seven plots correspond to network after reduction

---

Under review as a conference paper at ICLR 2021
5.2 MNIST
The last one-dimensional example was hopefully very intuitive and visual, yet would now be interesting to test the architecture on a higher-dimeesional dataset. We chose to apply it to MNIST, the very popular handwritten digit recognition dataset.
In fig. g we visualize the comparison between our Reduction Algorithm and the standard pruning method as implemented by Tensorflow (neither the reduced model nor the pruned model were re- trained). The first two plots (training and testing) compare the two methods for ten separate models which were trained then automatically reduced (given different drop in accuracy thresholds between 10-8 and 10-2) and pruned for various compression rates. The training scheme was always the same:
trained slightly with no regularization and then trained with increasing regularization, de- creasing learning-rate, and increasing batch-size using an adam optimizer. We chose three stacks with n 1024 neurons in the ReLU layer and d 16 neurons in the bottleneck layer per stack.
We observe that with no loss in accuracy (10 (10-8) we achieve a compression factor of at least 9 for each seed (typically more than 12). This fits nicely to the theory, that the learned function equation needs a finite number of neurons nj (independent of the original n2 as will be also discussed In the next paragraph) and all other neurons are redundant. Thus, fig. [ suggest that the theoretical ni is probably below 100 in this scenario. If we reduce the network to the suggested n;, our algorithm would misclassify typically around 100 times less images of the training set than the standard pruning for the same compression factor and the same seed. We can also see that if we require the train or test misclassification be below any threshold less than 1% respectively 2% our method clearly outperforms the standard pruning method for every seed.
meag Sude selverts
rederct veluerts
Figure 8: Training and Testing error (in %) for ten different initial seeds (each seed represented by a different color)
Figure also shows two plots which compare the Reduction Algorithm and the pruning method, for different number of neurons n, in the ReLU layer of every stack. As one can easily see, the com- pression factor goes up as the number of neurons increases (per stack, for three stack and d, = 16 neurons in the bottleneck layer) and the plots help visualize that we can indeed reduce the networks to a rather constant number of neurons n < 100 per stack (no matter how many neurons n, we use), which illustrate the result of the theory in section 3 aboutt a finite number of neurons needed to represent the Iearned function.
6::80
1014
1004
Figure 9: Training and Testing error (in %) for different number of neurons per stack
8

---

Under review as a conference paper at ICLR 2021
Figure 10 compares the two methods for different number of epochs using the same training scheme as explained above, where we just multiply the number of epochs by some increasing num- ber and using the same architecture with three stacks (nz 1024 and dj 16). One can also from these plots the importance of training for some time, in order to approach a perfectly trained model (which would be necessary in eq. T for the theory in section 3 to hold), indeed the clear trend is that the compression factor increases as the training time increases.
Indentt getiiccoock
X-M
2 2-1
44.00
8:00
2-1
2-33
2--21
Figure 10: Training and Testing error (in %) for different number of epochs
CONCLUSION AND FURTHER WORK
In this paper, we have introduced a neural network architecture which allows to be reduced signifi- cantly in the sense that we can remove or replace many of its ReLU neurons by fewer ReLU neurons. This property alone is already of interest for number of reasons evoked in the introductory section. We could also analyze the learned function of each stack and observe the composition of functions.
Inspired by the lottery ticket hypothesis, we could argue that it would be difficult train smaller neural network to generalize as well as the reduced model (when both have the same dimension).
Worth noting is that if one tries to evaluate an upper bound of the generalization gap (difference between the empirical eтror and true error) based on the sum of the weights, (Kawaguchi et al.) 2017]. one could potentially find better estimation by taking the sum of the weights after reduction.
Also of interest is that, after the reduction algorithm was applied, we obtain a fully- coly--connected neural network. Therefore this method of reduction/coopprssion could be further improved by applying for example weight pruning on top of it.
There are many possibilities for future work, and many are going to be explored very soon. We want to investigate every step of the Reduction Algorithm in more detail whether it is for checking fewer training data points by choosing them non-randomly in the first step, or finding a better and more efficient way to cluster the remaining neurons in the last step.
Similar ideas (of reducing the number of neurons) could potentially be applied to the bottleneck layer (at least the second and third step of the algorithm, since they do not require the presence of affine weights). Investigating the performance of the algorithm on different datasets and comparing it other neural network architectures is certainly of interest well as extending it to be used in CNNs and RNNs.
Since our algorithm is highly theory driven, we might use these ideas to better theoretically explain the lottery ticket hypothesis (Frankle & Carbin 2018).
REFERENCES
Jimmy Ba and Rich Caruana. Do deep nets really need to be deep? In Advances in neural informa- tion processing systems. pp. 2654 2662, 2014. http:h
nips. ctt.lpss.ccppp/////e//
484-do- net.s
net s real -
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. anXiv preprint arXiv:1803.03633, 2018. btRpstts::/// htlttpps//axxi..oo/////./
03635

---

Under review as a conference paper at ICLR 2021
Trevor Gale, Matei Zaharia, Cliff Young, and Erich Elsen. Sparse gpu kernels for deep learning. arXiv preprint wrXiv:2006.10901 2020.
10901
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in neural information processing systemss, pp. 1135- 1143, 2015. URL httthhtpp/ppeeeee
cc/ ait.s.cc/aaarrsSf---aaaaaaaooo--
andconnections
Babak Hassibi and David G Stork. Second order derivatives for network pruning: Optimal brain
Surgeon. In Advances in neural information processing systems, pp. 164-171, 1993. URLhttp: //papers , nips. cc wwcp/pppeee.. httpppppppppp// 647 second order - for network pruning opt imal- Drain- surgeon. pdf
Tianxing He, Yuchen Fan, Yanmin Qian, Tian Tan, and Kai Yu. Reshaping deep neural network for fast decoding by node-pruning. In 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 245-249. IEEE, 2014. URL
e.org/ httpg//bbbrracttcocueeee
6853595
Jakob Heiss, Josef Teichmann, and Hanna Wutte. How implicit regularization of Neural Networks affects the learned function Part I, November 2019. URL httpps://axxi: wwt.vv.rrggabbbs/aeeeeee
02903
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint arXiv:1503.02533 2015. URL https: wttpww/w.rrg/bb///...oooo 02531
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. arXiv preprint arXiv:1710.05440 2017. httpps::/aaxii.orr///aaaaa
05468
Yann LeCun, John S Denker, and Sara Solla. Optimal brain damage. In Advances in neural information processing systems, pp. 598-605, 1990. URL htth:t::// //tpper//ppprss.ee coappersniis..om htppsccc/pp. pap
er/250-opt htt.::-pttaaa---braaa-----aaaaaa pdf
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for 2016. URL httts:://axxl..oortt
efficient convnets. arXiv preprint
111608.08710.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. arXiv preprint 11X00:18100005270, 2018. TRl.hhtts://arxivvorr ab
8/1810. 05270
Hartmut Maennel, Olivier Bousquet, and Sylvain Gelly. Gradient Descent Quantizes ReLU Network Features. arXiv e-prints, art. arXiv:
arXiv:1803.0836) 803.08367, March 2018. URL http:s////axxi..rrr.tt
abs/1803 08367v1
Zelda Mariet and Suvrit Sra. Diversity networks: neural network compression using determinantal point processes. arXiv preprint arXiv:1511.05077 2015.
wtaeiii.rrg/baa /ab//
1511. 05077
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning. arXiv e-prints, art. arXiv:1412.6614, December 2014. httpht wwwpe/iiii.oggaab/////aaa/ 1412. 6614v4
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. arXiv preprint arXtv:1910001635, 2019. URL
01635. pdf
Saharon Rosset, Grzegorz Swirszez, Nathan Srebro, and Zhu. l regularization in infinite di-
mensional feature spaces. In Nader H. Bshouty and Claudio Gentile (eds.), Learning Theory, pp.
544-558, Berlin, Hcidelberg, 2007. Springer Berlin Hcidelberg. ISBN 978- 3-777----4--7 URL htttps://iimt www.inrrrnnrr.r....r nger com hwt.:////aaateee/..cmmm
Victor Sanh, Thomas Wolf, and Alexander M Rush. Movement pruming: Adaptive sparsity by fine- tuning. arXiv preprint 2rXiv:2055.06683 2020. URL
768.
10

---

Under review as a conference paper at ICLR 2021
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? arXiv preprint 1rXiv:1902.05040,, 2019. URL https:
//arxiv. org abs 190..99222.. 05040
Suraj Srinivas and R Venkatesh Babu. Data-free parameter pruning for deep neural networks. arXiv preprint arXiv:1507.061453 2015.
wwwpa/s/.org.oooooo.ooooo..o..sa 06149
Hidenori Tanaka, Daniel Kunin, Daniel LK Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. arXiv preprint arXiv:2006.05403 2020.
URL stttps://arxiv.orr////////
05467)
Francis Williams, Matthew Trager, Daniele Panozzo, Claudio Silva, Denis Zorin, and Joan Bruna.
Gradient dynamics of shallow univariate relu networks. In Advances in Neural Information Pro- cessing Systems, pp. 8378 8387, 2019. URL http:: nips wttppeppppppppeteeeeeeeeeeeeeeee 6046-
gradient - -atnddddnaaciie cs of challow uni wanivariateeae relu wew.-
A STEP-BY-STEP EXAMPLE OF HOW TO APPLY THE REDUCTION ALGORITHM
Starting with a three-stack architecture (like in the previous example and illustrated in fig. 5). we put d, 16 neurons every bottleneck. We then proceeded train this network: first without regularization and then with regularization for longer time.
Here we applied the Reduction Algorithm twice. We reduced the trained neural network first time, then trained the reduced model again which allowed us to reduce that model even further:
Removing and Replacing the Outside Neurons Instead of checking all 60000 training data points, we only checked 65 data points during the first reduction and 30 during the sec- ond reduction to time.
Removing the weakest neurons
We used different tolerances for every stack. For the experiment model we chose tolerances of 30, 20, and 10 for stacks 1, 2, and 3 respectively for the first reduction, and tolerances 10, 2, and 17 for the second reduction. The goal in this step (and the next) was to vary the hyperparameter such that we would not lose too much accuracy while removing many neurons possible.
Clustering Further reduction of the number of neurons as discussed before. See table 2 for an illustration of how to typically apply the Reduction Algorithm on given network.
Steps
n1
12.
11/
Train accuracy
Test accuracy
Full (wide) network
1024
1024
1024
0.9945
0.9799
Replacing outside neurons
72
925
932
0.9945
0.9799
Removing weak neurons
67
98
37
0.9940
0.9800
Clustering
67
84
15
0.9936
0.9803
After retraining
67
84
15
0.9960
0.9799
Replacing outside neurons
55
81
15
0.9959
0.9800
Removing weak neurons
55
75
8
0.9949
0.9809
Clustering
54
73
0.9941
0.9802
Table Number of neurons for each stack and accuracy at every step of the Reduction Algorithm applied on the large neural network first and on the retrained reduced network second
11


Reviews:
[{"review_id": "nFLnVR93Bld", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe authors leverage a functional regularization reformulation of neural network training problems to prune networks via a reduction algorithm. They present limited experimental evidence showing that the reduction algorithm reduces the number of neurons without sacrificing too much accuracy. \n\n\nMajor comments/questions\n\n1. Clarity and correctness\nThere are significant issues in the presentation and clarity. The authors use footnotes to explain important concepts, but many definitions are missing. The material in the footnotes can be included in the main text with a more natural flow. The main observation in Section 4.1 is not presented as a rigorous result, which appears to be the most interesting result. Remark 4.1 can also be presented as a theorem.\n\n2. Insufficient comparisons with the baselines.\n There is extensive literature in pruning and sparsification of network layers. In Table 1 and Table 2 there is no comparison with standard baselines in pruning. Does the proposed method perform better than standard pruning based on  weight magnitude/gradient norm/Hessian based metrics? \n\n3. Figure 6 is not very informative. It would be better to zoom in the relevant portion of the plot. Focusing on a few examples instead of seven different examples would make a better display.\n\n4. It is not clear why the authors consider the bottleneck architecture in Figure 4 and 5. Is the bottleneck required for the theory behind pruning or reducing overfitting?\n\n5. Section 3 starts with 'the authors have shown in an unpublished paper\". Is this referring to Maennel et al, 2018? Similar results also appeared in other papers (e.g. Savarese et al. 2019. Please provide a reference or proof for the equivalence of (1) and (2). The proof is in fact straightforward, we only need n_j>=d+1 to hold for Caratheodory's theorem. The authors can be more precise for the required width n_j. This is a significant omission.\n\n6. On page 3, footnote 1, P(f) is not properly defined and it's not clear what P(f)=\\infty means. This can be clarified by providing necessary references noted above.\nFurthermore in eq (1), NN_\\theta is not properly defined. Is this a standard relu network?  \n\n7. In the introduction, the authors claim that the proposed method preserves the network output exactly as opposed to other pruning methods. However, in Section 4.2 and 4.3, the authors also resort to approximation methods involving magnitude based pruning and clustering, which are standard in the literature. The observation from Section 4.1 is also not exactly applied and yields an approximate neural network.\n\n8. What would be the computational complexity of looping through every neuron and the proposed approximation? Is there a way to justify this approximation?\n\nMinor comments\n1. The manuscript needs a careful proofreading since it contains lots of typos and grammatical errors.\npage 1. It's architecture -> Its architecture.\npage 1. authros -> authors\n\n2. There some definitions which need further explanation\npage 1. I believe what is meant by a 'large layer' is a wide layer.\npage 1. Could you please clarify what sparsity refers to in \"reduce the number of neurons by 90% to 99% without introducing sparsity\"? \npage 3. bottleneacks->bottlenecks", "extra_scores": {}, "extra_text": {}}, {"review_id": "jcmv8fjSYTQ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper suggests a pruning technique specific to ReLU networks by taking advantage of activation patterns and the separating hyperplanes. The technique consists of three steps: : (1) remove neurons that are never active and combine neurons that are always active, (2) remove neurons with little contribution to the output, and (3) use weighted k-means to combine other neurons. The method is evaluated on specific toy problems and the MNIST dataset.\n\nThe paper proposes a novel technique to reduce neurons in a ReLU network. The method to combine neurons takes the hyperplane arrangements (where activations of neurons change) into account and leads to much smaller networks with equal performance in the experiments.\n\nThe three major problems of the paper are that it lacks motivation of the proposed technique, it contains an insufficient experimental evaluation and important parts of the paper cannot be reviewed either due to a reference to unspecified, unpublished work or a lack of a derivation.\n\nSince the correctness of the paper cannot be evaluated and the technique is insufficiently validated, I recommend to reject. \n\n\nDetails on weaknesses:\n- The correctness of the proposed technique cannot be reviewed. \n(a) Section 3 cannot be confirmed as it refers to results from unspecified unpublished work, i.e., it is impossible to find and read through the unpublished work to estimate its validity. Moreover it is unclear why these results are important for the given paper and how the results are used. The paper states that one should only learn from this entire section that a finite(!) number of neurons is sufficient (which we always have in a practical setting so the conclusion is void?) In any way, either this section is not necessary for the rest of the paper and should be removed, or it is necessary in which case it cannot be verified.\n(b) The proposed pruning technique consists of three steps (see above in the summary) two of which are trivial: (1)&(2). The third step (3) uses weighted k-means to combine other neurons. There is no explanation, motivation or derivation of the equations how the clusters are combined. (The workings of the method are also surprising, because a cluster containing a single neuron is reduced to a new single neuron in such a way that the function changes, which is counter-intuitive. It seems therefore likely that the equations contain typos, also since they introduce square roots of square roots and it is not defined what is meant by squaring a vector in the function g.)\nTherefore, the validity cannot be confirmed and the reader must trust the experimental result section. This is unfortunate as there are opportunities to shorten less relevant parts in favor of a derivaiton of the equations.\n\n- The experiments are not sufficient. The experiments only consider specific toy problems and the MNIST dataset, which is too simple to showcase the pruning technique. The method is neither compared to any other pruning technique and it is fairly simple to prune networks on MNIST with a similar loss of accuracy. Finally, the method introduces two hyperparameters which are not tested. To validate the performance, both a more complex dataset and the comparison to other pruning techniques are necessary.\n\n- The presentation needs improvement. For example, there is a rather long explanation of a seemingly simple architecture and still details are left unclear (Is there a linear layer with weights that are trained, or is the linear skip connection only introduced when pruning the network?) It would be helpful to add an equation for the stack layer and reduce the explanations. The possibly redundant Section 3 could be removed. Instead, the proposed method could be derived and explained. The experiments could be explained in more detail (Why do the plots show the smoothened second derivative?)\n\n\n\n\nTypos:\nLine 4 Motivation „authros“\nPage 3, footnote, „bottleneacks has diomension“\nPage 4 toward the end of Section 3: „the the“\nPage 5: the first sentence is not a sentence", "extra_scores": {}, "extra_text": {}}, {"review_id": "Sv_CdJ-pRHz", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \n- In this paper, the authors propose a novel algorithm for pruning fully-trained ReLU neural networks. To motivate the algorithm, the authors first introduce a new network architecture with an affine skip-connection at each layer. Then the authors connect it to the theory developed in an `unpublished work`. They show that for such neural networks, the number of units in the original layer can be greatly reduced. The main idea of the proposed algorithm is basically to prune those neurons whose removal will not change the function a lot. To quantify this, the authors turn to the L2 norm of each neuron. Experiments on simple toy data and MNIST are conducted.\n\n\nOverall, I believe this paper is not ready for publication. So, I vote for rejection. \n- This paper massively refers to the unpublished work by the author, while the authors only provide only little details about the developed theory in the unpublished work. If this is a concurrent submission to ICLR, the author should still cite it anonymously.\n- To me, the proposed deep stack network is very similar to the formulation of the highway network in Srivastava et al., (2015).\n- The experiments are not convincing enough. The authors only conduct experiments on a simple toy dataset and MNIST. The numbers are fairly close to each other. To show the statistical significance, some measures, such as one standard error should be provided. I would encourage the authors to at least conduct some experiments on CIFAR datasets.\n\nTypos:\n- Exactly speaking, the learned function will not be the same same as before ->Exactly speaking, the learned function will not be the same  as before \n- Therefore the the function optimizing eq. (2) can be represented by finite number -> Therefore the function optimizing eq. (2) can be represented by a finite number\n\n\nSrivastava, Rupesh Kumar, Klaus Greff, and Jürgen Schmidhuber. \"Highway networks.\" arXiv preprint arXiv:1505.00387 (2015).", "extra_scores": {}, "extra_text": {}}, {"review_id": "GvVHhZXZkx2", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 2, "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": "The paper focuses on defining a new architecture that allows being reduced without significantly affecting the performance. \n\nIn short, the paper is not properly written nor well organized; is hard to read with vague contributions and vague positioning with respect to the state of the art. Experiments are not convincing: Toy experiment and minimum experiments in MNIST without a clear comparison to existing neuron pruning algorithms.  ", "extra_scores": {}, "extra_text": {}}, {"review_id": "3bjb6sh6Isp", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 2, "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": "The paper describes a way to reduce the dimensionality of a deep ReLU network. In general, the paper is not well written and hard to follow. They keep referencing \"unpublished work of the authros\" although its use in practice is not very clear.\n\nPractically, they prune a deep network by (a) removing dead ReLU neurons; (b) combine neurons for which the ReLU always acts as the identity. None of these two ideas is particularly novel, especially considering the huge amount of literature to be found on network pruning. Experiments are only done on an artificial dataset and on MNIST.\n\nMany parts of the paper are poorly described. For example, their \"stack network\" is simply a residual network with affine projections on the residual link. A \"P-FUNCTIONAL\" is not defined. The link between Eq. (4) and their algorithm is not clear.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a clear reject. None of the reviewers supports publication of this work. The concerns of the reviewers are largely valid.
Decision: Reject