Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: This paper proposed a framework based on a mathematical tool of tropical geometry to characterize the decision boundary of neural networks. The analysis is applied to network pruning, lottery ticket hypothesis and adversarial attacks.

I have some questions:

Q1: What benefit does introducing tropical geometry brings in terms of theoretical analysis? Does using tropical geometry give us the theoretical results that traditional analysis can not give us? If so, what is it? I am trying to understand why the authors use this tool. The authors should be explicit in their motivation so that the readers are clear about the contribution of this paper. More specifically, from my perspective, tropical semiring, tropical polynomials and tropical rational functions all can be represented with the standard mathematical tools. Here they are just redefining several concepts.

Q2: In “Experiments on Tropical Pruning”, the authors mentioned “we compare our tropical pruning approach against Class Blind (CB), Class Uniform (CU), and Class Distribution (CD) methods Han et al. (2015)”. What is Class Blind, Class Uniform and Class Distribution? There seems to be an error here “Figure 5 shows the pruning comparison between our tropical approach ...”, i think Figure 5 should be Figure 4. 

Q3: In the adversarial attack part, is the authors proposing a new attack method? If so, then the authors should report the test accuracy under attack. Also, the experimental results should not be restricted to MNIST dataset. I am also not sure about the attack settings here, the authors said “Instead of designing a sample noise η such that (x0 + η) belongs to a new decision region, one can instead fix x0 and perturb the network parameters to move the decision boundaries in a way that x0 appears in a new classification region.”. Why use this setting? Are there any intuitions? Since this is different from traditional adversarial attack terminology, the authors should stop using adversarial attacks as in “tropical adversarial attacks” because it is really misleading.



===================================================================
Thanks the authors for the response. I still have two questions:

Q1: The authors say that this theory provides a deeper understanding to Lottery Ticket Hypothesis (LTH). Then another paper “Rethinking the Value of Network Pruning” [1] suggests something different than LTH. [1] suggests that we do not need the initialization of large networks to train the pruned network from scratch to achieve high accuracy. Since the authors claim that their theory is related to LTH, then what would the proposed theory say about [1]?

Q2: Since you redesign the task of adversarial attacks, I am still not convinced why this setting is interesting? The reason why people are interested in adversarial attacks is because it could happen during test time. What is the application of this setting? Why this new setting is important and worth studying? They are not clear to me. 
Also, as i wrote in my initial review, “the authors should stop using “adversarial attacks” as in “tropical adversarial attacks” because it is really misleading.”. I hope the authors can address this concern, or otherwise new readers may also find this part difficult to understand.

[1] Rethinking the Value of Network Pruning. Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, Trevor Darrell. ICLR 2019.


review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: This paper proposes a method to characterize the decision boundary of deep neural networks. The authors take advantage of a new perspective on deep neural network i.e., tropical geometry. They present and prove a theorem connecting the decision boundary of deep neural networks to tropical hyperspheres.  Then, they use the theoretical results of the theorem for two applications i.e., network pruning and adversarial examples generation.  For the former, they show that using the introduced decision boundary characterization using the tropical geometry, one can dimish the number of parameters in a model with insignificant loss in performance. For the latter, they introduce a new method for adversarial examples generation by altering the decision boundary. 

Overall, the technical and theoretical contribution of the paper regarding the relation of decision boundary to the tropical geometry is significant and could be useful for further investigation of the decision boundary of deep neural networks. 
However, there are several caveats in this paper that need further clarification.

1) This paper needs to be placed properly among several important missing references on the decision boundary of deep neural networks [1][2]. In particular, using introduced tropical geometry perspective, how we can obtain the complexity of the decision boundary of a deep neural network?

2)  The second part of Theorem 2 should be explained straightforwardly and clearly as it plays an important role in the subsequent results and applications. 

3) In the tropical network pruning section, the authors mention that "since fully connected layers in deep neural networks tend to have much higher memory complexity than convolutional layers, we restrict our focus to pruning fully connected layers". However, convolutional layers of investigated architectures (i.e., VGG16 and AlexNet) have a large number of parameters as well. So, wouldn't it be necessary to investigate pruning convolutional layers as well if diminishing the number of parameters is the main purpose? Moreover, the size of the last fully connected layer is simply determined by the preceding convolutional architecture, which in fact extracts the salient features (at least for well-known image datasets), while the last fully connected layer just flattens the extracted features to be fed into the subsequent classifier. Hence, it would be interesting and, in my opinion, necessary to investigate pruning convolutional layers as well. 
Furthermore, the authors mention that a pruned subnetwork has a similar decision boundary to the original network. What does it mean exactly by "similar"? What are the measures capturing this similarity, if any? Also, the authors imply that two networks performing similarly (in terms of the accuracy) on a particular dataset have similar decision boundaries. I am skeptical if this the case and it needs to be validated concretely. 

