Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper provides a data-independent way for pruning neutrons in deep neural networks with a provable trade-off between its compression rate and the approximation error. The output of a layer of neurons is approximated by a corset of neurons in its preceding layer. 

The pruning of neurons based on the coresets is shown to be effective when compared with other methods. The authors have validated it on two convolutional network architectures.  

The paper starts from defining the coresets and introducing the VC dimension, and extends the theorem to more generalized cases. 

The coreset seems to require the activation function to be non-negative, which will possibly limit the scope of application of the proposed theory. 
review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: ------ after reading authors' response ------
Thanks for the complete response and revision. The new Fig 4 is very nice, and this helps address my concerns. I'm more favorable of the paper now, changing from "Weak Accept" to "Accept".

Note a small typo in the displayed equation just above Fig 4: the sum is over $P_{test}$ but it's written $P_{t}est$ (and also using \text makes it look nicer, $P_{\text{test}}$)

------- original review -----
The paper proposes a neuron pruning technique that can compress an existing pre-trained neural net (though the experiments actually do additional unspecified "fine-tuning" training). It is motivated by the need to compress neural nets so they work on embedded devices (smart phones, etc.), and it is in contrast to most other techniques that prune at training, or prune after-training but prune weights not nodes. They argue convincingly that pruning weights is awkward, as one has to work with sparse matrices which are only actually effective for extreme sparsity levels. They also claim another big benefit is that theirs is the first with with (1) provable guarantees, and (2) is data-independent.

I have a some criticism of the paper, but before I get lost in the details, let me say that I like the overall paper. I think it's a clever idea, it's a useful topic, the authors show very good understanding of the coreset literature, and it has some nice theory.  The paper is also well-written and easy to understand, and the appendix is short enough that I actually read it.

However, I have at least two major comments:


(1) The theorems are nice, but with the exception of Thm 6 (which I like), they are simple applications of existing results. My main issue is that you have not provided an end-to-end bound. There are two things lacking:

(1a) Lack of dealing with several layers, e.g., composing your approximation error. With an additive error instead of a relative error, does composition cause a major problem? Seems like this could be an easy theorem.

(1b) Lack of a clear final statement bounding the overall error. This is somewhat trivial (if you have a single pruned layer), but it makes the assumptions more clear. In particular, you assume the input x has norm bounded by beta. In this sense, you have not provided a "data-independent" guarantee.  Since you do not have a relative error bound, the norm of x is important.  Yet this also exposes something that really confuses me: for the ReLU activation, with non-negative inputs, this is positive homogeneous, i.e., phi( beta ||p|| ) = beta phi( ||p|| ). If you look at step 2 in Algo 2, you see that the choice of beta does not affect the probabilities (if phi is ReLU or anything else with this property). Thus we can choose beta arbitrarily... and thus you have a fixed additive bound, for an arbitrarily large input, which seems impossible!

(2) Experiments were very promising, but I'm not convinced about the baselines.

(2a) The fine-tuning after pruning wasn't described so I don't know how much effect it had. It makes sense to do this, but it means that it is less clear if your results were due to your theorem.  Please show results with and without the fine-tuning, and describe the fine-tuning (how many epochs of training?)

