Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper presents a new method for network pruning based on coresets which relies on inner and outer approximations of the convex hull of the weights of each layer of the neural network, with the inner approximation being obtained from a subset of the weights of the neurons and the outer approximation being a dilation of the former. This form of determining which weights to prune is almost completely independent from the dataset, which is one of the main advantages claimed by the authors.
strengths_and_weaknesses: This paper presents some interesting ideas, but it is not easy to follow. I have several comments to the authors about how to improve the writing below. Among other things, some concepts are used before definition, some explanations are repeated, and often it is only possible to understand what is going on when a new and more accessible definition is presented. However, what really concerns me is the limited experimental evaluation: the last sentence of the abstract sounds an alarm of hand-picking. Indeed, the results in Section 3 are very limited: only one pruning rate is used for each method tested, which is far from ideal. I would not expect a new method to always beat all other methods in order to accept a paper, but I do expect to see a thorough assessment of where and why a new method performs better. Finally, I believe that the authors understand quite well what they are doing and are very excited about it, but they also need to provide more context for the readers by going over their design choices in more detail and with more context and explanations to non-experts.

### Comments on the writing

Section 1:
- In the Abstract, line 5, you write data dependant. In the Introduction, line 61, you write data-dependent. Please choose one convention for spelling and hyphenation.
- The whole paragraph on coresets is very difficult to read and I could only understand most of it (except for my question about x*) after reading the paragraph "How to prune using coresets?" in Section 2, in which the useful parts are actually repeated. I would encourage the authors to rewrite this and perhaps merge both paragraphs at a convenient point.
- Line 46: "corestes" -> coresets
- Line 69: "guarantees" -> guarantee

Section 2:
- Line 88: "See" -> see
- By the time that [n] is defined in line 92, it has already been used in line 83.
- Definition 2.2 repeats a lot of terms that were already introduced in the second paragraph of Section 2. Again, I would encourage the authors to think of rewriting the paper with less repetition, more clarity, and each term introduced at the most appropriate time.
- Line 113-114: the excerpt "and it corresponds to the importance of this point with respect to the query space at hand" seems to refer to s(p) rather than its denominator alone, but it is not clear from context.
- Line 118: "Our method hinges upon an elegant combination of": Academic papers should not contain self-praise; please remove "elegant". Likewise for "an elegant combination" in line 326.
- Line 137: One of the many examples of the use of "e.g." looks a bit unusual: are you saying that ReLU, among many others, does not admit such an approximation? Please also revisit other uses in the paper (line 148) and compare them with the form in which this abbreviation is commonly used.
- Line 139: Replace "at" with "in" (two incidences; see also lines 148, 156, 194 twice, 195, 208, 286)
- Caption of Figure 1: Replace "novelty" with "contribution"? In the fourth line, replace "A" with "a"
- Line 161: Add "an" after "constructing"
- Line 221: "Deep" -> deep

Section 3:
- Line 254: Remove quotes from "Numpy"
- Line 293: "obtain a" -> obtain an; remove comma between "coreset" and "when"

Section 4:
- Line 322: "Decision Trees" -> decision trees

Section 5:
- Line 328: "on variety" -> on *a* variety

References:

- Remove [5]: duplicate of [6] with wrong publication year
questions: 1) In Section 1.1, line 42, what do you mean by finding a query x*? My understanding is that you are actually looking for a subset of all queries, not for a single one.

2) In Section 2, line 83, what do you mean by w(p_i) := w_i? I understand that every neuron of the top layer has a weight for the neuron at the bottom layer, but it is not a function of the value of its weights.

3) What is the reason for assuming all the weights of P as equal to 1 in the main paper?

4) In Section 2.1, between lines 114 and 116, what do you mean by "Once we bound these sensitivities" and "The size of the sample is proportional to the sum of these bounds"?

5) In Theorem 2.3, line 127, what do you mean by "points with nonempty interior"? Points do not have interior.

6) In Section 2.2, line 133, can you explain what do you mean by the dilated form of B consisting of a conical combination? Wouldn't it make more sense to say that this is a weighted sum in which the sum of the weights now exceed 1?

7) In Section 3, why is every network pruned with a different subset of approaches? What happened with the missing ones in each of those cases?

8) In Table 1, what is the meaning of "Baseline Err." and "Pruned Err."? Is the first the complement of the accuracy and the second the drop due to pruning? Why is the first one almost the same but not always across all methods tested?