4) In adversarial examples generation, typically for a pre-trained deep neural network model one is interested in generating examples that are misclassified by the model while they resemble real instances. In this setting, we keep the model and thus its decision boundary intact. In this paper, nevertheless, aiming at generating adversarial examples, the decision boundary and thus the (pre-trained) model is altered. By chaining the decision boundary, however, the model's decisions for original real samples might change as well. Therefore, it is not clear to the reviewer how the introduced method is comparable to the well-established adversarial example generation setting.  

5) Two previous papers investigated the decision boundary of the deep neural networks in the presence of adversarial examples [3][4]. Please discuss how the introduced method in this paper is placed among these methods. 

Minor comments:
In the abstract, "We utilize this geometric characterization to shed light and new perspective on three tasks" --> unclear, needs to be revised.

Proposition 1, "the zonotope formed be the line segments" --> "the zonotope formed by the line segments"

Page 7. Results. "For VGG16, we perform similarly on both SVHN and CIFAR10 CIFAR100." --> "For VGG16, we perform similarly on both SVHN and CIFAR10."




References:
[1] @article{li2018decision,
  title={On the decision boundary of deep neural networks},
  author={Li, Yu and Richtarik, Peter and Ding, Lizhong and Gao, Xin},
  journal={arXiv preprint arXiv:1808.05385},
  year={2018}
}
[2] @article{beise2018decision,
  title={On decision regions of narrow deep neural networks},
  author={Beise, Hans-Peter and Da Cruz, Steve Dias and Schr{\"o}der, Udo},
  journal={arXiv preprint arXiv:1807.01194},
  year={2018}
}

[3] @article{khoury2018geometry,
  title={On the geometry of adversarial examples},
  author={Khoury, Marc and Hadfield-Menell, Dylan},
  journal={arXiv preprint arXiv:1811.00525},
  year={2018}
}

[4] @inproceedings{
he2018decision,
title={Decision Boundary Analysis of Adversarial Examples},
author={Warren He and Bo Li and Dawn Song},
booktitle={International Conference on Learning Representations},
year={2018},
url={https://openreview.net/forum?id=BkpiPMbA-},
}


review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: 1. Summary of the paper

This paper describes the decision boundaries of a certain class of
neural networks (piecewise linear, non-linear activation functions)
through the lens of tropical geometry.
An earlier result by Zhang et al. (2018) is extended to multi-class
classification problems (technically, only the result for a binary
classification is given in the main text, though).

Similar to this earlier work, the network is shown to be represented as
a tropical rational function. The dual subdivision of this function is
shown to be represented as the convex hull of two zonotopes.

This characterisation is used to explain different phenomena of neural
network training, viz. the 'lottery ticket hypothesis', network
pruning, and adversarial attacks.

2. Summary of the review

This is a highly interesting paper with a very relevant subject. I think
that the perspective of tropical geometry leads to valuable insights. My
background is *not* in tropical geometry, so this paper required several
passes to fully grasp.

I like the novel insights that this paper creates; it is very interesting
to observe known phenomena via tropical geometry. I appreciate the
thorough description of all concepts in this paper. This is to some
extent both 'boon and bane': on the one hand, the paper contains a lot
of information and concepts that need to be understood; on the other
hand, the experiments go *wide* but not *deep*. I suggest to accept the
paper, but to fully endorse it, I would recommend to work on the
following issues:

- Clarity & exposition: In some places, the paper could build intuition
  for non-experts (such as myself) better. This is closely tied to the
  second point.

- Focus: I would maybe pick *one* or *two* of the experimental areas and
  use the remaining space to explain all concepts in more detail, build
  some intuition, and provide a more in-depth setup. Nothing has to
  removed of course; it could still be put in the appendix.

This paper has the potential to be a very strong insightful contribution
to to our community; the authors are to be commended!

3. Detailed comments (clarity)

The paper describes its concepts well and has a high information
density. At times, there is the risk that readers are provided with too
much information in the main text, leaving the necessary intuition
somewhat lacking (unless they are already experts in the subject matter,
in which case a lot of the information can be skipped).

I realise that writing a paper based on methods that are not yet
well-established is no small feat; the authors are to be commended for
that!

Here are some suggestions from someone with a background in differential
topology:

- The introduction and contributions are somewhat repetitive; I would
  suggest merging the 'Contributions.' paragraph with the one preceding
  it

- Even though it *should* be a well-known definition, I would briefly
  explain that the semiring lacks an additive inverse

- Add an explanation of the tropical quotient to Definition 1; I find
  the current phrasing of Definition 3 to be confusing at first glance

- What are *upper faces*? Faces with a specific coordinate fixed?

- A definition of $\pi$ is required. It is my understanding that $\pi$
  is a projection function that 'drops' the last coordinate. Is this
  correct? If so, it should be briefly mentioned on p. 3; else, the
  discussion about the bias-free case on p. 4 cannot be understood.

- Theorem 2 lacks an 'intuitive' formulation; the results are stated in
  a terse mathematical fashion, but it would be helpful (also in light
  of the subsequent discussion) to briefly comment on their *meaning*.

  For example, the first result could be restated as 'the decision
  boundary is a subset of a tropical hypersurface of the polynomial
  $R(x)$'.

  The paragraph 'Theorem 2 bridges the gap...' could maybe also be moved
  to _precede_ the theorem statement.

- The paper refers to $\mathcal{T}(R(x))$ as a super-set, but in my
  understanding, it is a *level set* because Definition 4 uses an
  equality, not an inequality. Am I misunderstanding this? One potential
  misinterpretation of my part could be that superset refers to the fact
  that $\mathcal{B} \subseteq \mathcal{T}(R(x))$; so not a superset
  in the sense of level set analysis, but rather a superset in terms of
  set theory. If this is the case, maybe rephrase the sentence above to
  something like 'boundaries $\mathcal{B}$ through their superset
  $\mathcal{T}(R(x))$ according to the first statement of Theorem 2'.

- What does the colour map in Figure 2 depict? The number of iterations?
  Moreover, I find the polytope though to understand at first glance;
  how is it related to the decision boundaries that are shown in the
  leftmost figure?

- I would suggest to place Figure 1 after stating Theorem 2, since it is
  only referenced later on. Furthermore, the red structures are somewhat
  confusing. According to Theorem 2, the decision boundary is a subset
  of the hypersurface, right? What is the relation of the red structures
  in the convex hull visualisation? The caption states that they are
  normals, but as far as I can tell, this has not been formalised
  anywhere in the paper (it is used later on, though).

- To what extent is the existence of the functions described by Theorem 2
  unique? On p. 5, in Section 4, the paper alludes to *not* using the
  functional form of the network directly because it does not seem to be
  unique. I would like this to be explained a in more details, as
  I found the justification of why the dual subdivision is used quite
  hard to follow.

- In Section 4, how many experiments of the sort were performed? I find
  this a highly instructive view so I would love to see more experiments
  of this sort. Do these claims hold over multiple repetitions and for
  (slightly) larger architectures as well?

  Please also see my comments on Figure 2 above.

- The claim that orientations are preserved should be formalised.
  I immediately understand the intuition behind this concept, but
  if possible, I would like a quantification of this. Might it be
  possible to *measure* changes in orientation with respect to an
  original polytope? If so, it should be possible to provide more
  experiments about these effects and summarise them accordingly.
  Maybe it would also be interesting to investigate whether other
  initialisations can be compared in terms of their orientations?

- In Section 5, I would give a brief link to the appendix for the
  definition of a Minkowski sum.

- Section 5 has (in contrast to the other sections) a lot of details
  containing the experimental setup, but it is missing a description of
  the competitor methods. Adding to what I wrote above, I feel that the
  paper should rather pick *one* area in which experiments are
  performed; the pruning (together with the lottery ticket hypothesis
  explanation, which could be seen as a motivating example) strikes me
  as a good candidate for this.

  I really like this concept of tropical pruning, by the way---it is an
  elegant, principled description!

- The plots in Figure 4 should summarise multiple pruning runs, if
  possible. Why not show a standard deviation as well? Given the
  stochasticity of training, I would think this highly necessary.

- In Section 6, I find the comment on normals generating a superset to
  the decision boundaries hard to understand.

-  The perspective of perturbing the network such that the decision
   boundaries change is really interesting, but I am missing
   a 'take-away message' or a discussion of the insights. Currently,
   this section seems more like a feasibility study: it appears to be
   possible to use the tropical description to find new parameters that
   misclassify a given input. I would propose a discussion of the
   implications of these findings. 

- Concerning future extensions of this work, are there some promising
  results or directions for CNNs or GCNs? If so, it would strengthen
  the conclusion if they were mentioned.

4. Minor style issues

The paper is well-written. I found some minor style issues:

- 'piece-wise' --> 'piecewise' (occur multiple times)
- 'recently demonstrated' --> 'demonstrated'
- 'Thereafter, tropical hypersurfaces divide' --> 'Tropical hypersurfaces divide'
- 'If set $B$ --> 'Letting B'
- I am not sure if I would call adversarial attacks a 'nuisance'; maybe rather a 'problem'?
- Use '\operatorname' or '\mathrm' to typeset the loss in Eq. 5

5. Update after rebuttal

The authors addressed all my important comments; their efforts in rewriting and revising the paper in such a short time period are to be commended. I am very happy to raise my score.
review_title: Official Blind Review #1

Meta-review: This paper studies the decision boundaries of a certain class of
neural networks (piecewise linear, non-linear activation functions)
using tropical geometry, a subfield of algebraic geometry that leverages piece-wise linear structures. 
Building on earlier work, such piecewise linear networks are shown to be represented as
a tropical rational function. This characterisation is used to explain different phenomena of neural
network training, such as the 'lottery ticket hypothesis', network
pruning, and adversarial attacks.

This paper received mixed reviews, owing to its very specialized area. Whereas R1 championed the submission 
for its technical novelty, the other reviewers felt the current exposition is too inaccessible and some application areas are not properly addressed. The AC shares these concerns, recommends rejection and strongly encourages the authors to address the reviewers concerns in the next iteration. 

Decision: Reject