Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies neural networks from the perspective of tropical geometry and applies its theoretical results to develop a novel algorithm for the compression of neural networks with ReLU activations. The presented algorithm outperforms a previous tropical network compression algorithm in terms of the accuracy of the compressed network.
main_review: ### Strengths
1. The paper presents a mathematically solid analysis of neural networks (seen as tropical rational mappings), including a bound for the approximation error of the compressed network.
2. The presented algorithm seems to outperform a recent tropical baseline in terms of test accuracy of the pruned network.
3. Since the tropical viewpoint is a pretty new perspective on ReLU networks, the paper may inspire more interesting theoretical work in the area and may thus be of interest for theoretical researchers in the field.

### Weaknesses/Suggestions for Improvement
1. The CNNs used in the comparison in Figure 4 are quite old. It would be good to remove LeNet and have a more modern architecture, like a ResNet instead.
2. The paper neither mentions the computational and storage (memory) complexity nor the runtimes of the introduced algorithm. Having a comparison between the paper’s algorithm and the one from Smyrnis & Maragos would be beneficial.
3. Related to the previous point: All the networks used in the evaluation section are pretty small. Is it possible to run the algorithm on larger networks? Transformer networks contain only fully-connected layers, so it would be really interesting to apply the algorithm to them.
4. The paper states that the algorithm is only applicable to fully-connected layers, but it is tested on multiple CNN architectures in the experimental section. Are only nodes from the fully-connected layers pruned in the experiments? ThiNet is a filter pruning method, so I assume that at least some of the methods also prune the convolutional layers.
5. The paper should state in the abstract that the algorithms only apply to networks with only ReLU activations.
6. The last sentence of the abstract says: “We deduce that our methods (1) show an improvement over relevant tropical geometry techniques, (2) advance baseline pruning methods, and (3) have competitive performance against a modern pruning technique.” I agree with point (1): The proposed method seems to work better than the tropical one from Smyrnis & Maragos. Regarding (2): I cannot see how the method advances any baseline apart from the tropical one already mentioned in (1) - neither in terms of test accuracy nor in terms of speed. Regarding (3): The most “modern” pruning technique the authors compare to is ThiNet from 2017 which is clearly not state of the art by looking at Figure 3 of the pruning survey [1]. The statements in (2) or (3) should either be backed up by more concrete evidence or removed.
[1] What is the State of Neural Network Pruning? Blalock, Gonzalez Ortiz, Frankle, Guttag.

**Minor**

7. The captions to the tables should be self-explanatory. It is not clear from the captions that the figures in Table 1 and 3 are the test accuracies after pruning and that the figures in Table 2 are the left hand side of Proposition 5.

summary_of_the_review: The paper seems to be mathematically solid, but I see room for improvement in the experimental section. Since the experiments focus on small architectures, it is unclear to me whether the proposed algorithm can be used to compress larger networks. Since theoretical work has an important value on its own, the compression algorithm is not required to be of immediate practical interest. However, it should be made clear what the limitations of the presented method are. Judging from the presented experiments, the last sentence of the abstract may be overclaiming the experimental results. Nonetheless, the tropical geometry section seems intriguing and may be of interest to theorists.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: ***This is a educated guess review as the paper is outside my domain expertise.

This paper proposes a compression method using a framework based on geometrical zonotope reduction. The authors further analyze the error bounds of the proposed methods and compare its performance with modern pruning techniques. I think the main contribution of the work would be novelty of the proposed method.
main_review: Pros: The proposed method seems novel and has theoretical guarantees. 

Cons: 
- The paper is a bit hard to process for general audience in machine learning, and the topic of the work does not seem to align well with ICLR. it would be nice if the authors could explain why this work would be good match to this conference.
- The emprical study is only performed on small scale datasets (a.k.a., MNIST and Fashion-MNIST). To compare with more modern compression techniques, experiments on more large scale datasets (e.g., CIFAR-10/100, COCO, Imagenet, etc) would better demonstrate the superiority of the proposed method.
summary_of_the_review: As this work is outside my domain of expertise, this is only an educated guess type of review, and I am willing to hear how other reviewers' opinions. 

===Update after the authors' response===
The summary of the paper in the authors' response is very helpful for the reader to grasp the main message of this work. Still, I have decided to keep my score as a) the empirical contribution is a bit limited, and as mentioned by the authors, the experiments are mainly proof-of-concept; and b) though the theoretical contribution is novel, it still needs a bit more work to justify its significance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes to study neural network compression through the lens of zonotope reduction. They present approximation bounds for tropical polynomials based on Hausdorff distance and use this to motivate the development of two neural network compression methods. These methods are evaluated on the MNIST, Fashion-MNIST, CIFAR-10, and CIFAR-100 datasets.
main_review: Questions:
- Why do the bounds decrease as the percentage of remaining weights decreases? This is pointed out but not explained. This suggests that the bounds of Prop. 4 and 5 aren't very useful. We should expect that if we can use more weights, we can at least avoid making the error worse, but this is not borne out by the computations in Table 2.