9) In Table 2, what is the meaning of "FR"?

10) In Table 3, is "Orig. Err." the same as "Baseline Err." from before? If so, please make it uniform.

11) Why is only one pruning rate reported for each model and approach?

12) How do you think coreset-based pruning relates to what happens in the case exact compression methods (e.g., https://arxiv.org/abs/2102.07804 & https://arxiv.org/abs/2107.07467)?
limitations: No; Section 5 talks about future work, which is not the same thing as limitations of the current work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a method for pruning neural network weights at each layer. This improves on previous algorithms for activation function coresets by attaining tight sensitivity bounds with no data assumptions and mild assumptions on the network weights. The coreset construction relies on combining two key ideas from convex geometry: specifically finding the Caratheodory set of each vertex of a John-Löwner ellipsoid. Experiments show that the proposed approach outperforms several recent baselines, pruning more weights while achieving lower classification error.
strengths_and_weaknesses: ## Originality/Significance/Quality
- Builds on previous work on network pruning in a novel way via tools from convex geometry
- Cites related work where appropriate
- Elegant idea that with intermediate results that may be of independent interest
- Experimental results look impressive, although different baselines are used in different experiments

## Clarity
- The paper is generally a pleasure to read, but I have a couple of suggestions:
    - The weights assumption (Regression Complexity Measure) is a key contribution of the paper, and the presentation would be improved it if was mentioned earlier, perhaps with an informal statement and/or background motivation in Section 1
    - The John ellipsoid is defined with a dilation of $d$ (ambient dimension), but is used in Lemma 2.7 with a dilation of $r$ (rank).
- Typos
	- Line 140: "with respect ReLU" should be "with respect to ReLU"
	- Line 148: "at [74]" should be "in [74]"
	- References [5-7] are identical

questions: - Why different baselines used for different tables/models/experiments?
- Is Theorem 2.8 directly comparable with previous work?
- Do you have any intuition/empirical results on what dimensionality reduction method works best in this setting?
- Can this method be applied to attention-based networks such as transformers?

limitations: This paper describes limitations as opportunities for future work, but does not address any potential negative social impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper aims to advance coreset-based neural network pruning by relaxing the assumptions made in the previous works (especially Mussay et al.). This work claims to provide data-independent sample complexity bounds for layer pruning for multiplicative coresets including for ReLU-like activations which were considered to be non-approximable with fewer than O(n) samples. Novelty aspects come by providing a different upper bound for sensitivity, to be used for importance sampling. This upper bound on sensitivity uses certain conditions satisfied in Algorithm 1 which uses the Carathéodory theorem applied to the vertices of maximal volume ellipsoid contained within the convex hull of weights in a layer. Having mentioned these theoretical results, the paper empirically shows the efficacy of their algorithm on different architectures (LeNet, VGG, and ResNet) on different datasets (MNIST, CIFAR-10, and ImageNet-1K). 
strengths_and_weaknesses: Strengths:

- The theory seems to be reasonably sound and novel (usage of Löwner-John ellipsoid with Carathéodory theorem). 
- The Paper is decently written albeit I’ve some questions (described later)
-  Empirical experimentation involves a variety of networks and datasets and baselines. 

Weaknesses:

Weaknesses of this work are mostly my questions and some suggestions which call for small experimentation for coreset guarantee. I describe them as follows:

- Since the work follows the same notations as in Mussay et al. can they also include a neural network diagram so that it would be easier to follow what is mentioned in line 77? 
- Line 699 claim 1: why does the ellipsoid have at most 2r vertices? Shouldn't that be exactly 2r? 
- What is special about the vertices of the ellipsoid that is used to get the Carathéodory set?
- The upper bound on sensitivity (and hence on the normalizing constant t) is in terms of regression complexity measure $\mu(P)$. Is there any bound on this term, or this can get arbitrarily large (somewhere as large as the o(n)?).
- I am unable to comprehend why following this procedure would lead to the possibility of multiplicative coresets. The proof given by Mussay et al. (Appendix A.1) describes a possibility of the case that shows that for ReLU like activation functions sample complexity is O(n). Why should this procedure not fall into the case mentioned by Mussay et al.?
- In Definition 2.5, it may be better to use $x \in \mathbb{R}^{d} \times {1}$ and $P \subseteq  \mathbb{R}^{d+1} $. 
- Algorithm 2:  r is not defined. 
- Algorithm 2: To run the while loop runs iff $|Q| \geq 2*rank(Q)^2$. Where did this condition come from? In neural network pruning setting where |Q| at the beginning would be the #neurons in the next layer and rank(Q) can be at max #neurons in the next layer, how often does this while loop ever get executed? 
- On the empirical side: similar to Mussay et al, can authors include a curve showing true multiplicative error in some simulations, comparing it with baselines, showing the efficacy of their method? 
- Can authors include pruning results without re-training as well like Mussay et al.? It is important to see how performance looks when not re-trained.  
- All the results need to have the standard deviation attached for the testing error.  
- Table 1: Why is the PR different for the methods but PvC or  Algo2? 


Add the following to the related work:

- Gantavya Bhatt and Jeff Bilmes. Tighter m-DPP Coreset Sample Complexity Bounds. In ICML 2021 Workshop: SubSetML: Subset Selection in Machine Learning: From Theory to Practice, Virtual, July 2021. This paper aims to improve bounds for DPP-based coreset and show possible applications to neural networks pruning (similar to mussay et al.) 

- Diversity Networks: Neural Network Compression Using Determinantal Point Processes. Zelda Mariet, Suvrit Sra


I'm willing to raise my rating upon satisfactory response. 
questions: As mentioned in the main review.
limitations: As mentioned in the main review.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: **Summary of results**
The main scope is compression of neural networks with coreset: How to remove neurons or filters after training such that we achieve almost the same performance. The paper proposes an $\ell_{\infty}$ coreset for $\ell_1$ regression (in Lemma 2.7). This coreset is exploited for pruning a single-layer neural network with ReLU activations with all-one output weights (details in Definition 2.2). Compared to existing results in the literature,  the proposed theoretical guarantee is data-independent without explicit assumptions on the norm of inputs. Experimentally comparisions have been conducted on standard neural networks to compare the proposed coreset-based pruning with baselines. 

**Comments on relevance and importance of the scope** 
Pruning neurons not only enhance the storage and computational complexity of neural networks but also may enhance the generalizability of the nets. Thus, it is a core topic in neural computing. 




strengths_and_weaknesses: 
**Advantages**
1. Compared to existing results, the coreset size is data-independent up to the regression complexity measure.   
2. The proposed algorithm handles low-rank weight matrices that are essential in pruning neural networks. 
3. Nice literature review and introduction 
4. Experimental comparison with various existing methods 
5. In my view, the proposed $\ell_{\infty}$ coreset for $\ell_1$ regression in Lemma 2.7 is more interesting and solid than the main theorem and coreset design for neural networks. 
6. Details of the coreset design with complexity analysis of algorithm 

**Main Concern** 
1. The proposed bound strongly depends on the regression complexity measure, which is not proven to be **bounded**. Notably, we can design sets for which this complexity measure scales with the size of the set. For such a set, the established coreset-size is greater than the number of neurons, hence the theoretical bound is vacuous. 
2. To compare the baselines, I recommend checking comparisons for networks with the same accuracy levels and comparison rates (in tables 1-3). Indeed, the compression has to be conducted on the same input networks (so with the same level of accuracy). Comparing compression algorithms on different networks may not lead to a fair comparison. 


**Minor Comments**
 Adding details about the computational complexity of methods to find Lowner ellipsoid would improve clarity.  

**Post Rebuttal** 
The response address my major concerns so I updated my score. 
questions: 1. There are coreset designed for l1 regression with similar techniques:(i) Lowner ellipsoid and (ii) Caratheodory set (see, for example, the survey on Sampling Algorithms and Coresets for $\ell_p$ Regression). I wondered what the novelty of the proposed algorithm compared to these exciting methods for l1 regression. 
2. Can authors validate boundedness of regression complexity measure for simple cases? 
3. Is it possible to characterize a worse case for the regression complexity measure?

limitations: This project does not have negative social impacts.
review_title: null

Meta-review: metareview: The paper proposes a method for pruning neural network weights at each layer. The authors have addressed the concerns from the reviewers and the reviewers raised their scores. Although the reviewer somewhat agrees with the authors that the standard practice in the network pruning literature is to report a very limited set of results, the reviewer expects the authors to try a bit harder to expand the results for the final revision. Please incorporate the reviewers’ suggestions in their detailed reviews and revise the final version of the paper properly.
confidence: Less certain
Decision: Accept