Venue: NeurIPS 2022 Conference

Reviews:

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: The authors propose a layerwise pruning method that formulates the problem of eliminating neurons as a weakly submodular optimization problem for which the well-known greedy algorithm gives an approximation guarantee.  They illustrate the practical performance of three different variants of their strategy when extended to prune the entire network on a variety of tasks.
strengths_and_weaknesses: Originality: The idea of formulating the pruning problem to take advantage of weak submodularity is novel to me.  Although it does build somewhat crucially on existing work.

Quality:  The technical and experimental results seem to be well-executed to the best of my assessment.  One can always add more competitors and try on a wider variety of architectures, but I found the selected experiments to be illustrative and compelling.

Clarity:  The exposition was clear overall though I found Figure 1 tough to read even after significant zooming.

Significance:  While it may be more expensive than some other approaches, the cost of this procedure is typically only born once.  So, I can see this as being a very useful tool in practice and may spur pruning research in novel directions.
questions: It would be nice to see some discussion of the practical computational cost among the various methods in the main text.  While I don't see the cost of this method as overly limiting, it is nice to get a sense of how taxing the methods really are. 

Also, some thoughts about why the approach seems to do much better in some regimes while only comparable in others?
limitations: Some limitations were discussed, though I don't see the focus on the data limited regime as a limitation of the methodology necessarily.  Or am I missing something important?
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper propose a network pruning approach via sub modular optimization. The proposed method uses a greedy fashion to layer-wisely select neuron that improves the performance most. This paper shows that the returned solution given by the greedy algorithm is able to well approximate the optimal solution (of a NP hard problem). To reduce the cost, a computation-saving approach is also proposed. Empirical results shows that the approach is able to achieve good performance when the available training data at pruning is small.
strengths_and_weaknesses: Overall I find this paper quite interesting, especially its performance when there is limited number of training data at pruning. The theoretical guarantee is also stronger and does not require stronger assumptions. However, I do have some concerns:

1. It seems the proposed method in general is very similar to Ye at al.. Both methods are greedy forward selection and the different seems subtle. Could you give more discussion in terms of methodology?

2. Following up Q1, it seems that an main improvement over Ye at al is to reduce the computation cost. However, [1] also propose a new technical to reduce the cost and I was wondering how does your method compares with [1]?

3. What would max_{|S|\le k} F(S) looks like? I understand that it is NP hard but it would be interesting to show how this quantities looks like.

4. Can we empirically verify the \gamma_{U,k} as this is an important quantity?

[1] Greedy Optimization Provably Wins the Lottery: Logarithmic Number of Winning Tickets is Enough

questions: See above.
limitations: Yes
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: The paper proposes a neural network node pruning method and shows that the objective is essentially a form of weakly-submodular function optimization. Therefore, the pruning of a single layer can be solved using the greedy algorithm with a theoretical guarantee. The paper also shows that using a limited number of data, the proposed method is able to achieve the best performance compared to baselines.
strengths_and_weaknesses: Strengths:
1. The paper draws a very intriguing and solid connection between neural network pruning and submodular optimization. More specifically, the weakly-submodular optimization factor is closely related to the activation matrix.

2. The paper studies the problem in a comprehensive manner, including pruning of regular regions of neurons, strategies of pruning multiple layers, and speed-up tricks for the submodular optimization.

3. The proposed method empirically achieves the best performance compared to baselines on some network structures under a limited number of samples.

Weaknesses:
1. The proposed approach has relatively high computational complexity. It seems that scaling would be a problem for scenarios such as larger network structures or utilizing a large number of data samples for pruning.

2. Given the limitation of the complexity, I guess that the empirical experiments could be hardly extended to more complex datasets (e.g., ones with larger image dimensions) or larger network structures.

3. The proposed framework only works for one layer. For pruning of multiple layers the paper proposes some heuristics.

questions: 1. Can authors estimate the weakly-submodular factors gamma in the experiments and report the corresponding guarantees? Can authors also discuss high tight are the estimates of such factors provided in Proposition 3/4?

2. Can authors provide wall clock running time of the optimization algorithm on the experiments and discuss the limitations of the complexity?

3. For multiple layer pruning, it seems that the changes of one layer could affect the pruning of other layers. Can the authors provide some insights about the empirical behaviors of convergence of the proposed methods?
limitations: Yes.
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: Goal: effective and efficient structured pruning of a pre-trained NN-network if only small amount of unlabeled training data is available

Contributions: 
1) The authors propose a new technique (called "principled data-efficient structured pruning") that alters the existing  "reweighting" method [Mariet and Sra, 2015]. Unlike [Mariet and Sra,2015]:
     * submodular optimization ... they  formulate the subset selection problem of  structured pruning as a weakly submodular maximization problem  and solve it approximately by greedy search
     * extended pruning: pruning of regular regions of neurons (e.g., channels) and three strategies for pruning of multliple layers 
     * limited number of training data (cca. 1% of the original training data) with no labels and one-shot pruning (without fine-tuning)
2) Theoretical justification of the method and its performance (in the Supplementary material).
3) Experimental evaluation of a solid scope with promising results.

strengths_and_weaknesses: Strengths (significance and quality):
1) The problem of effective structured pruning of a pre-trained NN-network in the presented limited-data regime is important. Most of the existing structured pruning techniques require greater amount of training data and fine-tuning to work well. The proposed method (or even its particular parts) appears to be a valuable contribution with this respect.   
2) The experimental evaluation of a solid scope offers promising (outstanding and stable) results.
3) Theoretical performance guarantee.
4) The authors try to be fair in their comparisons with concurrent techniques (e.g. the application of reweighting, various parameter settings...) and analyze also the weaknesses of their method.

Clarity:
1) The submission is relatively clearly written and easy to read (except the theoretical parts and the figures). If there was enough place, I would prefer to move more experimental results from the supplementary into the main paper.  The figures (e.g. Figure 1) are small and less comprehensible. It would maybe help to scale the graphs differently, to highlight the variants of the proposed method or to change the used colors. 

Novelty:
1) The novelty of the contribution is slightly limited. The proposed method is based on previous work by [Mariet and Sra,2015]. The original method is altered using the principles of submodular optimization to be advantageous in the new context of  limited-data. 
2) The related work is cited and addressed adequately. 
questions: 1. In the abstract,  you write that "current structured pruning methods do not provide any performance guarantees". Later on, e.g., on lines 75-78,  you mention one such method. You should add something like "most of" into the abstract to be fair. 

2. To confirm the novelty of your method, it would be nice to analyze in a more concrete way, what the  [Mariet and Sra,2015] method uses instead of submodular optimization and greedy search. Did you compare your approach to  [Mariet and Sra,2015]  exactly?
limitations: OK: The authors try to analyze both strengths and limitations of the paper in the experimental part.
review_title: null

Meta-review: metareview: The paper proposes a data-efficient structured pruning method, that for a given layer finds neurons/channels to prune with corresponding new weights for the next layer, that minimize the change in the next layer's input induced by pruning. This selection problem is formulated as a weakly submodular maximization problem, thus it can be provably approximated using the greedy algorithm. The proposed solution is interesting and practical as it requires limited-number of training data and no labels. The reviewers found the authors' response convincing, however the authors are strongly encouraged to incorporate the clarifications provided in the rebuttal into the final version.
confidence: Certain
Decision: Accept