(2b) You do some abstract experiments with random weights, to test your theorem, which is a nice somewhat direct test of your results (I assume here you are not fine-tuning, as it doesn't make sense, right?). Also in the abstract setup, you could test this as a function of depth, since I'm worried that your error guarantees get worse as a function of depth. The experimental setup was vague: what are the inputs x (from a ball, or sphere? uniform?), was this averaged over many runs? What was this network (you change size when you go to the LeNet-300-100), especially, what was the 100% number of samples (1000?)?.

(2c) For table 3, taking the LeNet for example, you have 90% compression and improved error. This is nice, but to really convince me, in addition to adding the results without the fine-tuning, I'd like to see what you get with uniform pruning (say, with 85% compression) with and without fine-tuning. I don't have a good "baseline" expectation here, so while your improved error with 90% compression seems like a fantastic result, I suspect that one might get similar results (with say 85% compression) with trivial subsampling.


Some minor comments: 

-- abstract, "guarantees the accuracy of the function" and "... on MNIST while improving the accuracy."  These are 2 very different meaning of "accuracy", so please be more precise, e.g., a per-layer approximation error vs classification error on testing data.

-- First paragraph of intro, saying networks are limited to HPC environments is hyperbole. These networks might need to be trained in an HPC environment, but most can be deployed on laptops (not an HPC environment). A bigger issue is deploying them on a smartphone.  Adding some quantitative numbers would strengthen your case (e.g., size of typical neural nets, and size of RAM in a smartphone).  Note that training requires much more memory due to memory explosion in backpropagation, but this does not effect runtime/deployment.

-- middle of page 2, "is very fast, ..." the comma should be a semicolon to make it grammatically correct.  Page 3, near bottom, "corests" is a typo.

-- personally I dislike things like Table 1, as they feel too much like boasting. You've chosen the columns carefully so it doesn't feel that meaningful, and you've already stated these things in the text. But it's not my paper.

-- def 4 is very hard to parse. Are these subsets or strict subsets?

-- Notation B_alpha could be explained; I'm used to seeing B_alpha(0), and you can always just write \forall x with ||x||<= alpha to make it super clear.

-- Your theorems require phi to be non-decreasing, but intuitively you can clearly handle non-increasing, since the set of inputs x \in B_beta is invariant to sign changes. More generally, you could assume the existence of some 1D function psi(t) such that phi( t ) <= psi( |t| ). I don't know if there are many more common activation functions, but this could give a wider class.  The change to the proofs is trivial, since you just replace psi( |t| ) for phi( alpha beta).

-- If Corollary 9 "follows directly from Theorem 5", why didn't Thm 7 and Corollary 8 also follow directly? You mean, it follows, but using the same simple bounding tricks from the appendix as used for Thm 7 and Corollary 8, right?

-- Fig 3 shows very nice results

-- A.1 Proof of Thm 6, you could use \subsetneq (with amssymb package) to be more clear that it is a strict subset, since I find \subset vague since different authors have different conventions.
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: The authors proposed a model compressing method based on coreset framework. The goal of the paper is to reduce the number of neurons. The basic idea is sampling the neurons on each layer with probability equal to the neuron's max share among all the outputs to the next layer, and updating the weights associated with the remained neurons. Another main contribution is the authors provided theoretical analysis to guarantee the accuracy vs compression trade-off for all possible inputs.
Pros:

The proposed method is easy to understand and seems to make sense.
The theoretical analysis seems strong.
The experiment results on two datasets show the proposed method achieved high compression rate and improvement of accuracy.


Cons:

Despite the theoretical guarantee, it is not as clear on the value of the proposed method in real world. I would be better to test on more datasets and networks to verify the effectiveness of the proposed compressing method, as it claimed to be data-independent.


Although the method achieved very good experiment results, its contribution to the high accuracy is unclear, since the networks were fine-tuned after the compression. So how do we exactly evaluate the accuracy vs compression trade-off when there is no such trade-off shown in the experiments?


Questions and suggestions:


In the Fig 2, it seems that the performances of the proposed method and the percentile-based method should be close to each other, and the uniform sampling method should be worse than them. However the results are opposite. If it was not incorrect labeling in the figure, it would be good to add some analyses about this result.

To solve the second point in "Cons", is it possible to show the accuracy of the compressed model without fine-tune? Or still fine-tune the model but simply set u(q) = w(q) in the line 8 algorithm 1?
review_title: Official Blind Review #1

Meta-review: The rebuttal period influenced R1 to raise their rating of the paper.
The most negative reviewer did not respond to the author response.
This work proposes an interesting approach that will be of interest to the community.
The AC recommends acceptance.
Decision: Accept (Poster)