- Why was Alfarra et al. (2020) not compared to experimentally? The empirical comparison seems highly relevant. A discussion and comparison of the techniques should also be included since this work is quite related.

- What is deepNN? This is in the plot captions 4c and 4d but is never explained.

Feedback:
- The experimental results on CIFAR datasets are not very convincing. Compression of networks such as AlexNet and VGG is of limited interest as such architectures have been out-of-date for years. It would be much better to evaluate on modern architectures such as ResNets, Vision Transformers, etc.

- On MNIST and Fashion-MNIST, ThiNet generally does better except on Fashion-MNIST for LeNet.

- For all experiments, the authors should clearly state the current SOTA method for pruning and include those results as well. While beating SOTA is not necessarily a requirement, it at least needs to be provided for comparison.

- Also, the supplementary material was not submitted separately but instead included in the main PDF. While I actually prefer this approach for convenience, I believe they are supposed to be submitted separately. Also, it would be better to include the code for reproducibility.

Positive feedback:
- The background on tropical geometry is well-explained.

- Theorem 2 has a very clean statement. Q: Do related statements exist in the literature?
summary_of_the_review: This paper has some interesting results (such as Theorem 2) and the techniques are interesting and seem well-motivated (although this paper is not the first to study tropical geometric neural compression). However, the bounds from Propositions 4 and 5 seem to be not practically useful, and the experimental results have limitations. Thus, I hesitate to recommend acceptance at this time. It would be great if the authors can provide clear responses to my questions above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, a novel method of structured pruning of neural networks using tropical geometry has been proposed. The core idea is to use the tools from tropical geometry to represent a neural network as tropical polynomials and then apply k-means clustering using some distance metrics that work on such representation. 

The paper contains background information on tropical geometry and related tools. Experiments have been performed on linear layers of a binary classification network trained on MNIST (3/5 and 4/9) and LeNet5 and VGG trained on MNIST and Fashion-MNIST. The proposed method is compared with $L1$ structured pruning, Smyrnis & Maragos (2020), and ThiNet (Luo et al., 2017). 
main_review: Strengths: 
1. This is a novel idea that has not been explored widely for structured network compression.
2. A proper introduction to tropical geometry and the related tool has been done for non-domain experts.
3. Illustrations are very helpful in understanding the method.

Weaknesses:
1. Comparison with non-tropical methods has not been performed.
2. Please report the wall clock time of finding a pruned network and inference time.
3. Without pseudo-code or code segment(s) for zonotope generators part, it is hard to reproduce the experiments. The paper will also be more accessible to non-domain experts if included. The experimental setup is very short and not enough to reproduce the results.
summary_of_the_review: I am leaning towards acceptance of the paper as it provides a very interesting and new idea. As I am not a domain expert in tropical geometry, I would wait for other expert reviewers to judge the theoretical part. If authors can provide pseudo-code or code segment that makes this paper more accessible for me leading to better understanding, then I am willing to change my score.
review_title: null

Meta-review: The submission introduces an algorithm for structured pruning of fully connected ReLU layers using ideas from tropical geometry. The paper begins with a very accessible overview of key concepts from tropical geometry, and shows how ReLU networks can be thought of as  tropical polynomials. It gives an efficient K-means-based algorithm for pruning units in a way that approximately minimizes the Hausdorff distance between certain polytopes. Experiments show that the method outperforms other methods based on tropical geometry and is competitive with SOTA methods from a few years ago.

I think the reviewers, authors and I all agree on the following points: tropical geometry is a mathematical topic not commonly used in our field and for which it is difficult to find expert reviewers (notice that most of the citations aren't from ML venues). The paper is well-written, and the authors have taken pains to present the required concepts in an accessible way. Nobody has raised any concerns about correctness. While this isn't the first pruning method that uses tropical geometry, the algorithm is novel and interesting. It's expensive, but not unreasonably so. The experiments are a proof-of-concept: they use small networks by today's standards, and the baselines aren't the current SOTA. 

The average scores are slightly below the usual cutoff. The reviewers are concerned about whether this method is useful, given that is based on different principles from current methods and can't quite compete with current SOTA. But my own sense is that this is a paper that we'd like to have at ICLR. It gives a clear, accessible introduction to tropical geometry and demonstrates its usefulness for practical deep learning. It demonstrates competitiveness with fairly strong baselines, which is all we should expect from methods that haven't benefited from years of hill-climbing on the same handful of ideas. I recommend acceptance.
Decision: Accept (Poster)