Scaling Up Exact Neural Network Compression by ReLU Stability
Authors: Thiago Serra
Xin Yu
Abhinav Kumar
Srikumar Ramalingam
Venue: NeurIPS 2021 Poster (2021)
Keywords: Scaling
Neural Networks
Lossless Compression
ReLU

Abstract: We can compress a rectifier network while exactly preserving its underlying functionality with respect to a given input domain if some of its neurons are stable. However, current approaches to determine the stability of neurons with Rectified Linear Unit (ReLU) activations require solving or finding a good approximation to multiple discrete optimization problems. In this work, we introduce an algorithm based on solving a single optimization problem to identify all stable neurons. Our approach is on median 183 times faster than the state-of-art method on CIFAR-10, which allows us to explore exact compression on deeper (5 x 100) and wider (2 x 800) networks within minutes. For classifiers trained under an amount of L1 regularization that does not worsen accuracy, we can remove up to 56% of the connections on the CIFAR-10 dataset. The code is available at the following link, https://github.com/yuxwind/ExactCompression .

Scaling Up Exact Neural Network Compression by ReLU Stability
Thiago Serra Bucknell University
Xin Yu
University of Utah
Lewisburg, PA, United States thiago. serra@bucknell. edu
Salt Lake City, UT, United States xin. yunutah. edu
Abhinav Kumar
Srikumar Ramalingam
Michigan State University East Lansing, MI, United States kumarab6@msu.co edu
Google Research
New York, NY, United States rsrikumarOgoogle.o com
Abstract
We can compress a rectifier network while exactly preserving its underlying func- tionality with respect to given input domain if some of its neurons are stable. However, current approaches to determine the stability of neurons with Rectified Linear Unit (RcLU) activations require solving or finding good approximation to multiple discrete optimization problems. In this work, we introduce an algorithm based on solving a single optimization problem to identify all stable neurons. Our approach on median 183 times faster than the state-of-art method on CIFAR- 10, which allows us to explore exact compression
deeper (5 x 100) and wider (2 800) networks within minutes. For classifiers trained under an amount of regularization that does not worsen accuracy, we can remove up to 56% of the connections on CIFAR- 10 dataset. The code is available at the following link, htttp://githun http:////iddd//////CCCoeeeeee ExactCompression.
Introduction
For the past decade, the computing requirements associated with state-of-ar art machine learning models have grown faster than typical hardware improvements [5]. Although those requirements are often associated with training neural networks, they also translate into larger models, which are challenging to deploy modest computational environments, such as in mobile devices.
Meanwhile, we have learned that the expressiveness of the models associated with neural networks when measured in terms of their number of linear regions grows polynomially on the number of neurons and occasionally exponentially on the network depth [69, 65, 73, 81, 36, 37J. Hence, we may wonder if the pressing need for larger models could not be countered by such gains in model complexity. Namely, if we could not represent the same model using a smaller neural network. More specifically, we consider the following definition of equivalence [49, 79]:
Definition 1. Two neural networks Ni and N₂ with associated functions fi Ro0 + Rd and f2 : R0 - Rmm are local equivalent with respect to a domain C I if fi()) f2(x) Vo D.
There is an extensive literature on methods for compressing neural networks [18, 11], which is aimed obtaining smaller networks that are nearly as good as the original ones. These methods generally produce networks that are not equivalent, and thus require retraining the neural network for better accuracy. They may also lead models in which the relative accuracy for some classes more affected than that of other classes [43].
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Compressing a neural network while preserving its associated function is a relatively less explored topic. which has been commonly referred to as lossless compression [79, 83]. However, that term has also been used for the more general case in which the overall accuracy of the compressed network is no worse than that of the original network regardless of equivalence [95]. Hence, we regard exact compression as more appropriate term when equivalence is preserved.
Exact compression has distinct benefits and challenges. On the one hand, there is no need for retraining and no risk of disproportionately affecting some classes more than others. On the other hand, optimization problems that are formulated for exact compression need to account for any valid input as opposed to relying on sample of inputs. In this paper, we focus on how to scale such an approach to a point in which exact compression starts become practical for certain applications.
In particular, we introduce and evaluate a faster algorithm for exact compression based on identifying all neurons with Rectified Linear Unit (Rel.U) activation that have linear behavior, which are denoted as stable. In other words, those are the neurons for which the mapping of inputs to outputs is always characterized by linear function, which is either the constant value 0 or the preactivation output. We can remove or merge such neurons-and even entire layers in some cases- while obtaining a smaller but equivalent neural network. Our main contributions are the following:
We propose the algorithm ISA (Identifying Stable Activations), which is based on solving single Mixed-Intege Linear Programming (MILP) formulation to verify the stability of all neurons of feedforward neural network with ReLU activations. ISA is faster than solving MILP formulations for every neuron either optimally [90] or approximately [79]. Compared to [79], the median improvement of 83 times on MNIST dataset (183 times on CIFAR-10 dataset and 137 times on CIFAR- 100 dataset) -ndd in fact greater in larger networks.
(ii) We reduce the runtime with a GPU-based preprocessing step that identifies neurons that are not stable with respect to the training set. The median improvement for that part alone is of 3.2 times on MNIST dataset.
(iii) We outline and prove the correctness of a new compression algorithm, LEO++ (Lossless Expres- siveness Optimization, as in [79]), which leverages (i) to perform all compressions once per layer instead of once per stable neuron [79].
(iv) We leverage the scalability of our approach to investigate exact compressibility on classifiers that are deeper (5 100) and wider (2 x 800) than previously studied in [79] (2 x 100). We show that approximately 20% of the neurons and 40% of the connections can be removed from MNIST classifiers trained with an amount of e, regularization that does not worsen accuracy.
2
Related work
There many pruning methods for sparsifying or reducing the size of neural networks by removing connections, neurons, or even layers. They are justified by the significant redundancy among parameters [23] and the better generalization bounds of compressed networks [8, 98, 87, 88].
Surveys such as [11] note that these methods are typically based on a tradeoff between model efficiency and quality: the models of compressed neural networks tend to have comparatively lower accuracy, save some exceptions [35, 95, 87]. Nevertheless, the loss in accuracy due to compression is disproportionately distributed across classes and more severe in a fraction of them; the most impacted inputs are those that the original network could not classify well; and the overall robustness to noise or adversarial examples is diminished [43]. Furthermore, the amount of compression yielding similar performance to the original network can vary significantly depending on the task [59].
To make up for model changes and potential accuracy loss, one may rely on three-step procedure consisting of (I) training the neural network; (2) compression; and (3) retraining. Nevertheless, the scope of compression methods is seldom restricted to the second step. For example, the compressibil- ity of a neural network hinges on how it was trained, with regularizations such as & and & often used to make part of the network parameters negligible in magnitude- and hopefully in impact well.
In fact, the two main-and recurring-thent corresponding parameters are sufficiently small [38, 66, 47, 35, 34, 57, 29, 31, 89] and when the impact of the connection on the loss function is sufficiently small [54, 39, 52, 64, 25, 96, 97, 56, 91, 92, 82]. The main issue with the first approach is that small weights may nevertheless be important,
in this topic are pruning connections when the
2

