Previous work showed empirically that large neural networks can be significantly reduced in size while preserving their accuracy. Model compression became a central research topic, as it is crucial for deployment of neural networks on devices with limited computational and memory resources. The majority of the compression methods are based on heuristics and offer no worst-case guarantees on the trade-off between the compression rate and the approximation error for an arbitrarily new sample. We propose the first efficient, data-independent neural pruning algorithm with a provable trade-off between its compression rate and the approximation error for any future test sample. Our method is based on the coreset framework, which finds a small weighted subset of points that provably approximates the original inputs. Specifically, we approximate the output of a layer of neurons by a coreset of neurons in the previous layer and discard the rest. We apply this framework in a layer-by-layer fashion from the top to the bottom. Unlike previous works, our coreset is data independent, meaning that it provably guarantees the accuracy of the function for any input x ∈ R d , including an adversarial one. We demonstrate the effectiveness of our method on popular network architectures. In particular, our coresets yield 90% compression of the LeNet-300-100 architecture on MNIST while improving classification accuracy.
------ 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.