Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Strengths:
  - Paper is largely well written and comprehensive.
  - Paper furthers a relatively unexplored area of neural network compression (fully lossless compression).
  - 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. 

Weaknesses:
  - Method does not appear to be feasible when discussing very large networks.
  - Further analysis on input selection could improve the paper.
limitations_and_societal_impact: Limitations are largely discussed, as is societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

Their 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).
main_review: ## Score

I 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. 

However, 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. 


## Ways to Improve my Score

Given 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. 


## Strengths

* Very insightful and impactful re-formulation of MILP-based problem formulations for ReLU networks. These insights may also be useful beyond the compression community. 

* Strong introduction and presentation of related work. 

* Easy-to-follow and good writing style. 

* Cool presentation of the main contributions in Sections 5.1-5.3. I learned something while reading the paper. 


## Weaknesses

* 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? 

* 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. 

* 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

* 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.


## Minor Feedback

* line 26: typo: "that not equivalent"

* A few more interesting and recent references for your related work: 
  * On robustness of pruning (line 65): https://arxiv.org/abs/2103.03014
  * 2nd order prune methods (line 73,74): https://arxiv.org/abs/2004.14340

* The first sentence in the abstract is somewhat mis-leading. It is really only true for ReLU networks I believe. 

* 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. 

* 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. 

* Thank you for submitting a detailed appendix and code. Very helpful and very much appreciated. 

## Update after Discussion

The 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. 

I have raised my score from 6 to 7.
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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

As 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.

Nevertheless, 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).

The 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.

Regarding 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.

The paper is clearly written, and I only have minor comments to make:
- 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).
- There are a couple of typos/missing words, in lines 26 and 303.
- I would suggest adding comments in Algorithm 1, to clearly identify which part of the text corresponds to which part of the pseudocode.

Overall, 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.

Reference:

T. Serra, , A. Kumar, and S. Ramalingam. Lossless compression of deep neural networks. In CPAIOR, 2020.

**Post-rebuttal comment**:

After the author response, I have updated my score (see below comment for details).
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_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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). 
main_review: 1.	Originality: This work is an expanded work of the previously developed method, but the authors expanded it well with some interesting techniques. 

2.	Quality: The submission is technically sound overall, but some minor improvements can be expected in the experimental results.

3.	Clarity: The submission is well written and very clear. 

4.	Significance: 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.

- 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.

[1] cuDNN: Efficient Primitives for Deep Learning

- 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.
limitations_and_societal_impact: -
review_title: null

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)