---

although it is possible to empirically quantify their impact on the loss function [76]. The main issue with the second approach is the computational cost of calculating the second-order derivatives of the loss function in deep networks, which has lead to many approaches for approximating such values.
Overlapping with such approximations, there is growing literature on casting neural network compression as an optimization problem [41, 62, 1, 96, 79, 26J. Most often, these formulations aim to minimize the impact of the compression on how the neural network performs on the training set.
Other lines of work and overlapping themes in neural network compression include combining similar neurons [84, 63, 86, 87]; low-rank approximation, factorization, and random projection of the weight matrices [46, 24, 51, 8, 93, 85, 91, 87, 88, 58]; and statistical tests on the relevance of a connection to network output [95]. Many recent approaches focus pruning at initialization instead of after training [56, 55, 92, 89, 30] as well as on what parameters to use when these networks are retrained [29, 61, 74].
Exact compression was only recently explored for fully-connected feedforward neural networks [79] and graph neural networks [83]. Nevertheless, we may associate it with the literature neural network equivalency, which includes verifying that networks are equivalent [67, 15]. identifying operations that produce equivalent networks [42, 16, 50, 49, 72], reconstructing networks from their outputs [3, 4, 27, 2, 75], and evaluating the effect of redundant representations on training [10, 71].
3 Setting and notation
We consider fully-connected feedforward neural networks with L hidden layers, in which we denote my as the number of units or width of layer E L := {1, .,........ L} and at as the output of the i-th unit of layer / for E (1,2...., nu... For uniformity, we denote xt E 1." as the network input. We denote the output of the i-th unit of layer / as o = (3))), where the pre-activation output of == w -' + bद is defined by the learned weights w E "K- and the bias 6/ E IR of the unit as well as the activation function o' + R associated with layer I, which is of (u) = max f0, u] the ReLU [33]. The output layer may have a different structure, such as the softmax layer [13], which is nevertheless irrelevant for our purpose of compressing the hidden layers. For every layer I E L. let W' [0) w² ... w I be the matrix of weights, W be a submatrix of W consisting of the rows in set S, and b' = [ by ... 1², be the vector of biases. Finally, let I, (S) be m m diagonal matrix in which the i-th diagonal element is if E S and 0 if i i S.
4 Identifying stability for exact compression
This section explains the concept of stability and describes how MILP has been used identify stable neurons. If the output of neuron in layer / is always linear on its inputs, we say that the neuron is stable. This happens in two ways for the ReLU activation. When x! 0 for any valid input, which implies that yf < O, we say that the neuron is stably inactive. When o! y for any valid input, which implies that of 2 0, we say that the neuron is stably active.
The qualifier valid is essential since not every input may occur in practice. If w + O, there are nonempty halfspaces on x'-1 that would make that neuron active or inactive, {a'-1 : w/-
+b < 0} and (2-- w/ _/'1 + bf 2 0}. but it is possible that valid inputs only map to one of them. For the first layer, we only need to account for the valid inputs to the neural network. For example, the domain of a network trained on the MNIST dataset is (x x E [0, 784 3 [53]. For the remaining hidden layers, we also account for the combinations of outputs that can be produced by the preceding layers given their valid inputs and parameters. Hence, assessing stability is no longer straightforward.
We can determine if a neuron of a trained neural network is stable by solving optimization problems to maximize and minimize its preactivation output [90]. The main decision variables in these problems are the inputs for which the preactivation output is optimized. Consequently, there is also a decision variable associated with the output of every neuron, in addition to other variables described below.
MILP formulation of a single neuron For every neuron of layer 1, we map every input vector a to the corresponding output x/ through set of línear constraints that also include binary variable of denoting if the unit is active or not, variable for the pre- are-activttion output v/. variable x ;= max{0, - y/} denoting the output of complementary fictitious unit, and positive constants
3

---

Mf and μ4 that are as large as z and x can be. The formulation below is explained in Appendix Al.
wi x'-1 + by v/ = x1
(1)
0 S o S M
(2)
s x $ 14(1 z/)
(3)
2 E {0,
(4)
Using MILP to determine stability Let X C IR be the set of valid inputs for the neural network,
which we may assume be bounded in every direction. We obtain the interval D2 , for the preactivation output uf of neuron i in layer I' by solving the following optimization problems [90]:
Ld = min w x." =1"- by x. E
E::01 (1) - (4) 44 E [1' - -1,, [m]}
(5)
F/ = max wtt -1 + by.
x x: (1) (4) VI 11, [m]]]
(6)
When Jd < 0, then x!" = 0 for every x² E X and the neuron is stably inactive. When yd 2 0. then x! = for every x0 X and the neuron stably active.
Variations of the formulations above have been proposed for diverse tasks over neural networks, such verifying them [17], embedding their model into broader decision-making problem [78, 9, 21], and measuring their expressiveness [81]. When stable units are identified, other optimization problems over trained neural networks become easier to solve [90]. For example, weight regularization can induce neuron stability and facilitate adversarial robustness verification [94]. There is extensive work on the properties of such formulations and methods solve them more effectively [28, 7, 12, 80, 6).
For the purpose of identifying stable neurons, however, it is not scalable to analyze large neural networks by solving such optimization problems for every neuron [90]-or even by just approximately
solving each of them to ensure that y. S 0 or y 2 0 [79].
5 A new algorithm for exact compression
Based on observations discussed in what follows (I to III), we propose a new MILP formulation to identify stable neurons (Section 5.1), means to generate feasible solutions while the formulation is solve (Section 5.2), a preprocessing step to reduce the effort to solve the formulation (Section 5.3), the resulting algorithm ISA for identifying all stable neurons once (Section 5.4), and the revised compression algorithm LED++ exploiting all stable neurons in each layer at once (Appendix A5).
5.1 A new MILP formulation
Consider the two observations below and their implications:
The overlap between optimization problems Although previous approaches require solving many optimization problems, their formulations are all very similar: we maximize or minimize the same objective function for each neuron, the feasible set of the problems for each layer are the same, and they are contained in the feasible set of problems for the subsequent layers.
II: Proving stability is harder than disproving it Certifying that neuron is stable is considerably more complex than certifying that a neuron not stable. For the former, we need to exhaustively show that all inputs lead to the neuron always being active or always being inactive, which can be achieved by solving (5) and (6) for every neuron. For the latter, we just need a pair of inputs to the neural network such that the neuron active with one of them and inactive with the other.
Therefore, we consider the problem of finding an input that serves as a certificate of a neuron not being stable to many neurons of unknown classification possible. For that purpose, we define a decision variable p E {0. 1} to denote if an input activates neuron in layer i. Likewise, we define a decision variable gf E (0,1) to denote if an input does not activate neuron in layer I. Furthermore, restrict the scope of the problem to state that have not been previously observed

---

by using P S [I. activates the neuron. Likewise, we use Q' C (1..... nt) as the set of neurons in layer' for which there is no known input that does not activate the neuron. For brevity, let P := (IP) [IP'...., PP)) and
n as the set of neurons in layer / for which there is no known input that
Q == QT) characterize an instance of such optimization problem, which is formulated as
follows:
C ((PQ) Q) max
Σ EEL
Σ PEP
p
Σ
(7)
iEQ!
s.t.
x X
(8)
(1) - (4) E [n]]
(9)
0 /
(10)
0 5 Φ S 1- WELIEE
(11)
P.. E {0.
(12)
Note that constraint (12) is actually not necessary. We refer to Appendix A2 for more details.
The formulation above yields an input that maximizes the number of neurons with an activation state that has not been previously observed. The following results show that it entails an approach in which no more than .N + 1 such formulations are solved. We refer to Appendix A3 for the proofs.
Proposition 1. IfC(P,Q) stably active.
0. then every neuron i E IP' is stably inactive and every neuron E Q'
Corollary 2. The stability of all neurons of a neural network can be determined by solving formula- tion (7) at most N + times, where N Σ nt.
Those results imply that we can iteratively solve the new formulation as part of an algorithm to identify all stable neurons. In fact, we can determine the stability of the entire neural network with a single call to the MILP solver. Except for the last time that formulation (7)-(1) is solved, there no need solve to optimality: any solution with a positive objective function value can be used to reduce the number of unobserved states. Hence, all that we need is a way to inspect every feasible solution obtained by the MILP solver and then remove the solutions in which either /f = or of for states that were already observed. Both of those needs can be addressed in fully-fledged MILP solvers by implementing a lazy constraint callback. We refer to Appendix A4 for more details. When we finally reach C C(P, Q) 0, the correctness of the MILP solver serves as a certificate of the stability of those remaining neurons. The resulting algorithm is described in Section 5,4.
5.2 Inducing feasible MILP solutions
The runtime with a single solver call depends the frequency with which feasible solutions obtained. Although at most N + optimal solutions would suffice if we were to make consecutive calls to the solver until C(P, Q) O, we should not expect the same from the first N + feasible solutions found by the MILP solver while using the lazy constraint callback because they may not have a positive objective function value due to the p and gf variables that have been fixed to Ó. On top of that, obtaining a feasible solution for an MILP formulation is NP-complete [19].
II Finding feasible solutions to MILP formulations of neural networks is easy To any valid input of the neural network there a corresponding solution of the MILP formulation: the neural network input implies which neurons are active and what is their output when active [28].
Although any random input would suffice, we have found that it is better in practice to use inputs indirectly generated by the MILP solver. Namely, we can use the solution of the Linear Program- ming (LP) relaxation, which is solved least once per branch-and-bouu is obtained from the MILP formulation by relaxing its integrality constraints. In the case of binary variables with domain (0, 1}, that consists of relaxing the domain of such variables to the continuous interval [0. 1]. We use the values of x in the solution of the LP relaxation as the network input, and thus obtain feasible MILP solution by replacing the values of the other dariables-whih may be fractional for the decision variables with binary domains-by the values implied by fixing z However imprecise due to the relaxation of the binary domains, the input defined by the optimal solution of the LP relaxation may intuitively guide us toward maximizing the objective function.
node. The LP relaxation
5

---

5.3 Preprocessing
In addition to generating feasible MILP solutions at every node the branch-and-bow boundd tree during the solving process, also evaluate the training number of states that need to be search for by the MILP solver. By using GPUs, this step can be completed in few seconds for all the experiments performed.
the trained neural network to reduce the
5.4 Identifying stable neurons
Algorithm 1, which we denote ISA (Identifying Stable Activations), identifies all stable neurons of neural network. The prior discussion on identifying stable units leads to the steps described between lines 3 and 28. First, P and are initialized between lines 3 and 6 according the preprocessing step deseribed above. Next, the MILP formulation is iteratively solved between lines 7 and 28. The block between lines 8 and 9 identifies the termination criterion, which implies that the unobserved states cannot be obtained with any valid input. The block between lines 10 and 24 inspects every feasible solution identify unobserved states and then effectively remove the decision variables associated with those states from the objective function by adding a constraint that sets their value to O. The block between lines 25 and 26 produces feasible solution from solution of the LP relaxation when the latter is produced by the MILP solver. For brevity, we assume that the block between lines 10 and 24 would leverage such solution at the next repetition of the loop.
Algorithm ISA provably identifies all stable neurons of a neural network by iterating over the solution of single MILP formulation verify the occurrence of states unobserved the training set
1: Input: neural network
(I, (m,, W het.
2: Output: stable neurons (((P).
3: for + to L do
D Pre Pre-processing step
4: Ip' +- subset of {1, (1...., n4 that is never activated by the training set
5: Q! subset of {I,..... n that is always activated by the training set
6: end for
7:
while solving C(P, Q) do
>> Loop interacting with MILP solver Remaining neurons are all stable
8: if optimal value is proven to be then break
9:
> Nothing else to be done b Identified unobserved states > Loops all hidden layers b. Loops over neurons that have not been seen active yet Neuron is active for the first time
10: else found positive MILP solution
2. then
11: for 1 <- 1 to do
12:
for every i E Ip do
13:
if p 0 then
14:
P P \t)
Neuron is not stably inactive
15:
P/ < 0
Restricts MILP to avoid identifying neuron again
end if
17:
end for for every i
18:
@ do
> Loops over neurons that have not been seen inactive yet Neuron is inactive for the first time > Neuron is not stably active Restricts MILP to avoid identifying neuron again
19:
if प then
20:
0
+ 0 {2}
21:
4-0 0
end if
end for end for 25: else if found LP relaxation solution (G. E. then Input à may produce unseen states
23:
use o to produce an solution (z. Σ, P. Q) & Produce unseen activations for input 27: end if
28:
end while
return (((P), (()))
29:

---

6 Experimental results
We trained and evaluated the compressibility of classifiers for the datasets MNIST [53], CIFAR- 10 [48], and CIFAR- 100 [48] with and without E weight regularization, which is known to induce stability [90]. We refer to Appendix A6 for details on environment and implementation. We use the notation L X ri for the architecture of L hidden layers with n neurons each. We started at L 2 and n = 100, and then doubled the width n or incremented the depth L until the majority of the runs for MNIST classifiers for any configuration timed out after 3 hours. With preliminary runs, we chose values for l which spanned from those for which accuracy is improving as & increases until those for which the accuracy starts decreasing. We trained and evaluated neural networks with 5 different random initialization seeds for each choice of 4 The amount of regularization used did not stabilize the entire layer. We refer to Appendix A7 for additional figures and tables with complete results.
Regularization and compression Fig. illustrates the average accuracy and number nodes that can be removed from networks according to architecture and dataset based on the amount of regularization used. When used in moderate amounts, regularization improves accuracy and very often that also coincides with enabling exact compression. We observe regularization improving accuracy in 17 of the 21 plots in Fig. 1. In 14 cases, we reduce the size of these more accurate networks. Those include all architectures for MNIST (a to g), the architecture with width 400 for CIFAR-100 (r), and all the architectures with more hidden layers for CIFAR-10 10 and CIFAR- (j. I, n, q, S, u).
Runtime improvement Fig. compares the baseline [79] with our approach smaller MNIST classifiers- 2 x 100, 2 x 200, and 2 x 400 400-using & as described above. The median ratio between runtimes is 100. The overall speedup is greater in larger networks: the median runtime ratio is 77 for 2 x 100, 153 for 2 x 200, and 193 for 2 x 400. By comparing the runtimes when not timing out with and without the preprocessing step in 2 X 100, we observe median speed up of 3.2.
Effect of regularization on compressibility We observe more compression with more & regular- ization. For sufficiently large networks having the same accuracy those trained with L 0 on MNIST, we can remove around 20% of the neurons and 40% of the connections. In line with [79], we observe that the exact compressibility of neural networks trained with & = 0 is negligible, but also that you can have the cake and eat it too: certain choices of regularization lead to better accuracy and smaller network. towever,the cake can get very expensive runtimes increase considerably.
Relationship between compressibility and accuracy Fig. 3 analyzes the relationship between classifier accuracy and the number of neurons left after compression for 2 x 100 classifiers. When excluding uncompressible networks with & = or sufficiently small, we obtain linear regressions with coefficient of determination (R2) of 69% on MNIST, 91 % on CIFAR- 10, and 61 % on CIFAR- 100. That suggests that accuracy is a good proxy for how much a neural network can be compressed.
Motivation for exact compression We also compared exact compression with Magnitude- based Pruning (MP), one of the most commonly used inexact methods. First, we identified all the connec- tions that would be pruned by the removal of stably inactive neurons with our approach, which would also be harmless if identified and removed by MP. Second, we ranked all the connections based on the absolute value of their coefficients in order to identify at what pruning ratio those connections would have been removed by MP. We consistently found out across architectures of different sizes and levels of regularization that some of the pruned connections by our method would be found by MP at the 99th percentile. In other words, even though such connections would have no impact if removed from the network, MP would only resort to removing them at very extreme levels of pruning. Furthermore, the same pruning ratio is used with MP, on average 10% of the total number of connections or 18% of the pruned connections-rement
by our method would not be removed by MP.
6.1 Limitations and alternatives
Due to the use of MILP solvers, our approach is not applicable to very large networks. In what follows, we consider ways to extend our approach by lifting some or all the guarantees provided.
Inexact approach to larger networks We evaluated the impact of using only the quick preprocess- ing step described Section 5.3 to determine which neurons to remove. Note that the preprocessing step is in principle intended to identify neurons that are not stable in order to avoid spending further time on them, but we can conversely assume that all the other neurons are stable at the cost of removing more than we should. By using preprocessing alone, we identified on average 31.93%
7

---

Test accuracy (%)
60
98.2
Nodes removed
98
97.8
30
97.6
(b) 200 MNIST
(d) 400 MNIST
(1) x MNIST
97.4
97.2
2
1
-10
(a) x 100 @ MNIST
(c) 100 MNIST
(e) 100 MKIST
(g) 5 100 MNIST
Test accuracy (%)
60
Nodes removed (%)
50
30
(
(m)
45
40
0
0
1
2
3
4
L
-10-1
(h) 2 x 100 @ CIFAR-10
(i) 3 100 @ CIFAR-10
(1) 100 CIFAR-10
(n) 100 @ CIFAR-I0
Test accuracy (%)
60
Nodes removed (%)
30
25
(p)
(r)
(0)
20
2
-10-1
(o) 2 x 100 @ CIFAR-100
3g)3x x 100 CIFAR-100 (s) 4 x 100 @ CIFAR-100 (u) 100 @ CIFAR-100
Figure 1: Test accuracy and nodes removed for varying amounts of & regularization. The plots correspond to classifiers with different architectures on the (a)-(g) MNIST, (h)-(n) CIFAR-10, and (o)-(u) CIFAR- 100 datasets. For each dataset, we keep the ranges all the axes of the smaller plots same as the bigger plot but hide the ticks for brevity. Networks trained with { regularization can be exactly compressed, even when regularization improves accuracy. In light red background, test accuracy is better than with no regularization (blue curve) and exact compression occurs (red curve).
potentially stable neurons MNIST classifiers, 40.86% in CIFAR-10 classifiers, 41.98% in CIFAR- 100 classifiers. Among those neurons, only a few were actually not stable when evaluated with the test set. In terms of the number of not stable neurons with respect to the test set divided by the number of stable neurons with respect to the training set, would have removed 1.16% more neurons that we should for MNIST, 0.60% for CIFAR- 10, and 1.19% for CIFAR-100. We refer to Appendix A7.5 for experiments involving convolutional neural networks (CNNs).
Restricting exact compression to more likely inputs We also tested the effect of bounding the sum of all the MNIST inputs to be within the minimum and maximum observed values. In particular, we have constrained the sum of all inputs to be within the interval [15, 320] instead of [0, 784). We believed that this approach would be preferable to constraining the value of individual inputs, since that would have affected the output upon rotation and translation. Note that this constraint equivalent to imposing prior the number of foreground pixels the digits to be within range.

---

#2x @ MINSTT
x MNIIT
Proposed Runtime (8)
10
200 MIISTT
10
2 200 MINIST
1.5
Proposed Runtime
1.5
-2
10F
10P
11.5
0.5
10
10
10P
10
10a
10P
10
100
10
10a
10a
Baseline Runtime
Proposed w/o Preprocessing Runtime (s)
Figure 2: Comparison of runtimes (in seconds) to identify all stable neurons. On the left, we compare the proposed approach against the baseline from [79]. On the right, we compare the proposed approach with preprocessing against the proposed approach without preprocessing.
10
110
24
Accuracy (%)
Accuracy (%)
22
211
compression
compression
Compressible
Compressible
Compeessible
18
Compressible
140
180
100
170
160
196
200
120
140
160
180
200
Neurons left in MNIST classifiers
Neurons left in CIFAR 100 classifiers
Figure Relationship between size of compressed neural networks and accuracy on 100 classifiers. The coefficient of determination (R2) for the linear regression obtained for accuracy based on neurons left for compressible networks 69% on MNIST and 61 % on CIFAR-100.
Global priors that jointly on all the pixels have been used in computer vision in the pre-deep learning era, e.g., [22]. By restricting the analysis to the cases in which the time limit has not been exceeded either before or after the change, we obtained better runtime in 69.6% of the cases and the runtime geometric mean went down by 17.7%.
7 Conclusion
This paper outlined the potential for exact compression of neural networks and presented an approach that makes practical for sizes that are large enough for many applications. To the best of our knowledge, our approach is the state-of-the-as art for optimization-bet based exact compression. Our perfor- mance improvements come from insights about the MILP formulations associated with optimization problems over neural networks, which have many other applications besides exact compression. Most notably, such formulations are also used for network verification [14, 60, 77].
Large models are resource- resource-inensive for both training as well as inference. In contrast to approximate methods, our practitioners to save computational time and resources without worrying about any loss in perfor- mance. That helps preventing the documented side effect of disproportionally degrading performance for some classes more than for other classes when the indicator of a successful compression the overall performance, which could also lead to fairness issues [43, 68, 44].
Societal Impact
model compression algorithms can help deep learning
Acknowledgements Thiago Serra was supported by the National Science Foundation (NSF) grant IIS 2104583. Xin Yu and Srikumar Ramalingam were partially funded by the NSF grant IIS 1764071. Abhinav Kumar was partially funded by the Ford Motor Company and the Army Research Office (ARO) grant W91 INF- 18- 18-10300- We also thank the anonymous reviewers for their constructive feedback that helped in shaping the final manuscript.

---

References
A. Aghasi, A. Abdi. N. Nguyen, and J. Romberg. Net-Trim: Convex pruning of deep neural networks with performance guarantee. NewrIPS, 2017. 3
[2] A. Al-Falou and D. Trummer. Identifiability of recurrent neural networks. Econometric Theory, 2003. 3
[3] F. Albertini and E. Sontag. For neural networks, function determines form, Neural Nenworks, 1993. 3
F. Albertini and E. Sontag. Identifiability of discrete-time neural networks. In ECC, 1993. 3
[5] D. Amodei, D. Hernandez, G. Sastry, J. Clark. G. Brockman, and I. Sutskever. Al and compute. https: 2018. Accessed: 2020-12-23,
//openai... www/blog/eeeeeoocccooocooowooooo ai- and- compute/, 2018.
[6] R. Anderson, J. Huchette, W. Ma, C. Tjandraatmadja, and Vielma. Strong mixed mixed-integer programming formulations for trained neural networks. Mathematical Programming, 2020.
[7] R. Anderson, Huchette, Tjandraatmadja, and Vielma. Strong mixed- mixeedinteger programming formula- tions for trained neural networks. In IPCO, 2019. 4
[8] S. Arora, R. Ge, B. Neyshabur, and Zhang. Stronger generalization bounds for deep nets via a compression approach. In ICML, 2018. 2,
[9] D. Bergman, T. Huang, P. Brooks, A. Lodi, and A. Raghunathan. JANOS: An integrated predictive and prescriptive modeling framework. arXiv, 1911.09461, 2019. 4
[10] J. Berner, D. Elbrächter, and P. Grohs. How degenerate is the parametrization of neural networks with the relu activation function? In NeurlPS, 2019. 3
[11] D. Blalock, J. Ortiz, J. Frankle, and J. Guttag, What is the state of neural network pruning? In MI.Sys, 2020. 1,2
[12] E. Botoeva, P. Kouvaros, Kronqvist, A. Lomuscio, and R. Misener. Efficient verification of relu-based neural networks via dependency analysis. In AAAI, 2020. 4
[13] Bridle, Probabilistic interpretation feedforward classification network outputs, with relationships to statistical pattern recognition. Nearocomputing. 1990.
[14] R. Bunel, I. Turkaslan, P. Torr, P. Kohli, and M. Pawan Kumar. Piccewise linear neural network verification:
A comparative study. CoRR, ahs/11711.00455, 100455, 2017. 9
[15] M. Büning, P. Kern, and C. Sinz. Verifying equivalence properties of neural networks with relu activation functions. In CP, 2020. 3
[16] A. Chen, H. Lu, and R. Recht-Nielsen. On the geometry of feedforward neural network error surfaces. Neural Computation, 1993. 3
[17] C. Cheng, G. Nührenberg, and H. Ruess. Maximum resilience of artificial neural networks. In A7VA, 2017. 4, 18
[18] Y. Cheng, D. Wang, P. Zhou, and T. Zhang. Model compression and acceleration for deep neural networks:
The principles, progress, and challenges. IEEE Signal Processing Magazine, 2018.
[19] S. Cook. The complexity of dicorem-proving procedures. In STOC, 1971.
[20] G. Dantzig, D. Fulkerson, and S. Johnson. Solution of large scale traveling salesman problem. Technical Report P-510, RAND Corporation, Santa Monica, California, USA, 1954. 15
[21] A. Delarue, R. Anderson, and C. Tjandraatmadja, Reinforcement learning with combinatorial actions: application to vehicle routing. In NewrlPS, 2020.
[22] A. Delong, A. Osokin, Isack, and Boykov. Fast approximate energy minimization with label costs. JJCV, 2012.
[23] M. Denil, B. Shakibi, L. Dinh, M. Ranzato, and N. Freitas. Predicting parameters in deep learning. In NewrIPS, 2013.
[24] E. Denton, W. Zaremba, J. Bruna, Y. LeCun, and R. Fergus. Exploiting linear structure within convolutional networks for efficient evaluation. In NewrIPS, 2014. 3
10

---

[25] X. Dong, S. Chen, and S. Pan. Learning to prune deep neural networks via layer-wise optimal brain surgeon. In NeurlPS, 2017.
[26] M. ElAraby, G. Wolf, and M. Carvalho. Identifying efficient sub-networks using mixed integer program- ming. In OPT Workshop, 2020. 3
[27] C. Fefferman and S. Markel. Recovering feed-forward net from its output. In NewrlPS, 1994. 3
[28] M. Fischetti and J. Jo. Deep neural networks and mixed integer linear optimization. Constraints, 2018. 4,5
[29] Frankle and M. Carbin, The lottery ticket hypothesis: Finding sparse, trainable neural networks. In ICLR, 2019. 2,3
[30] J. Frankle, G. Dziugaite, D. Roy, and M. Carbin. Pruning neural networks at initialization: Why are we missing the mark? In ICLR, 2021.
[31] M. Gordon, K. Duh, and N. Andrews. Compressing BERT: Studying the effects of weight pruning on transfer learning. In Rep4NLP Workshop, 2020. 2
[32] LLC Gurobi Optimization. Gurobi optimizer reference manual, 2020. Version 9.1. 18
[33] Hahnloser, R. Sarpeshkar, Mahowald. Douglas, and S. Seung. Digital selection and analogue amplification coexist in cortex- cortex-inspired silicon circuit. Nature, 2000. 3
[34] S. Han, H. Mao, and Dally. Deep compression: Compressing deep neural networks with pruning. trained quantization and Huffman coding. In /CLR, 2016.
[35] S. Han, J. Pool, J. Tran, and W. Dally. Learning hoth weights and connections for efficient neural network. In NeurlPS, 2015. 2
[36] B. Hanin and Rolnick. Complexity of linear regions deep networks. In ICMI,, 2019.
[37] B. Hanin and D. Rolnick. Deep ReLU networks have surprisingly few activation patterns. In NewrlPS, 2019.
[38] S. Hanson and L.. Pratt. Comparing biases for minimal network construction with back-propagation. In NeurlPS, 1988.
[39] B. Hassibi, D. Stork, and G. Wolff. Optimal brain surgeon and general network pruning. In IEEE International Conference on Neural Nenworks, 1993. 2
[40] K. He, Zhang, S. Ren, and Sun. Deep residual learning for image recognition. CVPR, 2016. 18, 30 [41] Y. He, X. Zhang, and J. Sun. Channel pruning for accelerating very deep neural networks. In ICCV, 2017.
[42] R. Hecht-Nielsen. On the algebraic structure of feedforward network weight spaces. In Advanced Neural Computers. 1990. 3
[43] S. Hooker, A. Courville, G. Clark, Y. Dauphin, and A. Frome. What do compressed deep neural networks forget?? arXiv, 1911.05248, 2019. 1,
[44] S. Hooker, N. Moorosi, G. Clark, S. Bengio, and E. Denton. Characterising bias in compressed models. arXiv, 2010.03058, 2020.
[45] S. loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In ICML, 2015.
[46] M. Jaderberg, A. Vedaldi, and A. Zisserman. Speeding up convolutional neural networks with low rank expansions. BMVC, 2014.
[47] S. Janowsky. Pruning versus clipping in neural networks. Physical Review A, 1989.
[48] A. Krizhevsky al. Learning multiple layers of features from tiny images. 2009. 7, 18
[49] A. Kumar, T. Serra, and S. Ramalingam. Equivalent and approximate transformations of deep neural networks. arXiv, 1905. 11428, 2019. 3
[50] V. Kúrková and P. Kainen. Functionally equivalent feedforward neural networks. Newral Computation. 1994. 3

---

[51] V. Lebedev. Y. Ganin, M. Rakhuba, I. Oseledets. and V. Lempitsky. Speeding-up up convolutional neural networks using fine-tuned CP-decomposition. In ICLR, 2015. 3
[52] V. Lebedev and V. Lempitsky. Fast ConvNets using group-wise brain damage. In CVPR, 2016. 2
[53] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 1998. 3, 7, 18, 30
[54] Y. LeCun, J. Denker, and S. Solla. Optimal brain damage. In Newr/PS, 1989. 2
[55] N. Lee, T. Ajanthan, S. Gould, and P. Torr. A signal propagation perspective for pruning neural networks at initialization. In ICLR, 2020. 3
[56] N. Lee, T. Ajanthan, and P. Tomr. SNIP: Single-shot network pruning based on connection sensitivity. In ICI.R, 2019. 2,3
[57] H. Li, A. Kadav, I. Durdanovic, H. Samet, and H. Graf. Pruning filters for efficient convncts. In ICLR, 2017. 2
[58] J. Li, Y. Sun, J. Su, Suzuki, and Huang. Understanding generalization in deep learning via tensor methods, 2020.
[59] L. Liebenwein, C. Baykal, B. Carter, D. Gifford, and Rus. Lost in pruning: The effects of pruning neural networks beyond test accuracy. In MLSys, 2021. 2
[60] C. Liu, Arnon, C. Lazarus, Barrett, and M. Kochenderfer. Algorithms for verifying deep neural networks. CoRR, 2019. 9
[61] Z. Liu, M. Sun, T. Zhou, G. Huang, and T. Darrell. Rethinking the value of network pruning. ICLR, 2019. 3
[62] J. Luo. J. Wu, and W. Lin. ThiNet: A filter level pruning method for deep neural network compression. In ICCV, 2017. 3
[63] Z. Mariet and S. Sra. Diversity networks: Neural network compression using determinantal point processes. In ICLR, 2016. 3
[64] P. Molchanov, S. Tyree, T. Karras, T. Aila, and J. Kautz. Pruning convolutional neural networks for resource efficient inference. In ICLR, 2017. 2
[65] G. Montúfar, R. Pascanu, K. Cho, and Y. Bengio. On the number of linear regions of deep neural networks.
In NeurlPS, 2014. 1
[66] M. Mozer and P. Smolensky, Using relevance to reduce network size automatically. Connection Science, 1989. 2
[67] N. Narodytska. S. Kasiviswanathan, L. Ryzhyk, M. Sagiv, and T. Walsh. Verifying properties of binarized deep neural networks. AAAI, 2018.
[68] M. Paganini. Prune responsibly. arXiv, 2009.09936, 2020.
[69] R. Pascanu, G. Montúfar, and Y. Bengio. On the number of response regions of deep feedforward networks with piecewise linear activations. ICLR, 2014.
[70] A. Paszke, S. Gross, F. Massa, Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. PyTorch: An imperative style, high peeeorerforaccc deep learning library. In NewrIPS, 2019. 18
[71] P. Petersen, M. Raslan, and F. Voigtlacnder. Topological properties of the set of functions generated by neural networks of fixed size. Foundations of Computational Muthematics, 2020. 3
[72] M. Phuong and C. Lampert. Functional vs. parametric equivalence of ReLU networks. In ICLR, 2020. 3
[73] M. Raghu, B. Poole, J. Kleinberg, S. Ganguli, and J. Dickstein. On the expressive power of deep neural networks. In /CML, 2017. 1
[74] A. Renda, J. Frankle, and M. Carbin. Comparing rewinding and fine-tuning in neural network pruning. In ICLR, 2020. 3
12

---

[75] D. Rolnick and K. Kording, Reverse-engineerigg deep ReLU networks. In ICML, 2020. 3
[76] J. Rosenfeld, J. Frankle, M. Carbin, and N. Shavit. On the predictability of pruning across scales. arXiv, 10621, 2020. 3
[77] A. Rössig and M. Petkovic. Advances in verification of ReLU neural networks. Journal of Global Optimization, 2020. 9
[78] B. Say, G. Wu, Y. Zhou, and S. Sanner. Nonlinear hybrid planning with deep net learned transition models and mixed-integer linear programming. In IJCAI, 2017. 4
[79] T. Serra, A. Kumar, and S. Ramalingam. Lossless compression of deep neural networks. In CPAIOR, 2020.
2, 3, 4, 7,9, 9, 15, 17, 18, 22, 23
[80] T. Scrra and S. Ramalingam. Empirical bounds on linear regions of deep rectifier networks. In AAAI, 2020.
[81] T. Serra, C. Tjandraatmadja, and S. Ramalingam. Bounding and counting linear regions of deep neural networks. In ICMI,, 2018. 1,4
[82] S. Singh and D. Alistarh. WoodFisher: efficient second-order approximation for neural network compres- sion. In NewrlPS, 2020. 2
[83] G. Sourek and F. Zelezny. Lossless compression of structured convolutional models via lifting. In ICLR, 2021. 3
[84] S. Srinivas and R. Venkatesh Babu, Data-free parameter pruning for deep neural networks. In BMVC, 2015. 3
[85] J. Su, J. Li, B. Bhattacharjee, and F. Huang. Tensorial neural networks: Generalization of neural networks and application model compression, 2018. 3
[86] X. Suau, L. Zappella, and N. Apostoloff. Filter distillation for network compression. In WACV, 2020.
[87] T. Suzuki, H. Abe, T. Murata, S. Horiuchi, K. Ito, T. Wachi, S. Hirai, M. Yukishima, and T. Nishimura. Opectral-pruning Compressing deep neural network via spectral analysis. In IJCAI, 2020. 2,
[88] T. Suzuki, H. Abe, and T. Nishimura. Compression based bound for non-compressed network: Unified generalization error analysis of large compressible deep neural network. In ICLR, 2020. 2,
[89] H. Tanaka, D. Kunin, D. Yamins, and S. Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In NewrIPS, 2020. 2,
[90] V. Tjeng, K. Xiao, and R. Tedrake. Evaluating robustness of neural networks with mixed integer program- ming. In ICLR, 2019. 3,
[91] C. Wang, R. Grosse, S. Fidler, and G. Zhang. EigenDamage: Structured pruning in the Kronecker-factored eigenbasis. In ICML, 2019. 2,
[92] C. Wang, G. Zhang, and R. Grosse. Picking winning tickets before training by preserving gradient flow. In ICLR, 2020. 2,3
[93] W. Wang, Y. Sun, B. Eriksson, W. Wang, and V. Aggarwal. Wide compression: Tensor ring nets, 2018. 3
[94] K. Xiao, Tjeng, N. Shafiullah, and A. Madry. Training faster adversarial robustness verification via inducing ReLU stability. ICLR, 2019.
[95] X. Xing, L. Sha, Hong, Z. Shang, and J. Liu. Probabilistic connection importance inference and lossless compression of deep neural networks. In ICLR, 2020. 2,
[96] R. Yu, A. Li, C. Chen, J. Lai, V. Morariu, Han, M. Gao, C. Lin, and L. Davis. NISP: Pruning networks using neuron importance score propagation. In CVPR, 2018. 2,
1971 W. Zeng and R, Urtasun. MLPrune: Multi-layer pruning for automated neural network compression. 2018.
2
[98] Zhou, V. Veitch, M. Austern, R. Adams, and P. Orbanz. Non-vacuous generalization bounds at the ImageNet scale: A PAC-Bayesian compression approach. In ICLR, 2019. 2
13


Reviews:
[{"review_id": "meNWEYAR4a5", "reviewer": "Reviewer_nANE", "summary": "This paper proposes a method to solve the problem of exact compression of a neural network, where the network is decreased in size as much as possible,  with the result being functionally equivalent to the original network over the input domain. The proposed method identifies stably active and inactive neurons and remove a part of them from the network, while demonstrating significant speedup when compared to previous work.", "questions": "", "limitations": "", "rating": 7, "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": "This paper regards the problem of decreasing the size of a neural network as one of functional equivalence. The authors seek to create a smaller network which, when a particular input domain is considered, corresponds to the same function as the original. This is considerably different from the prevailing goal in related literature, which is to decrease the size of the network while considering only its performance according to a particular metric, over the input domain.\n\nAs in previous work performed by Serra et al. (2020), the method proposed identifies the stably active and inactive neurons of the network and removes them (the former by including some of them in that of the rest of the layer, and the latter by just removing them outright). Given the set of stably active and inactive neurons, the method to remove them which is proposed in this paper (Algorithm 1) is a variation of that present in Serra et al. The main novelty of this work is how these neurons are identified, using a single MILP per layer (presented in equations (7) - (12) as well as Algorithm 2 in the supplementary - which I would suggest including in the main paper). The proposed method is technically sound as a whole and provides demonstrable improvement when runtime is concerned.\n\nNevertheless, I have some concerns regarding the motivation and the limitations of this paper. As noted by the authors, their proposed method involves solving an MILP per each layer of the network, which is very expensive for large networks. My main concern is whether this expensive procedure should be considered, given that the problem of exact compression appears to be very demanding as a task, especially since regular pruning methods (which disregard whether the compression is exact or not) work faster and with small reduction in common evaluation metrics of a neural network (e.g. accuracy).\n\nThe authors highlight in the Related Work section interesting cases where exact compression might be preferred, namely classification problems on imbalanced datasets, as well as robustness. I believe that including such an experiment as a motivating example (i.e. for the first case, training a network for such a task, demonstrating failure of regular pruning techniques, and then demonstrating how much compression can be obtained by the exact compression scheme) would greatly strengthen the motivation behind the paper.\n\nRegarding the experimental evaluation present in the paper, it sufficiently demonstrates the speedup of the proposed method, as well as how much compression can be obtained under the exact scheme, both with and without regularization. I want to mention the fact that in Figure 3 and in most results in the supplementary, it appears that if there is no L1 regularization, then no nodes are removed. This seems interesting (since it demonstrates that the exact compression appears to require regularization to work) and I think it requires further discussion.\n\nThe paper is clearly written, and I only have minor comments to make:\n- As mentioned above, I would suggest including Algorithm 2 in the main paper, since it contains most of the novelty of the work (or at the very least better explain it in Section 5).\n- There are a couple of typos/missing words, in lines 26 and 303.\n- I would suggest adding comments in Algorithm 1, to clearly identify which part of the text corresponds to which part of the pseudocode.\n\nOverall, this is a good submission, but it lacks a few motivating examples to demonstrate the usefulness of exact compression. With those, I believe the significance of this work would be improved.\n\nReference:\n\nT. Serra, , A. Kumar, and S. Ramalingam. Lossless compression of deep neural networks. In CPAIOR, 2020.\n\n**Post-rebuttal comment**:\n\nAfter the author response, I have updated my score (see below comment for details).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately discussed the main limitation of their work, which is the difficulty to apply it in large networks. They have also adequately discussed its possible societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "_Zn73i7UXKq", "reviewer": "Reviewer_xWxW", "summary": "This work proposes a modified Mixed-integer linear programming (MILP) to compress a feed-forward deep neural network. The proposed algorithm seems to be work if some of the network neurons are stable. The authors evaluated the algorithm with several small datasets (MNIST, CIFAR-10, and CIFAR-100). ", "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": "1.\tOriginality: This work is an expanded work of the previously developed method, but the authors expanded it well with some interesting techniques. \n\n2.\tQuality: The submission is technically sound overall, but some minor improvements can be expected in the experimental results.\n\n3.\tClarity: The submission is well written and very clear. \n\n4.\tSignificance: The significance of the work is moderate. Despite the authors can attain the results about 10 times faster than the baseline, the proposed algorithm still not applicable on large networks.\n\n- Reviewer thinks the paper can be enhanced if the authors apply the algorithm to a small CNN. The CIFAR10 and CIFAR100 datasets usually hard to be achieved high accuracy on FFDNN. Fortunately, convolution can be lowered to matrix multiplication [1], the proposed algorithm can be easily expanded to CNN. Exploring this further would be helpful to the optimization community.\n\n[1] cuDNN: Efficient Primitives for Deep Learning\n\n- The authors mentioned the advantages of exact compression in line 33 as \"there is no risk of disproportionately affecting some inputs and others\". Please provide a concrete example of this.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "VFxzoSjkQI", "reviewer": "Reviewer_fHDg", "summary": "This paper proposes a MILP-based method for lossless compression of neural networks by removal of ReLU neurons whose output is characterized by a linear function, which can be merged or removed while inducing no change in functionality of the network.", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n  - Paper is largely well written and comprehensive.\n  - Paper furthers a relatively unexplored area of neural network compression (fully lossless compression).\n  - Work seems to be largely based on the cited work of Serra, et al, but shows improvement over that method in terms of runtime requirements and capability. \n\nWeaknesses:\n  - Method does not appear to be feasible when discussing very large networks.\n  - Further analysis on input selection could improve the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are largely discussed, as is societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "U_kg6e-wFom", "reviewer": "Reviewer_9nxn", "summary": "The paper builds upon prior work on MLPs with ReLU activations that leverage the insight that ReLUs are either linear or zero to formulate a MILP to solve the problem of _exact compression_, i.e., the process of reducing neurons in the networks while exactly preserving the output of the network for the input domain. The compression hinges on the insight that if a ReLU neuron is always activated it becomes an affine function while if it's always inactive it's simple zero and does not contribute to the output.\n\nTheir main contribution over prior work is a simple, but elegant insight on the problem formulation for the MILP that avoids solving the MILP exactly for each neuron in the network and instead solving it approximately at most N times (N = # neurons) while simplifying the problem (i.e. removing decision variables pertaining to neurons that are not stable) at each step so that only during the final call the MILP has to be solved exactly. The resulting exact compression problem thus has significantly reduced runtime compared to prior work leading to the ability to scale to larger networks (up to 2x800 or 5x100 in their experiments compared to 2x100 in prior work).", "questions": "", "limitations": "", "rating": 7, "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": "## Score\n\nI like the paper and I think that MILP formulations are powerful tools with broad range of applications for ReLU networks including compression, robustness, verification, etc... As such, the contribution to improve upen and scale MILP-based problem formulations in ReLU networks is an important contribution to the community on its own and hopefully many other papers can benefit from the insights presented in this work. \n\nHowever, I do have some concerns regarding the application to compression and the resulting compression results. My main concern is that the experimental results (e.g. Fig 3a, 3h, 3o) indicate that you can only start doing meaningful compression (meaningful in the sense that you can remove a significant amount of neurons) once you increase l1-regularization, which however at that point already hurts the test accuracy. So with this method it seems you cannot get compressed networks without loss of accuracy compared to the best performing network. \n\n\n## Ways to Improve my Score\n\nGiven the interesting insights into the problem formulation and the resulting impressive performance in terms of scalability of the MILP, I believe the paper needs to significantly improve some of its discussion and presentation of the experimental results. I am listening my concerns (\"Weaknesse\") in more details below. If the authors can address these concerns sufficiently during the rebuttal I would be happy to increase my score. \n\n\n## Strengths\n\n* Very insightful and impactful re-formulation of MILP-based problem formulations for ReLU networks. These insights may also be useful beyond the compression community. \n\n* Strong introduction and presentation of related work. \n\n* Easy-to-follow and good writing style. \n\n* Cool presentation of the main contributions in Sections 5.1-5.3. I learned something while reading the paper. \n\n\n## Weaknesses\n\n* My main issues comes down to the experimental performance, mainly around Fig. 3. It seems to me that you need a lot of l1-regularization in order to be able to prune any non-negligible number of neurons. However, at that point the test accuracy has already dropped significantly compared to the networks that are only slightly regularized or unregularized. Please consider discussing some of these aspects in more detail in the paper and try to understand (even on an intuitive level where this is coming from). Alternatively, can you find scenarios where this is not the case? Maybe relaxing the search space for the input space could be one way because assuming the entire $[0,1]$ domain for MNIST, e.g., might still be too large for what is a reasonable input? \n\n* Even if there is not an obvious scenario where the compression is more useful without accuracy loss, the authors could be discussing other potential applications or use cases of their novel MILP-formulations in order to increase the impact of the paper and the possible applications so that other researchers can benefit from their contribution. \n\n* Could you discuss applications to other type of networks? What about convolutional layers for example? Even simple CNNs like LeNet5 could be interesting. There should be a hopefully ease generalization of the formulations to convolutional layers and I would love to see some preliminary results or discussions in that direction\n\n* I am not a big fan of Section 5.4. I think it's too formal for something that intuitively makes a lot of sense. I would move all the theoretical results and the pseudo-code into the appendix for people if they are interested in seeing a very formal discussion about how neuron stability can be used for compression. In the main paper, I would instead focus on a high-level summary of this section. I would then use the space to expand upon some of the additional technical details with regards to Sections 5.1-5.3, i.e., move some of the material from supplementary Sections A-E into the main paper potentially even including Algorithm 2.\n\n\n## Minor Feedback\n\n* line 26: typo: \"that not equivalent\"\n\n* A few more interesting and recent references for your related work: \n  * On robustness of pruning (line 65): https://arxiv.org/abs/2103.03014\n  * 2nd order prune methods (line 73,74): https://arxiv.org/abs/2004.14340\n\n* The first sentence in the abstract is somewhat mis-leading. It is really only true for ReLU networks I believe. \n\n* Maybe mention how you would handle batch-norm and data normalization in the first layer. Might be obvious some readers but potentially not to everyone. \n\n* Lines 121-125: Could be a little more specific what the decision variables of the MILP are? That took a while to understand and could be much streamlined if you mention that more explicitly. \n\n* Thank you for submitting a detailed appendix and code. Very helpful and very much appreciated. \n\n## Update after Discussion\n\nThe authors have responded to my concerns throughout the rebuttal period and clarified lingering points of confusion I raised in my initial review. Specifically, they addressed all my concerns mentioned in the \"Weaknesses\" section of my initial review and added additional insightful experiments. I want to emphasize that the additional results definitely should make it into the final submission if accepted. \n\nI have raised my score from 6 to 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, appropriately addressed, although I would tone down the 2nd part about societal impact with regards to \"minoritized groups in society\". While I get the authors' point, I think it's too much of a stretch.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers have agreed that the submission is original and interesting with clear/practical contributions to the domain. Authors’ detailed and informative responses also addressed most of the major concerns and some of the reviewers accordingly increased their scores. Given the overwhelming positive opinions, I am recommending an acceptance.
Decision: Accept (Poster)