On the Decision Boundaries of Deep Neural Networks: A Tropical Geometry Perspective
Authors: Motasem Alfarra
Adel Bibi
Hasan Hammoud
Mohamed Gaafar
Bernard Ghanem
Venue:  (2020)
Keywords: Decision boundaries
Neural Network
Tropical Geometry
Network Pruning
Adversarial Attacks
Lottery Ticket Hypothesis

Abstract: This work tackles the problem of characterizing and understanding the decision boundaries of neural networks with piece-wise linear non-linearity activations. We use tropical geometry, a new development in the area of algebraic geometry, to provide a characterization of the decision boundaries of a simple neural network of the form (Affine, ReLU, Affine). Specifically, we show that the decision boundaries are a subset of a tropical hypersurface, which is intimately related to a polytope formed by the convex hull of two zonotopes. The generators of the zonotopes are precise functions of the neural network parameters. We utilize this geometric characterization to shed light and new perspective on three tasks. In doing so, we propose a new tropical perspective for the lottery ticket hypothesis, where we see the effect of different initializations on the tropical geometric representation of the decision boundaries. Also, we leverage this characterization as a new set of tropical regularizers, which  deal directly  with the decision boundaries of a network. We investigate the use of these regularizers  in neural network pruning (removing network parameters that do not contribute to the tropical geometric representation of the decision boundaries) and in generating adversarial input attacks (with input perturbations explicitly perturbing the decision boundaries geometry to change the network prediction of the input). 

Under review as a conference paper at ICLR 2020
ON THE DECISION BOUNDARIES OF DEEP NEURAL NETWORKS: A TROPICAL GEOMETRY PERSPECTIVE
Anonymous authors Paper under double-blind review
ABSTRACT
This work tackles the problem of characterizing and understanding the decision boundaries of neural networks with piecewise linear non-linearity activations. We tropical geometry, a development in the area of algebraic geometry, provide a characterization of the decision boundaries of a simple neural network of the form (Affine, ReLU, Affine). Specifically, show that the decision bound- aries are a subset of a tropical hypersurface, which is intimately related to poly- tope formed by the convex hull of two zonotopes. The generators of the zonotopes are precise functions of the neural network parameters. We utilize this geometric characterization to shed lights on new perspectives of three tasks. In doing so, we propose new tropical perspective for the lottery ticket hypothesis, where we see the effect of different initializations on the tropical geometric representation of the decision boundaries. Also, leverage this characterization as new set of trop- ical regularizers, which deal directly with the decision boundaries of a network. We investigate the use of these regularizers in neural network pruning (removing network parameters that do not contribute to the tropical geometric representation of the decision boundaries) and in generating adversarial input attacks (with input perturbations explicitly perturbing the decision boundaries geometry to change the network prediction of the input).
INTRODUCTION
Deep Neural Networks (DNNs) have demonstrated outstanding performance across several research domains, including computer vision (Krizhessky et al., 2012), speech recognition (Hinton et al.,
2015 Devlin et al. 2018). quantum chemistry 2012), natural language processing (Bahdanau al.)
Schhit et al.) 2017). and healthcare (Ardila et al. 2019 Zhou el al. 2019) to name a few (Le- Cun et a 2015). Nevertheless, rigorous interpretation of their success remains evasive (Shalev- Shwartz & DeviD (014).. For instance, and in an attempt to uncover the expressive power of DNNs, Montutar et al. (2014) studied the complexity of functions computable by DNNs that have piecewise linear activations. They derived a lower bound on the maximum number of linear regions. Several other works have followed to improve such estimates under certain assumptions (Arora et al. 2018). In addition, and in attempt understand some of the subtle behaviours DNNs exhibit, e.g. the sensitive reaction of DNNs to small input perturbations, several works directly investigated the decision boundaries induced by DNN used for classification. The work of SSyed- Mohsen Moosavi-Dezfoolii (2019) showed that the smoothness of these decision boundaries and their curvature play vital role in network robustness. Moreover, He et al. (201 8a) studied the expressiveness of these decision boundaries at perturbed inputs and showed that these boundaries do not resemble the boundaries around benign inputs. [i et al. (2018) showed that under certain assumptions, the decision boundaries of the last fully connected layer of DNNs will converge to a linear SVM. Also, Beise et al. (2018) showed that the decision regions of DNNs with width smaller than the input dimension are unbounded.
More recently, and due to the popularity of the piecewise linear ReLU as an activation function, there has been surge in the number of works that study this class of DNNs in particular. As result, this has incited significant interest in new mathematical tools that help analyze piecewise linear functions, such as tropical geometry. While tropical geometry has shown its potential in many applications such as dynamic programming (Joswig Schröter 2019). linear programming (Allamigeon et al. 2015), multi-objective discrete optimization (Joswig Loho (019), enumerative geometry (Mikhalkin 2004), economics (Akian et al. 2009
Mai Tran & Yu 2015). it has only been

---

Under review as a conference paper at ICLR 2020
recently used to analyze DNNs. For instance, Zhang et al. (2018) showed an equivalency between the family of DNNs with piecewise linear activations and integer weight matrices and the family of tropical rational maps. iee. ratio between two multi-variate polynomials in tropical algebra. The work of Zhang et al. (2018) was mostly concerned about characterizing the complexity of a DNN and specifically counting the number of linear regions, into which the function represented by the DNN can divide the input space, by counting the number of vertices of some polytope representation. This novel approach recovered the results of Montufar et al. (2014) with a much simpler analysis.
Contributions. In this paper, take the results of Zhang et al. 2018 some steps further and present novel perspective on the decision boundaries of DNNs using tropical geometry. To that end, our contributions are three-fold. (i) We derive a geometric representation (convex hull between two zonotopes) for super set to the decision boundaries of DNN in the form (Affine, ReLU, Affine). (ii) We demonstrate support for the lottery ticket hypothesis (Frankle & Carbin 2019) using a geometric perspective. (iii) We leverage the geometrical representation of the decision boundaries (the decision boundaries polytope) in two interesting applications: network purning and adversarial attacks. In regards to tropical pruning, we provide new geometric perspective in which can directly compress the decision boundaries polytope efficiently resulting in only minor perturbations to the decision boundaries. We conduct extensive experiments on AlexNet (Krizhevsky et al.) 2012) and VGG16 (Simonyan & Zisserman 2014) on SVHN (Netzer et al. 2011). CIFARTO, and CI- FAR 100 Krizhevsky & Hinton] 2009) datasets, in which 90% pruning rate can be achieved with marginal drop in testing accuracy. As for tropical adversarial attack, show that one con- struct input adversaries that can change network predictions by perturbing the decision boundaries polytope. We conduct extensive experiments MNIST (LeCun 1998).
PRELIMINARIES TO TROPICAL GEOMETRY
We provide here some preliminaries tropical geometry. For thorough detailed review, refer the reader to the work of Itenberg et al. (200)); Maclagan & Sturmfels (2015).
Definition 1. (Tropical Semiring The tropical semiring the triplet (-U(- 3, Ø), where ① and @ define tropical addition and tropical multiplication, respectively. They are denoted as:
x + y = max(x, y,,
x x = = +.
VT,YET.
can be readily shown that ooo is the additive identity and is the multiplicative identity.
Given the previous definition, a tropical power can be formulated as z = G O a.r, for x E T, a E N, where a.z is standard multiplication. Moreover, the tropical quotient can be defined as: x O y
y where y the standard subtraction. For ease of notation, write 00 as x². Now, we are a position to define tropical polynomials, their solution sets and tropical rationals.
Definition 2. (Tropical Polynomials) For E Td. q E and a; E Nd, a d-variable tropical polynomial with n monomials. f T + T can be expressed as:
f(x) = (c. @ x²x) + (c2
+ ... + (c, 2 )x a: *ai aj when i i j.
We use the more compact vector notation x" 201 222 x' where x, Rd. Moreover and for ease of notation, we will denote c, @ n as cxx" throughout the paper.
Definition 3. (Tropical Rational Functions) A tropical rational function a standard difference or aofonallfunctio
equivalently, tropical quolient of two tropical polynomials: f(x) - g(x) = f(x) S g(x).
Algebraic curves or hypersurfaces in algebraic geometry, which are the solution sets to polynomials, can be analogously extended to tropical polynomials too.
Definition 4. (Tropical Hypersurfaces) A tropical hypersurface of tropical polynomial f(x xi B Cn a is the set of points x where f is allained by two or more monomials in f, i.e.
T()) = EX xx =c,x f(x), for some a; J.
Tropical hypersurfaces divide the domain of f into convex regions, where f is linear in each region. Moreover, every tropical polynomial can be associated with a Newton polytope.
A semiring is ring that lacks additive inverse.
2

---

Under review as a conference paper at ICLR 2020
Definition 5. (Newton Polytopes) The Newton polytope of a tropical polynomial fx) c1x"1 + ① Xmn is the convex hull of the exponents a, E Nd regarded as points in R2, i.e.
( == (an E R : ......... n and Ci + -00}.
A tropical polynomial determines dual subdivision, which can thus be constructed by projecting the collection of upper faces (UF) in P(f)= == (a, Gs) E Rd x R =1. 1....,, n) to Rd. That is to say, the dual subdivision determined by f is given as 8(f) == (T(p) C C UF(P())) where π R2 x + IRdd is the projection that drops the last coordinate. It has been shown by Maclagan & Sturmfels (2015) that the tropical hypersurface T(f) is the (d-I)-skeleton of the polyhedral complex dual to (()). So, each vertex of 8()) corresponds to one region in IR where f is linear. Zhang et al. (208)) showed equivalency between tropical rational maps and any neural network / IR" theorem.
with piecewise linear activations and integer weights through the following
Theorem 1. (Tropical Characterization of Neural Networks, Zhang et al. (2018)). A feedforward neural network with integer weights and real biases with piecewise linear activation functions is function f : R² + IRt, whose coordinates are tropical rational functions of the input, i.e.,
f(x) Hx) @ Q(x) H [x) Q(x),
where and Q are tropical polynomials.
While this result is new in the context of tropical geometry, it is not surprising, since any piecewise
linear function can be represented as a difference of two max functions over a set of hyperplanes
Melzer (1986). Mathematically, that is say if f is a piecewise linear function, it can be written as [xx max {a. x} max (b} x), where [m] = (I,...,m)) m) and [^] = (I,..... .......)
Thus, it is clear that each of the two maxima above is tropical polynomial recovering Theorem 1
3 DECISION BOUNDARIES OF DEEP NEURAL NETWORKS AS POLYTOPES
In this section, we analyze the decision boundaries of a network in the form (Affine, ReLU, Affine) using tropical geometry. For case, we use ReLUs as the non-linear activation, but any other piecewise linear function can also be used. The functional form of this network is: f(x) Bmax (Ax + C1; 0) + C2, where max(-) is element operator. The outputs of the network are the logit scores. Throughout this section, we assume that A E gpxn, B E 22xp, Ci E IP and C2 E R22 For ease of notation, we only consider networks with two outputs, i.e. B2XP, where the extension to multi-class output follows naturally and it is discussed in the appendix. Now, since a piecewise linear function, each output can be expressed as tropical rational as per Theorem If fi and f2 refer to the first and second outputs respectively, we have fi (x) = Hi (x) O Qi (x) and fa(x) H2 (x) @ Qx(x), where H1, H2, QI and Q2 are tropical polynomials. In what follows and for ease of presentation, we present our main results where the network f has no biases, i.e. c1 = and C2- = O, and we leave the generalization to the appendix.
Theorem 2. For a bias-free neural network in the form of f'(x) :R" - R2 where A E pxn and B E 22Xp, let R(x)= (x) O Q2(x) + Hz(x) o Qi (1(x) be tropical polynomial. Then:
Let = [x ER" R [x(x) = [2()) defines the decision boundaries of J, then C T (R(x))).
ConvHull (2c.. Bc,). Zc. is a zonotope in IR." with line segments {B (L,J) + (2, + (i.:),A (1: and shift (8-(1.;) + B (2.:))A- Zg, is a zonotope in IR" with line segments {BB((, (1,j)++ttt BB (A.)))((++G.,,........)))))))))) A,),A-(jj.0) [), and shift (1,:) :) + B (2, A). Note that A+ = max(A, 0) and A max(- (ors(AA A, 0). The line seg- ment (B* (1. () + B (2, [A (G.:) A -j,:)) has end points A (j.:) and A A- (j,:) in R and
5 (R(x))
scaled by [ (1,1) + (2,)))
The proof for Theorem 2 is left for the appendix.
Digesting Theorem 2. Theorem can be broken into two major results. The first, which is on the algebra side, i.e. finding the solution set to tropical polynomials, states that the decision boundaries
Without loss of generality, one can very well approximate real weights fractions by multiplying by least common multiple of the denominators discussed in /Zhang al. (2018)
3

---

Under review as a conference paper at ICLR 2020
Tropical Geometric View to Decision Doundaries
(x 6x" (xx) f2(xi)
Hoden
2G,
2G,
1000 = Hilk0 Qujal
4
Asbt - Ralaa Quis
ZG2
Zui Ro. MDL18) Q
((N00) Q1000)
((D(x)) = ConvestHull 2r,, 2oy)
Figure I: Decision Boundaries as Geometric Structures. The decision boundaries B (in red) comprise two linear pieces separating classes C₁ and C2. As per Theorem 2 the dual subdivision of this single hidden neural network the convex hull between the zonotopes ZG, and 2G,- The normals to the dual subdivison d (Rx))) are in one-to-one correspondence to the trpical hypersurface Tf((x).. which is a superset to the decision houndaries B. Note that some of the normals 6 (Rxx) (in red) are parallel the decision boundaries.
B is a subset of the tropical hypersurface of the tropical polynomial R(x), i.e. T(R(x)). The second result, which is the geometry side, of Theorem relates the tropical polynomial R(x) to the geometric representation of the solution set to R(x), i.e. T(((x)), referred to as the dual subdivision, i.e. 8(R(x)). In particular, Theorem 2 states that the dual subdivision for network is the convex hull of two zonotopes denoted as Zo, and Zc, Note that this dual subdivision is a function of only the network parameters A and B.
Theorem 2 bridges the gap between the behaviour of the decision boundaries B, through the super-set T (R(x)), and the polytope 8 [[))), which is the convex hull of two zonotopes. It is worthwhile mention that Zhang al. (2018) discussed a special case of the first part of Theorem 2 for neural network with a single output and a score function sxx) to classify the output. To the best of our knowledge, this work is the first to propose tropical geometric formulation of a super-set containing the decision boundaries of a multi-class classification neural network. In particular, the first result of Theorem 2 states that one can alter the network, e-g. by pruning network parameters, while preserving the decision boundaries B, if one preserves the tropical hypersurface of R(x) or ((.(x)). While preserving the tropical hypersurfaces can be equally difficult to preserving the decision boundaries directly, the second result of Theorem 2 comes in handy. For bias free network, π becomes an identity mapping with 8 R(x)) A R())), and thus the dual subdivision 6(R(x)) which is the Newton polytope (R((x) in this case, becomes a well structured geometric object that can be exploited to preserve decision boundaries. Since Maclagan & Sturmfels (2015) (Proposition 3.1.6) showed that the tropical hypersurface is the skeleton of the dual to A [[[[)), the normal lines to the edges of the polytope 5( R()) are in one-to-one correspondence with the tropical hypersurface T..( Figure [ details this intimate relation between the decision boundaries, tropical hypersurface T (R(x)), and normals to 6 (R(x)). Before any further discussion, we recap the definition of zonotopes.
Definition 6. Let u
E R". The zonotope formed by u'....,u" u is defined as Z(u', ,..,, u²)= (E zqu 0 S 24 1). Equivalentty, the zonotope can be expressed with
u
respect to the generator matrix U E RRx*, where U(i.:) un" as Zu == (Uxx x Vx E [0, 1]P}.
Another common definition for zonotopes is the Minkowski sum (refer to appendix A for the def- inition of the Minkowski sum) of a set of line segments that start from the origin with end points u' u'...., u² E R". It is also well known that the number of vertices of a zonotope is polynomial in
the number of line segments. That is to say, |vert (2u) S 2 n-1 i= (P71) = O (p" Gritzmann
& Sturmfels 1993).
While Theorem 2 presents a strong relation between polytope (convex hull of two zonotopes) and the decision boundaries, it remains unclear how such a polytope can be efficiently constructed. Although the number of vertices zonotope is polynomial in the number of its generating line segments, fast algorithms for enumerating these vertices are still restricted to zonotopes with line segments starting at the origin (Stinson et al. 2016). Since the line segments generating the zono- topes in Theorem 2 have arbitrary end points, we present the next result that transforms these line segments into generator matrix of line segments starting from the origin, as prescribed in Definition 6 This result is essential for the efficient computation of the zonotopes in Theorem 2
Proposition 1. Consider line segments in R" with two arbitrary end points as follows [uf u The zonotope formed by these line segments is equivalent to the zonotope formed by the line segments ([uj- u²., 0)} with shift of Ep uly
4

---

Under review as a conference paper at ICLR 2020
Resso
lettery inttrbattion
sonder In Intidbation
I0.0 gasstion rnfisiaation. 10.21 guandan risstration
Figure 2:
Effect of Different Initializations on the Decision Boundaries Polytope. From left to right: training dataset, decision boundaries polytope of original network followed by the decision boundaries polytope during several iterations of pruning with different initializations.
The proof is left for the appendix. As per Proposition 2G, 2G, in Theorem can be defined as G Diag [ + (1.:) + (2: and G2 = Diag[ (B,(() (2,:)) + (B []: A, both with shift (B (1,:)
the generator matrices of zonotopes
B (2. (1,:)++++BB+
A-
In what follows, we show several applications for Theorem We begin by leveraging the geometric structure to help in reaffirming the behaviour of the lottery ticket hypothesis.
TROPICAL VIEW TO THE LOTTERY TICKET HYPOTHESIS
The lottery ticket hypothesis was recently proposed by Frankle & Carbin (2019), in which the thors surmise the existence of sparse trainable sub-networks of dense, randomly manddoly-initialzzedd initialized, feed- forward networks that-when trained in isolation-perforee perform as well as the original network in similar number of iterations. To find such sub-networks, [rannlee Carbin (2019) propose the fol- lowing simple algorithm: perform standard network pruning, initialize the pruned network with the same initialization that was used in the original training setting, and train with the same number of epochs. They hypothesize that this should result in a smaller network with similar accuracy to the larger dense network. In other words, subnetwork can have similar decision boundaries the original network. While in this section we do not provide a theoretical reason for why this proposed pruning algorithm performs favorably, we utilize the geometric structure that arises from Theorem to reaffirm such bchaviour. In particular, we show that the orientation of the decision boundaries polytope 5 (R(x)). known to be superset to the decision boundaries T(R (R(x))
[R( x)), is preserved after pruning with the proposed initialization algorithm Frankle & Carbin (2099). On the other hand, pruning routines with a different initialization at each pruning iteration will result in a severe vari- ation in the orientation of the decision boundaries polytope. This leads to a large change in the orientation of the decision boundaries, which tends to hinder accuracy.
To this end, we train a neural network with 2 inputs (n 2). 2 outputs, and a single hidden layer with 40 nodes (p- = 40). We then prune the network by removing the smallest 2% the weights. The pruned network is then trained using different initializations: (i) the same initialization as the original network (Frankle& & Carbin/ 2019), (ii) Xavier (Glorot & Bengio 2010), (iii) standard Gaus- sian and (iv) zero mean Gaussian with variance of 0.1. Figure 2 shows the evolution of the decision boundaries polytope, i.e. 8(R(x)), ) we perform more pruning (increasing the x%) with different initializations. It is to be observed that the orientation of the polytopes 5( R(x)) vary much more for all different initialization schemes as compared to the lottery ticket initialization. This gives an indi- cation that lottery ticket initialization indeed preserves the decision boundaries throughout the evo- lution of pruning. Another approach to investigate the lottery ticket could be by observing the poly- topes representing the functional form of the network directly, Le. 5(H (x)) and ((Q (x)). in licu of the decision boundaries polytopes. However, this does not provide conclusive answers to the lottery ticket, since there can exist multiple functional forms, and correspondingly multiple polytopes 5(H (x)) and (1Q(1.2) (x)). for networks with the same decision boundaries. This is why we explicitly focus our analysis on 8( (R(x)), which is directly related to the decision boundaries of the network. Further discussions and experiments are left for the appendix.
5 TROPICAL NETWORK PRUNING
Network pruning has been identified as an effective approach for reducing the computational cost and memory usage during network inference time. While pruning dates back to the work LeCun jet al, (1990) and Hassibi Stork 1993), it has recently gained more attention. This is due to the fact that most neural networks over- parameterize commonly used datasets. In network pruning, the task find a smaller subset of the network parameters, such that the resulting smaller network has sim- ilar decision boundaries (and thus supposedly similar accuracy) to the original oarr-parameterized network. In this section, we show a new geometric approach towards network pruning. In particu-
5

---

Under review as a conference paper at ICLR 2020
Hidden
Hiddnn
Input
Output
ZG
Zc:
Output
ZG:
ZGa
([(())) ConvesHall(aa, 2a,) 6(R())) Convexfflll 26,)
Figure 3: Tropical Pruning Pipeline. Pruning the 4thh node, or equivalently removing the two yellow vertices of zonolope EGg does not affect the decision boundaries polytope which will not lead to any change in accuracy.
lar, indicated by Theorem preserving the polytope 5( (R(x)) preserves a superset to the decision boundaries [R((x)), and thus supposedly the decision boundaries themselves.
Motivational Insight. For single hidden layer neural network, the dual subdivision to the decision boundaries the polytope that is the convex hull of two zonotopes, where each is formed by taking the Minkowski sum of line segments (Theorem 2 Figure 3 shows an example where pruning neuron in the neural network has no effect on the dual subdivision polytope and equivalently no effect on the accuracy, since the decision boundaries of both networks remain the same.
Problem Formulation. Given the motivational insight, natural question arises: Given over- parameterized binary neural network f(x) = B max (Ax, O), can one construct a new neural network, parameterized by some sparser weight matrices À and B, such that this smaller network has a dual subdivision 8 (((x)) that preserves the decision boundaries of the original network?
In order to address this question, we propose the following general optimization problem
min d ((((R(x)). = min dl ConvHull (Za, 2 ConvHull (Za,: (G.) A.B
(I)
A.B
The function d(-) defines a distance between two geometric objects. Since the generators G and G2 are functions of Á and B (as per Theorem 2). this optimization problem can be challenging to solve, However, for pruning purposes, one observe from Theorem 2 that if the generators G1 and G2 had fewer number of line segments (rows), this corresponds the weight matrix Á (sparser weights). To this end, we observe that if G G1 and G2 G2. then 5( (R(x)) x 8( (()())) and thus the decision boundaries tend to preserved as consequence. Therefore, we propose the following optimization problem as a surrogate to Problem ①
fewer number of rows in
min A.B (1G, - | + ||.
G2 A1
Ao G 2,1
(2)
The matrix mixed norm for C E gaak is defined as || Ei_ | 12, which encourages the matrix C to be row sparse, i.e. complete rows of C are zero. Note that G Reag +)RReUU( (22, A), G2 Diag [eeLU :))+ +eeU)----------e ReLU(-B(LLL B)] A, and Diag (v) rearranges the elements of vector v in a diagonal matrix. We solve the afforementioned problem with alternating optimization over the variables A and B, where each sub- sub-problem is solved in closed form. Details of the optimization and the extension multi-class case left for the appendix.
Extension to Deeper Networks. For deeper networks, one can still apply the aforementioned op- timization for consecutive blocks. In particular, prune each consecutive block of the form (Affine,Rel.,AAfinne) starting from the input and ending at the output of the network.
Experiments on Tropical Pruning. Here, we evaluate the performance of the proposed pruning approach compared several classical approaches on several architectures and datasets. In par- ticular, we compare our tropical pruning approach against Class Blind (CB), Class Uniform (CU) and Class Distribution (CD) Han et al. (2015); See al. (2016). In Class Blind, all the parameters across all nodes of a layer are sorted by magnitude where 2% with smallest magnitudes are pruned. Similar to Class Blind, Class Uniform prunes the parameters with smallest 3% magnitudes per node in layer as opposed to sorting all parameters in all nodes as Class Blind. Lastly, Class Distri- bution performs pruning of all parameters for each node in the layer, just as in Class Uniform, but the parameters are pruned based on the standard deviation de of the magnitude of the parameters per node, Since fully connected layers in deep neural networks tend to have much higher memory complexity than convolutional layers, restrict our focus to pruning fully connected layers. We

---

Under review as a conference paper at ICLR 2020
Alexhet on SVHN
Alexhltt on CIFAR10
AlexNet on CIFAR100
40
Accuracy 40
60
Accuracy
-30
60
CB AUC 0.837
40
--ACC 0.63
20
CB AUC 0.359
40
CU- AUC 0.852
CU- AUC 0.61
CU- AUC 0.34
CD AUC. 0.843
CD) -D-CUC 0.606
20
CD AUUC 0.338
20
Ours
AUC 0.668
Ours AUC
50
60
70
80
90
100
50
60
70
80
90
100
40 60
100
Pruning Rate %
Pruning Rate %
Pruning Rate %
VGG16 on SVHN
VGG16 on CIFAR10
VGG16 on CIFARIDO
60
80
Accursc
60
CB- AUC 0.893
Accurccy
60
CD --AUC- 0.074
Accuracy
40
CB AUC 0.994
40
AUC 0.852
AU-ACC- 0.875
20
AUC 0.866
CD AUC 0.881
CD-AUC- = 0.869
CD -UC = 0.899
20
0.88
20
Ours AUC 0.894
Ours AUC 0.922
50
70 80
90
100
60
70
80
9D
100
40 60
100
Pruning Rato
Pruning Rate
Pruning
Figure 4: Results of Tropical Pruning. Pruning-accuus accuracy plots for AlexNet (top) and VGGI6 (bottom)
trained on SVHN, CIFARIO, and CIFARI00, pruned with our tropical method and three other pruning methods.
train AlexNet and VGG16 on SVHN CIFAR10, and CIFAR 100 datasets. We observe that we can prune more than 90% of the classifier parameters for both networks without affecting the accuracy. Moreover, we can boost the pruning ratio using our method without affecting the accuracy by simply retraining the network biases only.
Setup. We adapt the architectures of AlexNet and VGG16, since they were originally trained on Ima- geNet (Deng et al. 2009), to account for the discrepancy in the input resolution. The fully connected layers of AlexNet and VGG16 have sizes of (256,512,10 10) and (512.512,10), respectively on SVHN and CIFAR 100 with the last layer replaced to 100 for CIFAR100. All networks were trained to baseline test accuracy of 109%,,4%%43%% for AlexNet on SVHN CIFARIO 10 and CIFAR 100, respec- tively and (92%.92 6..9%, %, 70%) for VGG16. To evaluate the performance of pruning, following previous works (Han et al.) 2015), we report the area under the curve (AUC) of the pruning-accuracy plot. The higher the AUC is, the better the trade-off is between pruning rate and accuracy. For efficiency purposes, we run the optimization in Problem 2 for single alternating iteration to identify the rows in A and elements of B that will be pruned, since an exact pruning solution might not be necessary. The algorithm and the parameters setup to solving 22 is left for the appendix.
Results. Figure 4 shows the pruning comparison between our tropical approach and the three afore- mentioned popular pruning schemes on both AlexNet and VGG16 over the different datasets. Our proposed approach can indeed prune out as much as 90% of the parameters of the classifier without sacrificing much of the accuracy. For AlexNet, compared to other methods. In particular, we are better in AUC by 3%, 3%, and 2% over other pruning methods on SVHN, CIFARIO 10 and CIFARI00, respectively. This indicates that the decision boundaries can indeed be preserved by preserving the dual subdivision polytope. For VGG16, we perform similarly well on both SVHN and CIFARIO and slightly worse on CIFARI00. While the performance achieved here is comparable to the other pruning schemes, if not better, we emphasize that our contribution does not lie in outperforming state-of-the-art pruning methods, but rather in giving a new geometry based perspective to network pruning. We conduct more experiments, where only the biases of the network or the biases of the classifier are fine tuned after pruning Retrain- ing biases can be sufficient they do not contribute to the orientation of the decision boundaries polytope, thereafter the decision boundaries, but only a translation. Discussion on biases and more results are left for the appendix.
achieve much better performance in pruning as
6 TROPICAL ADVERSARIAL ATTACKS
DNNs are notoriously known to be susceptible to adversarial attacks. In fact, adding small im- perceptible noise, referred to as adversarial attacks, at the input of these networks can hinder their performance. Several works investigated the decision boundaries of neural networks in the presence of adversarial attacks. For instance, Khoury & Madfield-Menel (2018) analyzed high dimensional geometry of adversarial examples by the means of manifold reconstruction. Also, He et al. (2018b) crafted adversarial attacks by estimating the distance to the decision boundaries using random search directions. In this work, we provide a tropical geometric view to this problem. where we show how Theorem 2 can be leveraged to construct tropical geometric based targeted adversarial attack.
7

---

Under review as a conference paper at ICLR 2020
Figure 5: Dual View of Tropical Adversarial Attacks. We show the effects of tropical adversarial attacks on synthetic binary datasel two different input points (in black). From left to right: the decision regions of the original and perturbed models, and decision boundaries polytopes (green for original blue for perturbed),
Dual View to Adversarial Attacks. For a classifier ff I" + R and input Xo that is classified as a standard formulation for targeted adversarial attacks flips the classifier prediction to particular class and it usually defined as follows
ming D(n) s.t. arg max, fx + 7) = #
(3)
This objective aims at computing the lowest energy input noise 1i (measured by D) such that the the new sample (Xo + 11) crosses the decision boundaries of f to a new classification region. Here, we present a dual view to adversarial attacks. Instead of designing a sample noise 1) such that (Xo + 7)) belongs new decision region, one can instead fix X and perturb the network parameters move the decision boundaries in a way that Xy appears in a new classification region. In particular, let A be the first linear layer of ʃ. such that f(xo) g( )x)). One can now perturb A to alter the decision boundaries and relate the perturbation to the input perturbation as follows
g((A1 +
= 9 (Aixo + xo) = g(Aixo + A17) = f(xo + +))
(4)
From this dual view, we observe that traditional adversarial attacks are intimately related to per- turbing the parameters of the first linear layer through the linear system: A = fA, Xo- To this end, Theorem provides explicit means to geometrically construct adversarial attacks by means of perturbing decision boundaries. In particular, since the normals to the dual subdivision polytope 5(R(x)) of given neural network represent the tropical hypersurface set T (((())) which is, as per Theorem 2, a superset to the decision boundaries set B, ÇA, can be designed to result in a minimal perturbation to the dual subdivision that sufficient to change the network prediction xg to the targeted class f. Based on this observation, we formulate the problem as follows
min g,Ea;
Di(n) + D2(EA))
s.t.
- -loss(o(A))) (A( + () < -1; -loss(g(A) + EA, (x,,) () S 11;
(5)
(xo + n) E (0, 1]", |1 S G1; IlEA, lloc S2 A17- - [A, Xo= = 0.
The loss is the standard cross-entropy loss. The first row of constraints ensures that the network prediction is the desired target class t when the input Xy is perturbed by y,, and equivalently by perturbing the first linear layer A₁ by EA, This is identical to fi proposed by Carlini & Wagner (0116). Moreover, the third and fourth constraints guarantee that the perturbed input is feasible and that the perturbation is bounded, respectively. The fifth constraint is to limit the maximum perturbation on the first linear layer, while the last constraint enforces the dual equivalence between input perturbation and parameter perturbation. The function D. captures the perturbation of the dual subdivision polytope upon perturbing the first linear layer by EA,- For single hidden layer neural network parameterized as (A1 + (A.) ) Rexa and B E 22xp for the 1st and 2nd layers respectively, D2 can capture the perturbations in each of the two zonotopes discussed Theorem
(6) The derivation, discussion, and extension of (6) to multi-class neural networks left for the ap- pendix. We solve Problem ( with a penalty method on the linear equality constraints, A = Xg. Co, where each penalty step is solved with ADMM (Boyd et al.) 2011) in a similar fashion the work Xu et al. (2018). The details of the algorithm are left for the appendix.
D2(EA,) = Σ D (G.)))
|| (B-aaBBB))))AA
Motivational Insight to the Dual View. This intuition is presented in Figure We train single hidden layer neural network where the size of the input is 2 with 50 hidden nodes and 2 outputs on simple dataset shown in Figure 5] We then solve Problem 5 for given Xo shown in black. We show the decision boundaries for the network with and without the perturbation at the first lin- ear layer ε Figure 5 shows that indeed perturbing an edge of the dual subdivision polytope, by perturbing the first linear layer, corresponds to perturbing the decision boundaries and results in miss-classifying Xo. Interestingly and as expected, perturbing different decision boundaries corre- sponds perturbing different edges of the dual subdivision. In particular, can see from Figure
8

---

Under review as a conference paper at ICLR 2020
Figure 6: Effect of Tropical Adversarial Attacks MNIST Dataset. We show qualitative examples of adversarial attacks, produced by solving Problem (5). on two digits (8.9) from MNIST. From left to right, images are classified as [8,7,5,4] and [9,7,5,4] respectively.
that altering the decision boundaries, by altering the dual subdivision polytope through perturbations the first linear layer, can result in miss-classifying previously correctly classified input Xo-
MNIST Experiment. Here, we design perturbations to misclassify MNIST images. Figure 7 shows several adversarial examples that change the network prediction for digits 8 and 4, respectively. In some cases, the perturbation 7j is as small as = 0.1, where Xo E [0, 1 Several other adversarial results are left for the appendix. We again emphasize that our approach is not meant to be compared with (or beat) state of the art adversarial attacks, but rather to provide a novel geometrically inspired perspective that can shed new light in this field.
digits 5, and
7 CONCLUSION
In this paper, we leverage tropical geometry to characterize the decision boundaries of neural net- works in the form (Affine, ReLU, Affine) and relate it to well-studied geometric objects such as zonotopes and polytopes. We leaverage this representation in providing tropical perspective to support the lottery ticket hypothesis, network pruning and designing adversarial attacks. One natu- ral extension for this work compact derivation for the characterization of the decision boundaries of convolutional neural networks (CNNs) and graphical convolutional networks (GCNs).
REFERENCES
Marianne Akian, Stphane Gaubert, and Alexander Guterman. Tropical polyhedra are equivalent to mean payoff games. International Journal of Algebra and Computation, 2009.
Xavier Allamigeon, Pascal Benchimol, Stphane Gaubert, and Michael Joswig. Tropicalizing the simplex algorithm. SIAM J. Discrete Math. 29:2, 2015.
Diego Ardila, Atilla P. Kiraly, Sujecth Bharadwaj. Bokyung Choi, Joshua Reicher, Lily Peng, Daniel Tse, Mozziyar Etemadi, Wenxing Ye, Greg Corrado, David P. Naidich, and Shravya Shetty. End-to-end lung cancer screening with three-dimensional deep learning on low-dose chest com- puted tomography. Nature Medicine, 2019.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference Learning Representations, 2018.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In International Conference on Learning Representations, 2015.
Hans-Peter Beise, Steve Dias Da Cruz, and Udo Schröder. On decision regions of narrow deep neural networks. arXiv preprint arXiv:/807.000 01 194, 2018.
Leonard Berrada, Andrew Zisserman, and Pawan Kumar. Trusting svm for piecewise linear cnns. arXiv preprint arXiv: 161 1002155, 2016.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. Distributed optimiza- tion and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine learning, 2011.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. CoRR, 2016.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Computer Vision and Patter Recognition Conference (CVPR), 2009.

---

Under review as a conference paper at ICLR 2020
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: (0Xiv:8810008800 2018.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In ICLR. OpenReview.net, 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of 13th International Conference Artificial Intelligence and Statis- tics, 2010.
Peter Gritzmann and Bernd Sturmfels. Minkowski addition polytopes: computational complexity and applications to gröbner bases. SIAM Journal on Discrete Mathematics, 1993.
Song Han, Jeff Pool, John Tran, and William J. Dally, Learning both weights and connections for efficient neural networks. CoRR, 2015.
Babak Hassibi and David G Stork. Second order derivatives for network pruning: Optimal brain surgeon. In Advances in neural information processing systems, 1993.
Warren He, Bo Li, and Dawn Song. Decision boundary analysis of adversarial examples. In Inter- national Conference on Learning Representations (ICLR), 2018 8aa
Warren He, Bo Li, and Dawn Song. Decision boundary analysis of adversarial exaerss In In- fernational Conference on Learning Representations, 2018b. URL https://openreviee:
G. Hinton, L. Deng, D. Yu, G. E. Dahl, A. Mohamed, N. Jaitly, A. Senior, Vanhoucke, P. Nguyen, T. N. Sainath, and B. Kingsbury. Deep neural networks for acoustic modeling in speech recogni- tion: The shared views of four research groups. IEEE Signal Processing Magazine, 2012.
Ilia Itenberg, Grigory Mikhalkin, and Eugenii Shustin. Tropical algebraic geometry. Springer Science & Business Media, 2009.
Michael Joswig and Georg Loho. Monomial tropical cones for multicriteria optimization. AIP Conference Proceedings, 2019.
Michael Joswig and Benjamin Schröter. The tropical geometry of shortest paths. arXiv preprint 100.00290...0082. 2019.
Mare Khoury and Dylan Hadfield-Menell On the geometry of adversarial examples. arXiv preprint 1rX1v:18/1.00055,, 2018.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, Citeseer, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. ImageNet classification with deep con- volutional neural networks. Advances in Neural Information Processing Systems (NeurIPS), 2012.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist// 1998.
Yann LeCun, John S Denker, and Sara Solla. Optimal brain damage. In Advances in neural information processing systems, 1990.
Yann LeCun, Y Bengio, and Geoffrey Hinton. Deep learning. Nature, 2015.
Yu Li, Peter Richtarik, Lizhong Ding, and Xin Gao. On the decision boundary of deep neural networks. arXiv preprint /08.05588 2018.
Qinghua Liu, Xinyue Shen, and Yuantao Gu. Linearized admm for nonconvex nonsmooth optimiza- tion with convergence analysis. IEEE Access, 2019.
D. Maclagan and Sturmfels. Introduction to Tropical Geometry. Graduate Studies in Mathemat- ics. American Mathematical Society, 2015.
Ngoc Mai Tran and Josephine Yu. Product-mix auctions and tropical geometry. Mathematics of Operations Research, 2015.
10

---

Under review as a conference paper at ICLR 2020
D Melzer. On the expressibility of piecewise-lineat continuous functions the difference of two piecewise-linear convex functions. Quasidiifereniial Calculus. Springer, 1986.
Grigory Mikhalkin. Enumerative tropical algebraic geometry r2. Journal of the American Math- ematical Society, 2004.
Guido Montufar, Razvan Pascanu, Kyunghyun Cho, and Y Bengio. On the number of linear regions of deep neural networks. Advances in Neural Information Processing Systems (NeurIPS), 2014.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning, Advances in Neural Information Processing Systems (NeurIPS), 2011.
Kristof Schütt, Farhad Arbabzadah, Stefan Chmicla, Klaus-Robert Müller, and Alexandre Tkatchenko. Quantum-chemical insights from deep tensor neural networks. Nature Commu- nications, 2017.
Abigail See, Minh-Thang Luong, and Christopher D. Manning. Compression of neural machine translation models via pruning. CoRR, 2016.
Jonathan Uesato Pascal Frossard Seyed-Mohsen GloosviiDezzoooi Alhussein Fawzi. Robustness via curvature regularization, and vice versa. CVPR, 2019.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory algo- rithms. Cambridge university press, 2014.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1556, 2014.
Kerrek Stinson, David F Gleich, and Paul G Constantine. A randomized algorithm for enumerating zonotope vertices. arXiv preprint 1602v: 0000006660 2016.
Kaidi Xu, Sijia Liu, Zhao, Pin- Yu Chen, Huan Zhang, Deniz Erdogmus, Yanzhi Wang, and Xue Lin. Structured adversarial attack: Towards general implementation and better interpretability. arXiv preprint arXiv:1808.0 01664, 2018.
L Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim. Tropical geometry of deep neural networks, In International Conference on Machine Learning, ICMI. 2018, 2018.
Jian Zhou, Christopher Y. Park, Chandra L. Theesfeld, Aaron Wong, Yuan Yuan, Claudia Scheckel, John Fak, Julien Funk, Kevin Yao, Yoko Tajima, Alan Packer, Robert Darelll, and Olga G. Troy- anskaya. Whole-genome deep-learning analysis identifies contribution of noncoding mutations to autism risk. Nature Genetics, 2019.

---

Under review as a conference paper at ICLR 2020
A PRELIMINARIES AND DEFINITIONS.
Fact P+Q = {p- + q, Vp Pand E Q} is the Minkowski sum between two sets and Q.
Fact 2. Let f be tropical polynomial and let N. Then
P( =P()).
Let both f and g be tropical polynomials, Then Fact
P(f -(f))))
(7)
Fact
P(f 2 g) = ConvexHull (VP
(8)
Note that V(P(f)) is the set of vertices of the polytope P(f).
12

---

Under review as a conference paper at ICLR 2020
B PROOF OF THEOREM 2
Theorem 3. For a bias-free neural network the form of f(x) IR" I2 where A zpx" and B E x2x0, and let R(x) = (x) @ (x @ H2(x) @ Qi Qx be tropical polynomial, then
If the decision boundaries of f given by the set B far RR fi(x) f2(x)), then we have B T (R(x)).
8 (R(x))
Convitull (ZG,, 2G²) where EG, is zonotope in R" with {(B(1,))* + (B(2))))(((.))) Ai.i)) 13=1} with shift
line
segments
(B(1,:) + B(2 while ZG. is zonotope in IR" with line segments {(B(1.)) +
, P;=13 with shift (B(1.))++B(2,) AA
Note that A+ max 0) and A max -A, 0) where the max(.) is element-wise, The line segment (B(1,j)+ + j) (AAG.)) ((,,) one that has the end points A(j,:) and A(..)) in Ie" and scaled by the constant B(1,)) B)
Proof. For the first part, recall from Theoren [ Ithat both S1 and f2 are tropical rationals and hence,
[x(x = (x) - Qx(x)
f2(x) = H2(x) - Q2(x)
Thus
B = {a R" fi(x) = f2(x)) = E Hx(x) - Q1(x) H2(x)) Q2(x)}
= =xx E R" Hi(x) + Q2(x) = H2(x) + Qi(x)}
= E LRRE Hi(x) @ Q2(x) = H2(x) @ Qi(x))
Recall that the tropical hypersurface is defined as the set of x where the maximum is attained by two or more monomials. Therefore, the tropical hypersurface of R(x) the set of x where maximum is attained by two or more monomials in (H₃ (x) @ Q2(x)), or attained by two or more monomials in (H2(x) Q1 (x)). or attained by monomials in both of them in the same time, which is the decision boundaries. Hence, we can rewrite that as
T(R(x)) ((Hi(x) O Q2(x)) U T(H2(() O (x)))) UB.
Therefore C. T (. For the second part of the Theorem, we first use the decomposi- tion proposed by Zhang et al. (2018); Berrada et al. (2016) to show that for a network f(x) B max (Ax, 0), it can be decomposed as tropical rational as follows
f(x) B - B-)
max A x, A x)
A
B + max x A x
+
B
A
B
x
Therefore, have that
H + Q2(x)= (B+(1,) + B (2.)) max A (1,:) + B B+. (2.:)) A=x,
(x(x) + Qx() = B (1,;) BB max(A*x,A x)
B (L,)) + B (2. Axx.
Therefore note that
8(R(x) = 66 (HL(())) o
ConvexHull
( Q1(x)))
(H2(6)
(()
ConvexHull
13

---

Under review as a conference paper at ICLR 2020
(2.5) max (A (.:)), (.:))) tropically is given as follows Hi = O/==1 XA (1:) @x (.)) (1,)0B (2J)
Now observe that H1(x) = E/=1
thus we have that
6(H1(x)))
( + 0x (a.) t... (2. (
)
(I.p +B (2.p) (8(xA) (mN) @x (ni)))
(B ConvexHull (A (1,;), A (1,:)) +...
+( B (L. (2. ConvexHull A (p. A (p.
The operator + indicates Minkowski sum between sets. Note that ConvexHull A + (i,:), A (i,:
)) is the convexhull between two points which is line segment in 2n with end points that are (A+(),;) A :) scaled with (+,, B i). of line segments which is is a zonotope. Moreover, note that Q2(x) (B (1,:) B B2(, x
(2, Observe that (xF) is a Minkowski sum
tropically is given follows Q2(x) - (d:) 0,008 (2.1)) Thus is easy to see that [Jj in TR" (which is is a Minkowski
(()2(x)) is the Minkowski sum of the points (L
standard sum) resulting point. Lastly, is easy to see that ((H (x)
sum between zonotope and a single point which corresponds to shifted zonotope. A similar
symmetric argument can be applied for the second part (
It is also worthy to mention that the extension to network with multi class output is trivial. In that case all of the analysis can be exactly applied studying the decision boundary between any two classes (i,j) where B = {x E 1R" fi(x)= = (x)} and the rest of the proof will be exactly the same.
14

---

Under review as a conference paper at ICLR 2020
C DERIVATION WITH BIASES
In this section, we derive the statement of Theorem 2 for the neural network in the form of (Affine, ReLU, Affine) with the consideration of non-zero biases. We show that the presence of biases does affect the obtained results they only increase the dimension of the space, where the polytopes live, without affecting their shape or edge-orientation. Starting with the first linear layer for IR", have
Ax - -A H1 & Q1
with coordinates
21, A (i,))x A (i,:) x= (c1, 2 x (B.1) O x (6.) H1, O QQ
Thus, 1 is a point in (n+1) dimensions at (A (i,:), CI, and AQQ).) point in (n 1) dimensions at (A (i,:), 0), while under ग projection, 1(H,,) is a point in n dimensions at (A (i, )) and ((Q1)) is point in dimensions at (A (i, It can be seen that under projection ı, the geometrical representation of the output of the first linear layer does not change after adding biases.
Looking to the output after adding the ReLU layer, we
Z: = max Z1, 0) = max( A 4 C1, A
A
H Q1)
Q1 H2 & Q2.
0)] and A(Q1,) ) is the point (A (i,: 0). Thus, o 2H2, is the line segment [[ (AA + (i.:)) (A (i,) and ((Q1.) is the point (A-(i,)) (i) Again, the biases does not affect the geometry of the output after the ReLU layer, since the line segments now connecting points in (n 1) dimensions, but after projecting them using they will be identical to the line segments of the network with zero biases.
Hence, (HH, ) is the line segment [(A (z. :), 1 (i.:).
Finally, looking to the output of the second linear layer, we obtain
Zy = Bzy + C2 = =B++ B (H2 - -22) c
= =BB*H +B +2) - B H. + B+Q2)
H3 & Q3
Therefore
A(Ha.)
Σ B Q2.))))())))
8(Hg,) = (,,(,
Σ B (1,j)Q((i.))
Similar arguments be given for a(Q).) and 5(Qs,) ). It can be that the first part in both expressions Minkowski sum of line segments, which will give a zonotope in (n + 1), and n dimensions in the first and second expressions respectively. While the second part in both expres- sions is Minkowski sum of bunch of points which gives a single point (n + 1) and n dimensions for the first and second expression respectively. Note that the last dimension of the aforementioned dimensions is exactly the 7th coordinate of the bias of the second linear layer which is dropped under the π projection. Therefore, the shape of the geometrical representation of the decision boundaries with non-zero biases will not be affected under the projection and hence the presence of the biases will not affect any of the results of the paper.
point in
15

---

Under review as a conference paper at ICLR 2020
D PROOF OF PROPOSITION
1
Proposition Consider line segments R with two arbitrary end points as follows Lui, ui] The zonotope formed by these line segments is equivalent to the zonotope formed be the line segments {[u} uz. 0}},=1 with shift of Σ, uz.
Proof. Let Uj be matrix with (; - I,..., P. be a column-vector with w(1) W; i . Minkowski sum of line segments with arbitrary end points be defined as
P and 1p is a column-vector of ones of length Then, the zonotope 2 formed by the
2
Σ 1m
wjui + (1 - my) we E 10, Vi]
Ujw U2w + U21p, we 00, 11)
(U, U2) w + U21p. w E 10, 112}
(U, U2) we 00 1J i U21p)
Note that the Minkowski sum of any polytope with a point is translation; thus, the result follows directly from Definition 6
16

---

Under review as a conference paper at ICLR 2020
D.1
OPTIMIZATION OF OBJECTIVE EQUATION 2 THE BINARY CLASSIFIER
min 1 A,B 2
G Gi F + G2 G2
2
+ G1 ||,1 2,1
+ X2
G2
(9)
2,1
Note that G Diag ReL.U(((1.)) + ReLU ((2, :)) A, G2 = Diag ReLL +
ReLU CALUU-BBA B(L,:)) A. Note that G1 Diag ReLU((((,:)) + ReLLU(-B(2.)) A and G2
Diag ReL. (B() :)) + ReLU(-B(1.:)) A. For ease of notation we refer ReLU :)) and ReLU(-B((L. as B (i.:) and B (i,:), respectively. We solve the problem with co-rodinate descent an alternate over variables.
Update A.
1 Diag(c2) A - G2/l + Aı (Piag(c))) )A 2 +
Á < arg min Diag (ci) A G1
+ A2 Diag(c2)
2,1
where 0₁ ReLLU(((1,)) + ReLU(-B((,:)) and C2 = ReI.U(((2,)) ReLU (B)(,))) Note that the problem separable per-row of A. Therefore, the problem reduces to updating rows Á independently and the problem exhibits closed form solution.
(i.:) arg min (i.:)
Ac.)) - (1 ccA(i,))) Ge(t.:) (AIV 2e ((t.))
A(i,;) ci.(i. + +c G2(,
A(t.))11
aargmin min A(i.:)
arg
[ct + c
[ct +cb)
1 + A2v/
Ci, + G2(.(.))) [c +
2
[c + c²))
Update B+,,,:).
Diag (1,:)) A c.l + A Diag (B, A + C2 2,1
B1,,1) = arg min B (1.:) 2
s.t. B+1,,)) 2
2,111
Note that C G Diag B (2.:) Á and where Diag B (2.:) Á. Note the problem is
separable in the coordinates of (1,;;) and a projected gradient descent can be used solve the problem in such way as
[+()))A(())) - Ci.) 1 + (+()))A(())) Ca0,))) s.t. B 2 0.
B (1,5) arg arg min B B+(j)) 2
A similar symmetric argument can be used to update the variables B (2,:), B (1,:) -- and B (2,;)).
17

---

Under review as a conference paper at ICLR 2020
D.2 ADAPTING OPTIMIZATION EQUATION FOR MULTI-CLASE CLASSIFIER
Note that Theorem 2 describes a superset to the decision boundaries of a binary classifier through the dual subdivision R(x), i.e. (x)())) For neural network with & classes, natural extension for is to analyze the pair-wise decision boundaries of of all k-classes. Thus, let T (x)( be the superset to the decision boundaries separating classes i and j. Therefore, natural extension to the geometric loss in equation I to preserve the polytopes among all pairwise follows
min E A, Y(t.jEs
d(ConveHHull (Za (Za 20 zayt.r)) ConvexHull (Zo Zg Boott-)))
(10)
The set S' is all possible pairwise combinations of the k classes such that S = [i. Vi + j, I,...,,.3 j.j = I....,kk. k}. The generator ((G().)) is the zonotope with the generator matrix G Diag (e), + RcLU(-B(j.:) Å. However, such an approach is generally computationally expensive, particularly, when k is very large. To this end, we make the following observation that G(it,j") can be equivalently written as Minkowski sum between two sets zono- topes with the generators ((t)) -Diag ReLUU((i..)) Å and Gj- Diag ReLLU Á. That is to say, 2c --,- Ze... 72G,- This follows from the associative property of Minkowski sums given as follows:
Fact 5. Let (5:) be the set of n line segments. Then we have that
S = ............ PVV
where the sets P = Sj and V Se where C1 and C2 are any complementary parti- tions of the set {Si]imi.
Hence, ((st.-) can seen a concatenation between G,it) and G(jT). Thus, the objective in 10 can be expanded as follows
min A. Vii.ilEs
Σ
d(ConvexHull (2a,13 , 2Gu ,) ConvexHull (Zo (Zo (c))..)))
min A, Viijees
Σ
d( (CCovexHull (za,+ F2a,_ 2a, =2..)) ConvexHull (Zo,t 2
s0 min A.B
Σ
Gz-
G++
G
G++
|
F
+
Gy+
G.-
G G
Viiies
min A.B
Σ
G.
G.
[
2
+
[.
1
G
-
G,
| + 2
1
G, -G,1 l|= + G, G, l|=
Y(ijEEs
min A.B
b Σ
2 (k - 1)
c - G. G.I
1/ || -G, G,
| G G, 1,,
+|+ ā. -G
12)
The approximation follows in a similar argument to the binary classifier case where approximating the generators. The last equality follows from a counting argument. We solve the objective for all multi-class networks in the experiments with alternating optimization binary classifier case. Similarly to the binary classification approach, we introduce the Illl,,1 to enforce sparsity constraints for pruning purposes. Therefore the overall objective has the form
similar fashion to the
min A.B
G.
G
+
G
G.
| + ر,و Gyi
||= F + ||G,, -G, 11:)
F
|
+
G
||
+ G|,
+
G, 2,1
l2a1
2,1
211
For completion, derive the updates for À and B.
18

---

Under review as a conference paper at ICLR 2020
Update Å.
Å arg min Σ ||Diag B ((,,)) À Gi+ |
Diag B (i.:) A Gi-
2
Diag (B (B+ A A
2 + Diag
B (i.:))
À Gj- l
^ (IDiae B (B (6,:)) A
Diag
[ (i.:)) Á
Diag (B+(i.)) A 1
2,1
2,1
Diag (B (i.)) A
2.11
Similar to the binary classification, the problem is seprable in the rows of A. and a closed form solution in terms of the proximal operator of &g norm follows naturally for each (t;;).
Update (i,:).
? + Diag Bi.:))) A
B (1, = arg min Diag (i.:))) A- A-G (+.)))
s.t. (+,,)) 0.
2,1
Note that the problem is separable per coordinates of B (i,:) and each subproblem is updated as:
B (i.)) = arg min (t,f)) 2
(+.j))AG. G. (i.
+ A (i.j) ||, s.t. B+ 20 0
2 (i.))) G.+ (i.)) || + A B(i.)) A(C 2. B+(i 20
argmin (t,)))
max 0, AG
G AIAAG.))1
A similar argument can be used to update B (i,:) Vi. Finally, the parameters of the pruned network will be constructed A <- Á and B < B B B
19

---

Under review as a conference paper at ICLR 2020
Algorithm 1: Solving Problem 5
Input : AA 1R B E Rkxp, Xo E R" 4 0, 1,K 0,Ex, =0pxn; 17¹ = 2²
w z²
u² w On
Output: 1), EA,
Initialize: Po
while not converged do
for k S K do
7) update: h+1 (2XA A1 (2 -0))) EX, xo + pm -
min xp. 61) :2 - 1/pv² > min(1 - xx: C1)
w update: w w
max Xo. -1] : - 1/pv8 < max -X0, -E1)
2 1/Dvk
oohhewise
update: 2+1 xpth +2p (1) +1 p(1) + 1/p1"* w + +//00+ - V VL((zt xx))
EA, update:
SA, arg minga [|E,, 11 + >1lEA, - A + E(A1) s.t. 1|EA, S 62
u update: =+* 1 + p(1)tt1 -z)
v update: vh+1 v² + p(whit1 z² 1))
p 7P
end
À + 7
P - Po
end
E ALGORITHM FOR SOLVING 5
In this section, going to derive algorithm for solving the following problem.
min
D1(1) + D2(EA.)
n-Ea
s.t.
loss(((A (xo + +)),, S -1, - EA,) 1) S -1, (xo+ + n) E [0, |0 Se,, 1,E,, Sez, A EA, = 0.
(1I)
The function D2(EA) captures the perturbdation in the dual subdivision polytope such that the dual subdivion the network with the first linear layer A similar to the dual subdivion of the network with the first linear layer A₁ + EA,- This can be generally formulated as an ap- proximation to the following distance function d (ConvHull (G,) ConvHull (Za,, 2cz)).
where G. = Diag ReLU(B(1, :)) + (BLLU) :)] A (Ā EA.). G2 -Diag ReLU G Diag ReLU(B(1,)) + ReLUR (eLL(()B(2.)) Á and G2
)) + ReLU (BLUU-B(1,:)) A (A+
Diag (c2,)(((,:)) + ReLU(-B(L1, :)) Å. In particular, to approximate the function d, one can use a similar argument as in used in network pruning such that D2 approximates the generators of the zonotopes directly as follows
1
2 F
D2(EA,)
G
G
+
G2 G2
2
2
F
1
2
2
Diag
B B+(,,)) EA,
+
Diag B (1, EA,
2
F 2
2
Diag B + (2,:)
EA,
+ Diag (2,:) EA.
This can thereafter be extended to multi-class network with classes follows D (EA,) ش Diag (++G EA, | + Diag B=.)):) EA, F Following Xu et al. 2018). we take D (n) 1 || Therefore, write 11 follows
20

---

Under review as a conference paper at ICLR 2020
2 + Diag B B (i. EA 12 r
Di(n) + Σ Diag (+. EA
min
ne
5=1
s.t.
-loss(g(A1()) 7)), s -1, [0, I S c1 1o, E2. A Xo, = 0.
-loss(g((A) + EA, )xx),, t) - -1,
To enforce the linear equality constraints E,, = O, we use penalty method, where each iteration of the penalty method solve the sub-problem with ADMM updates. That is, we solve the following optimization problem with ADMM with increasing such that + co. For ease of notation, lets denote L(x0 + 11) -loss(g(A) (A1 + n)), and L(A1) -loss(o((A) + (A,)xo))
) 11 + Σ Diag (el..U(((.:)) EA, 12 + ||Diag ReI.U(-B(j.))) Ex, l| ==1
min M.R,
+ [(xo z) + (w + ho(EA.) + A/AAm EA, xol12+ +CAI).
s.t.
= a 2 w.
where
0,
if (xp + n) E (0. ||7llx Sa
h2(EAi) =
0, if IKE,, lo0,00 S
(1)1) = co,
else
else
The augmented Lagrangian is thus given as follows
C(1, w, EA. v. = |17112 C(xo + z) + kw(w)
Diag(B DB.)(BB(G.))AA 1 +||Diag(B (DDiag(BTii)))ee (i.:))
+ C(A1) h2( A11A Eai xoll2 + +u
TuT(rz (1- 2) + +v-(w= -2) 2)
+ 2 ( (11 2. || -
Thereafter, ADMM updates are given as follows
w x+1 b+1
arg min C(n, w, 2 ck u² vt),
v.w
h+1 arg arg min L(1 wht k+l ck u vl),
2
s+1 min L(1 wkl ghtl EA, uº v*).
u k+1 n + p( bt1), xk+ v + p(wk+1 2t1l).
Updating yy:
n arg min |/ + A||Ain EA. xol13 +u++u UT n P 1ln 2|1
2
(22AT A, + + (22AT EA + u²) -²)
Updating w:
21

---

Under review as a conference paper at ICLR 2020
w arg min v
(1(w) + p || 2
vk
arg min w
2
+ h1 (w).
It is easy to show that the update w is separable in coordinates as follows
min(1 - x1, z - 3/00/ > min(1 - X0,
wh+
max -X0.
-E1)
z - 1/00t max(-X0- -1
z² 1/00
otherwise
Updating z:
zf k+ arg min L(xo + 2) n v
P 2 2 (11y 2112 + || zl(2)
Liu al. (2019) showed that the linearized ADMM converges for some non-convex problems. Therefore, by linearizing C and adding Bergman divergence term ""/2|zz 1 1 we can then update as follows
1 -u= + wh1 + -v)) V + xx))
b+1
2 + p(1
1 + 2p
It is worthy to mention that the analysis until this step is inspired by Xu et al. (2018 with modifica- tions to adapt our new formulation.
Updating EA:
c+1
arg min [A, 11 + AllEA, x
+ + s.t. 1EA,, S 62.
&A
The previous problem can be solved with proximal gradient method.
22

---

Under review as a conference paper at ICLR 2020
F EXPERIMENTAL DETAILS AND MORE RESULTS
In this section, we are going to describe the settings and the values of the hyper-parameters that we used in the experiments. Moreover, will show more results since have limited space in the main paper.
F.1 TROPICAL VIEW TO THE LOTTERY TICKET HYPOTHESIS.
We begin by throwing the following question. Why investigating the tropical geometrical perspec- five of the decision boundaries is more important than investigating the tropical geometrical repre- sentation of the functional form of the network ? In this section, we show one more experiment that differentiate between these two views. In the following, we can see that variations can happen to the tropical geometrical representation of the functional form (zonotopes in of single hidden layer neural network), but the shape of the polytope of the decision boundaries is still unchanged and con- sequently, the decision boundaries. For this purpose, we trained single hidden layer neural network on simple dataset like the one in Figure then we do several iteration pruning, and visualise at each iteration both the polytope of the decision boundaries and the zonotopes of the functional representation of the neural network. change the shape of the decision boundaries polytope and consequently the decision boundaries of the neural network.
be easily seen that changes the zonotopes may not
Decinioo Boundarise Polyiope
Zonstope
Zonotace 2
Zanolopa 3
Zonolopa
Figure 7: Changes in Functional Zonotopes and Decision Boundaries Polytope. First column: decision boundaries polytope, rest of the columns are the geometrical representation of the func- tional form of the network. Under different pruning iterations using class blind, spot the changes that affected the tropical geometric representation of the functional form of the network (zonotopes) while the shape of the decision boundaries polytope is unaffected.
And thus it can be clearly seen that our formulation, which is looking at the decision boundaries polytope more general, precise and indeed more meaningful.
Moreover, we conducted the same experiment explained the main paper of this section on another dataset have further demonstration the favour that the lottery ticket initialization has over other
23

---

Under review as a conference paper at ICLR 2020
Spare
lilter Intoraatoo
IR.EA1 gossion Indo kuttonn 15 geasdion Inttl patton
Figure 8: Effect of Different Initializations on the Decision Boundarics Polytope. From left to right: training dataset, decision boundaries polytope of original network followed by the decision boundaries polytope during several iterations of pruning with different initializations.
Oryas
lottery trattitration
10 3.0:1 geastion tnbibbttion
COnT Pareragg
Figure 9: Effect of Different Initializations on the Decision Boundaries Polytope. From left to right: training dataset, decision boundaries polytope of original network followed by the decision boundaries polytope during several itcrations of pruning with different initializations.
initialization when pruning and retraining the pruned model. It clear that the lottery initializations is the one that preserves the shape of the decision boundaries polytope the most.
F.2 TROPICAL PRUNING
In the tropical pruning, we have control on two hyper-parameteen only, namely the number of iter- ations and the regularizer coefficient À which controls the pruning rate. In all of the experiments, we ran the algorithm for iteration only and we increase starting from 0.02 linearly with factor of 0.01 to reach 100% pruning. It is also worthy to mention that the output of the algorithm will be new sparse matrices Á, B, but the new network parameters will be the elements in the original matrices A, B that have indices correspond to the indices of non-zero elements in A, B. By that, the algorithm removes the non-effective line segments that do not contribute to the decision bound- aries polytope, without changing the non-deleted segments. Above all, more results of pruning of AlexNet and VGG16 on various datasets are shown below.
AlexNet
AlexNet CIFARID
AlexNet CIFAR100
40
60
Accuracy %
60
Accuracy %
Accurase
60
CB AUC 0.808
40
AUC 0.672
20
CB AUC G.375
0.931
AUC 0.659
0.362
Our AUC 0.938
CD- AUC 0.823
20
Our AUC 0.706
AUC 0.655
10
Our AUC 0.388
CD AUC 0.362
20
50
60
70
6D
90
100
50
60
70
80
90
100
20
40
60
6D
100
Pruning Rate
Pruning Rate %
Pruning Rate %
VBG16 on SVHN
VG616 on CIFAR1D
80
80
Accurccy
Accuracy.
-60
CB AUC 0.918
CU AUC 0.852
40
CU AUC 0.914
40
CD AUC 0.852
CD. AUC 0.914
Our AUC 0.83
20
AUC 0.913
20
100
70
Pruning Rate %
Pruning Rate
Figure 10: Results of Tropical Pruning with Fine Tuning the Biases of the Classifier. Tropical pruning applied on AlexNet and VGG16 trained SVHN, CIFAR1O, CIFAR100 100 against different pruning methods with fine tuning the biases of the classifier only.
24

---

Under review as a conference paper at ICLR 2020
AlexNet on SVHN
AlexNet CIFAR10
AlexNet CIFAR100
80
60
Accurary 36
Arturacy
Accuracy
60
CB AUC 0.854
40
0
20
0.663
40
CD AUC 0.859
CD AUC 0.66
CD AUC 0.365
20
Our AUC 0.886
Our AUC 0.693
Our AUC 0.391
50
60
70
90
100
50
60
70
80
90
100
0
20
40
60
80
100
Pruning Rate
Pruning Rate %
Pruning Rate %
VGG16 on SVHN
VGG16 CIFAR10
80
80
Accuracy %
Accuracy
CB AUC 0.894
CB AUC 0.917
CU- AUC 0.882
40
CU-AUC 0.912
AUC 0.883
AUC 0.914
20
0.908
20
80
100
70 Pruning
100
Pruning
Figure 11: Results of Tropical Pruning with Fine Tuning the Biases of the Network. Tropical pruning applied on AlexNet and VGGI6 trained on SVHN, CIFARIO, CIFAR100 against different pruning methods with fine tuning the biases of the network.
Figure 12: Dual View of Tropical Adversarial Attacks. Effect of tropical adversarial attack on synthetic dataset with classes in two different scenarios for the black input point. From left to right: decision boundaries Original model, perturbed model and decision boundaries poly- topes(green for original model and blue for perturbed model).
F.3 TROPICAL ADVERSARIAL ATTACK
For the tropical adversarial attack, control five different hyper parameters which
The upper bound for the infinite norm of 8.
62 : The upper bound for the//-Iloc,.e ll the perturbation on the first linear layer.
À Regularizer enforce the equality between input perturbation and first layer perturbation
7) Bergman divergence constant.
p: ADMM constant.
For all of the experiments, {E2, 7, p} had the values {1, 10 2.5, 1} respectively. the value of was 0.1 when attacking the -fours- images, and 0.2 for the rest of the images. Finally, we show extra results of attacking the decision boundaries of synthetic data in IR and MNIST images by tropical adversarial attacks.
25

---

Under review as a conference paper at ICLR 2020
5
Figure 13: Effeet of Tropical Adversarial Attacks on MNIST Images. First row from the left: Clean image, perturbed images classified as [7,3,2,1,0] respectively. Second row from left: Clean image, perturbed images classified as [9,8.733,2] respectively. Third row from left: Clean image, perturbed images classified as [9,8,7,5,3] respectively. Fourth row from left: Clean image, perturbed images classified as [9,4,3,2,1] respectively. Fifth row from left: Clean image, perturbed images classified [8,4,3.2,1] respectively.
G REBUTTAL
G.1 REVIEWER
We thank R3 for the time spent reviewing the paper. It is though not clear the authors the main reason behind the initial score of weak reject as R3 seems to have very generic questions about our work but not a particular criticism of the novelty/contribution that can address in our rebuttal. We hope that the following response addresses and clarifies some key elements. Morcover, we want to bring to the attention of R3 that we have addressed the commenttlyoossagestions of all reviewers in the revised version and marked them in blue.
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? so, what is it? am trying to understand why the authors use this tool. The authors should be explicit in their motivation 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.
that the readers
clear about the contribution of
As discussed thoroughly in the introduction (last paragraph of page 1), tropical geometry is the younger twin algebraic geometry particular semiring defined in way to align with the study
26

---

Under review as a conference paper at ICLR 2020
of piecewise linear functions. The early definitions stated in the paper (1 to 5) are well known in the TG literature and were restated for the completion of this paper. While it true that the definitions can be represented with standard mathematical tools; however, this misses the fundamental powerful element TG promises. TG transforms algebraic problems of piecewise linear nature to a combina- toric problem on general polytopes. To that end, Zhang et. al. 2018 (to the best of our knowledge the only work at the intersection between TG and DNNs) rederived classical results (upper bound on the number of linear pieces of DNNs) in a much simpler analysis by counting vertices on polytopes. In this work, instead of studying the functional representation of piecewise linear DNNs, we study their decision boundaries using the lens of TG. To wit, the geometric characterization of the deci- sion boundaries of DNNs developed in Theorem 2 cannot be attained using standard mathematical tools. More specifically, Theorem 2 represented superset to the decision boundaries (the tropical hypersurface T (()()). with a geometric structure that is the convex hull between two zonotopes. While this by itself opens doors for a family of new geometrically motivated regualrizers for train- ing DNNs that are in direct correspondence with the behaviour of the decision boundaries, we do not dwell training beyond this point and leave that for future work. However, this new result allowed for re-affirmation to the lottery ticket hypothesis in a new fresh perspective. Moreover, we propose new optimization problems that are geometrically motivated (based on Theorem 2) for sev- eral classical problems, i.e. network pruning and adversarial attacks that were not possible before and have provided several new insights and directions. That is we show an intimate relation between network perturbations (through decision boundary polytope perturbations) and the construction of adversarial attacks (input perturbations).
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 ap- proach ..., i think Figure 5 should be Figure 4.
We have added the definition of the pruning methods of Han et al. (2015) in the revised version of the paper for completion, and corrected the typo in the Figure reference.
Q3: In the adversarial attack part, is the authors proposing 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 + 17) belongs to a new deci- sion region, one can instead fix x0 and perturb the network parameters to move the decision boundaries in a way that x0 appears in 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 really misleading.
As highlighted in the last sentence in section 6, we are not competing against other attacks, but we rather show how this new geometric view to the decision boundaries provided by the TG analysis in Theorem 2 can be leveraged for the construction of adversarial attacks. We want to emphasize to R3 that the polytope representing the decision boundaries (convex hull two zonotopes as per Theorem 2) is a function of the network parameters and not of the input space. Thus, it is not initially clear how one can frame the adversarial attacks problem in this new fresh tropical setting since adversarial attacks is the task of perturbing the input space as opposed to the parameters space of the network resulting in flip in the prediction. In the tropical adversarial attacks section, we show that the problem of designing an adversarial attack +1 that flips the network prediction is closely related to the problem of flipping the network prediction by perturbing the network parameters in the first layer A + CA, where both problems are related through linear system. That is to say, if one finds (A, that perturbs the geometric structure (convex hull between two zonotopes, i.c. decision boundaries) sufficiently enough to flip the network prediction, one can find equivalent pixel adversarial attack 7 by solving the linear system A₁ = (A, Xo that flips the prediction of the original unperturbed network (see the end of page 7). We thereafter propose Problem (5) incorporating the geometric information from Theorem where the linear system is accounted for in the constraints set. We propose an algorithm to solve the problem (a mix of penalty and ADMM) detailed in Algorithm in the appendix. The solution problem 5 by applying Algorithm results in the construction of adversarial attacks (1) that indeed flip the network prediction over all tested examples on the MNIST dataset.
27

---

Under review as a conference paper at ICLR 2020
G.2 REVIEWER
We thank R2 for the time spent reviewing the paper. We also thank R2 for acknowledg- ing our technical and theoretical contributions. Please note that we have addressed the com- mensstypox/suggesiions of all reviewers in the revised version and marked them in blue. Follows our response.
Q1: 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?
The two works referenced by R2 are not directly related to the body of our work. Below, we sum- marize both works and state how our work is vastly different from both. The authors of [1] show that under certain assumptions, the decision boundaries of the last fully connected layer converges to an SVM classifier. That is to say, the features learnt in deep neural networks are linearly separable with max margin type linear classifier. On the other hand, the authors of [2] showed that the deci- sion regions of neural networks with width smaller than the input dimension are unbounded. In our work, we use new type of analysis (tropical geometry) to represent the of decision boundaries B through its superset T(R(x), x)) that is the solution set to the tropical polynomial R(x). We then show that this solution set is related to geometric structure referred to the decision boundaries polytope (convex hull between two zonotopes), this is analogous to constructing newton polytopes for the solution sets to classical polynomials in algebraic geoemtry. The normals to the edges of this polytope are parallel to the superset of the decision boundaries (((())). That is to say, if one processes the polytope in an way that preserves the direction of the normals, the decision boundaries of the network are preserved. This is the base idea behind all later experiments. In general, this new representation presents a new fresh revisit to the lottery ticket hypothesis and an utterly new view to network pruning and adversarial attacks. We do believe this new representation be of benefit to other applications and can open doors for a family of new geometrically inspired network regularizers well.
Q2: Regarding the complexity of the decision boundaries of neural networks.
The only work at the intersection between TG and DNNs that we are aware of is the work of Zhang et. al. 2018. They re-derived a classical upper bound to the number of linear regions of feed forward neural networks with ReLU activations by counting vertices of polytopes (Theorem 6.3). The work was limited to the complexity (number of linear regions) of the functional representation of the network and not to the decision boundary.
Q3: The second part of Theorem 2 should be explained straightforwardly and clearly as it plays an important role in the subsequent results and applications.
We have added a "Digesting Theorem 2" paragraph in the revised version and rearranged the struc- ture a bit around Theorem 2.
Q4: Pruning convolutional layers.
Most of the parameters (memory complexity) are the in fully connected layers. For example, the convolutional part of VGG16 has 14,714,688 parameters, whereas the fully connected layers have 262,000,400 parameters in total which is 17 times larger. Similarly, the convolutional part of AlexNet has 3,747,20 ,,00 parameters while only the first fully connected layer has 37,752,832 param- eters [5]. However, efficiently extending the tropical pruning to convolutional layers a nontrivial interesting direction. Generally speaking, convolutional layers fit our framework naturally since a convolutional kernel can be represented with a structured topelitz/cireulant matrix. However, a question of efficiency still remains as one still needs to construct the underlying structured matrix representing the convolutional kernel. Thereafter, direction of interest the tropical formulation of the network pruning problem as function of the convolutional kernels surpassing the need for the construction of the dense representation of the kernel. We keep this for future work.
Q5: For the similarity measure.
Comparing the exact decision boundaries between two different architectures can be very difficult in the sense where decision boundaries for two-class output network ff are defined as {x e R² : fi (x) = f2()))- Another approach to compare decision boundaries, which is proposed by our work, by computing the distance between the the dual subdivision polytope (ō (o((())) of the tropical
28

---

Under review as a conference paper at ICLR 2020
polynomials R(xx) representing two different architectures. This is since the normals to the edges of the polytope (6(R(x))) are parallel to superset of the decision boundaries (see Figure 1). This is exactly the proposed objective (1) where d(.)) is distance function to compare the orientation between two general polytopes. Since finding good choice for d(.) generally difficult we instead approximate it by comparing the generators constructing the (Ó (((x))) in Euclidean distance for ease (objective (2)). Experimentally and following prior art in the pruning literature (Han et. al. 2015), to compare the effectiveness of the pruning scheme, we compare the test accuracies across architectures as a function of the pruning ratio. Regardless, the reviewer is right about that similar test accuracies does not imply similar decision boundaries but rather only an indication.
Q6: In adversarial examples generation, typically for 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.
The new approach definitely comparable to the cell-establisehd adversarial example generation setting. Let us explain. The new analysis provided by Theorem 2, allows to present the decision boundaries geometrically
convex hull between two zonotopes which is function of only the network parameters and not the input space. Thus, it not clear how one can frame the adversarial attacks problem in this new fresh tropical setting since adversarial attacks is the task of perturbing the input space as opposed to the parameters space of the network resulting in flip in the prediction. In the tropical adversarial attacks section, we show that the problem of designing an adversarial attack X, + n that flips the network prediction is closely related to the problem of flipping the network prediction by perturbing the network parameters in the first layer A + where both problems are related through linear system. That is to say. if one finds CA, (perturbations in the first linear layer) that perturbs the geometric structure (convex hull between two zonotopes, i.e. decision boundaries) sufficiently enough to flip the network prediction, one can find equivalent pixel adversarial attack y by solving the linear system A = CA, Xo that flips the prediction of the original unperturbed network (see the end of page 7). We incorporate this in an overall objective (5) where the linear system is incorporated as a constraint. Upon solving (5) with the proposed Algorithm 1, we attack Therefore, this is comparable to
the original network (unperturbed) with the adversarial attack the classical adversarial attacks framework. This approach indeed resulted into flipping the network prediction over all tested examples on the MNIST dataset. As highlighted at the end of section 6, do not aim in our approach to outperform the state of the art adversarial attacks, but rather to provide a novel geometrically inspired perspective that can shed new light in this field.
Q7: 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.
The work of [3] analyzed the geometry of adversarial examples by means of manifold reconstruc- tion to study the trade off between robustness under different norms. On the other hand, [4] crafted adversarial attacks by estimating the distance to the decision boundaries using random search direc- tions. Both of the papers made a local estimation of the decision boundary around the attacked point to construct the adversarial attack to the input image. In our work, we geometrically characterized the decision boundaries in Theorem where the polytope (convex hull of two zonotopes) is only a function of the network parameters and NOT the input space. We presented a dual view to adver- sarial attacks in which one can construct adversarial examples by investigating network parameters perturbations that results in the largest perturbation to this polytope representing the decision bound- aries. The scope of our work, and unlike prior art [3,4], is focused towards new geometric polytope representation of the decision boundary in the network parameter space (not the input space) through a new novel analysis. We have added a discussion of both papers in the adversarial attacks section (Section 6).
Minor comments.
We have addressed the concerns of R2 and left the changes in blue in the revised version.
[1] "On the decision boundary of deep neural networks". SLi, Yu and Richtarik, Peter and Ding, Lizhong and Gao, Xin.
29

---

Under review as a conference paper at ICLR 2020
[2] "On decision regions of narrow deep neural networks". Beise, Hans-Peter and Da Cruz, Steve Dias and Schröder, Udo.
[3] "On the geometry of adversarial examples". Mare Khoury and and Dylan Hadfield-Menell.
[4] "Decision Boundary Analysis of Adversarial Examples". Warren He, Bo Li and Dawn Song.
[5] "Learning both weights and connections for efficient neural networks". Song Han, Jeff Pool,
John Tran, and William J. Dally.
G.3 REVIEWER
We thank R1 for the constructive detailed thorough review of the paper and for acknowledging our contributions and the new insights. Follows our response Rl's concerns.
In regards to clarity, exposition and focus.
To improve the clarity and exposition, we have added several paragraphs in the revised version of the paper. The revised edits are marked in blue. As in regards to the focus, we found that it is challenging within reasonable time to carry out this major change in the paper. To that end, we have done our best further elaborate on several key results in the paper. For instance, we have merged the paragraph above the contributions with the contributions paragraph. We have added another paragraph dissecting Theorem We have added some few relevant references that essential for the context of motivating tropical adversarial attacks.
In regards to the suggestions.
Adding the information that the semiring lacks the additive inverse.
This has been addressed in the revised version. Adding tropical quotient to definition 1.
This has been addressed in the revised version.
Definition of and the upper faces.
projection operator that drops the last coordinate. As for upper faces, the formal definition is given as follows, for a polytope P. F an upper face of P if x + te & P for any E F,t > 0 where is canonical vector. That is the faces that can be seen from "above". A good graphical example can be found Figure 2 from Zhang et. 2018 We dropped this definition from the paper as it may add some confusion while it does not play an important role in the later analysis.
Indeed,
Theorem 2 lacks intuitive formulation.
This has been addressed in the revised version and we have rearranged the structure of text below Theorem 2.
Regarding the issue of the tropical hypersurface.
Indeed, the superset is in terms of set theory. That is say, the set of decision boundaries B is supset of the tropical hypersurface set T(R(x)).
Regarding Figure 2.
The color map represents the compression percentage. We have added legend Figure Note that the second figure in Figure 2 tilted "original polytope" represents the polytope of the dual subdivision (convex hull between two zonotopes). While the polytope seems have only 4 vertices, there are in fact many other overlapping vertices and thereafter many small edges between all the seemingly overlapping vertices. It is to observe that the normals only the 4 major edges in the "original polytope" are indeed parallel to the decision boundaries plotted by performing forward passes through the network in the first figure titled "Input Space". Note that despite the fact that more compression performed, the orientation of the overall polytope is preserved for the lottery ticket initialization and thereafter preserving the main orientation of the decision boundaries. This unlike the the other types of initialization where the orientation of the polytope is vastly different with different compression ratios resulting into a larger change in the orientation of the decision boundaries.
30

---

Under review as a conference paper at ICLR 2020
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).
subsets of the tropical hypersurfaces. However, it has been shown by Maclagan & Sturmfels (2013) (Propositon 3.1.6) that the tropical hypersurface T to any d variate tropical polynomial is the (d-I)-skeleton of the polyhedral complex dual to the dual subdi- vision 6(). This implies that the normals to the edges (faces in higher dimensions) are parallel the tropical hypersurface. If R1 is interested in learning more about this, an excellent starting point to build up this intuition is the work of Erwan Brugall and Kristin Shaw "A bit of tropical geometry". Please refer to section 2.2 "Dual subdivisions" pages 6 and 7.
Correct.
The decision boundaries
The discussion about the functional form.
We elaborate on this in section the appendix. Instead of investigating the decision boundaries polytope of the tropical polynomial representing the decision boundaries R(x), we analyze the 4 different tropical polynomials representing the 2 different classes. Recall each output function of the network is tropical rational of two tropical polynomials giving rise to 4 different polytopes. Figure 7 shows that the decision boundary polytope 6( [(x)) with the lottery ticket is hardly changed while pruning the network (first column in Figure 7). On the contrary. the zonotopes (dual subdivisions of the 4 different tropical polynomials) vary much more significantly (coloumns 2.3,4.5). This demonstrates that there can exist different tropical polynomials representing the functional form of the network (i.e. H1,2 2 and 11,2) while having the same structure for the decision boundary polytope the corresponding first figure in the same row of Figure 7. This is a mere observation and worth investigating in future work.
In Section how many experiments of the sort were performed? I find this a highly in- structive view so I would love to see more experiments of this sort. Do these claims hold over multiple repetitions and for (slightly) larger architectures well?
We already had one extra experiment (Figure 8) in the appendix for another data. We have also based on the suggestion of RI added two more experiments (Figure 9) on two other datasets. Note that extracting the decision boundaries polytope for larger architectures is much more difficult for two different reasons. First, for deeper networks beyond the structure Reline-Rel.-Affiiee the decision boundaries polytope is generic and longer enjoys the nice properties zonotopes exhibit. Enumerating their vertices rapidly turns to a computationally intractable problem. Secondly, one can perhaps visualize the polytope for networks with 3 dimensional input but it gets trickier beyond that.
Regarding that the claim that orientations are preserved should be formalised.
That is an excellent question. We have investigated several metrics that try capture information about the orientation of a given polytope. For instance, we have investigated the feature that is the histogram of the oriented normals. That is a histogram of angles for all the normals to edges given polytope. We have also investigated the Hausdorff distance as a metric between polytopes. However, we have decided to keep this for future direction as this is by itself entirely new line of work. That is designing the distance functions d(.) between polytopes that captures orientation information that can be used for tropical pruning (objective 8) or perhaps other applications. Another interesting direction is whether such distance function can be learnt in meta-lcarning fashion. For now, we restrict the experiments to the approximation used in objective (2) which for now only captures the distance between the sets of generators of the zonotopes in Eucledian sense.
Adding link to the definition of minkowski sum in the appendix.
This has been addressed in the revised version.
Description to other pruning methods.
This has been addressed in the revised version where we have added the definition to all pruning competitors.
About the plots in Figure 4.
31

---

Under review as a conference paper at ICLR 2020
In the experiments of Figure 4, there is no stochasticity. All base networks (AlexNet and VGG16) are trained before hand to achieve the state-of-art baseline results on the respective datasets (SVHN, CIFARIO and CIFAR 100). The networks are then fixed and several pruning schemes, including the tropical approach, are applied with varying level of pruning ratio. We do not re-train the networks after each pruning step. Thus there exists no source of randomness. However, this is still an excellent observation. This is since we conduct experiments in the appendix where after each pruning ratio we fine tune only the biases of the classifier (Figure 10) or we fine tune the biases the complete network (Figure 11). In such experiments, due to the fine tuning step, we will consider in the final version to report the results averaged over multiple runs.
In Section 6, I find the comment on normals generating a superset to the decision boundaries hard to understand.
Indeed, the wording of the sentence was sub optimal. The statement was to reassure what has been established in earlier sections that the normals to the decision boundary polytope 8 (((()) represent the tropical hypersurface set T( [[)(x)) which is a super set to the decision boundaries set as per Theorem 2. We have rephrased the sentence.
Take-away message regarding perturbing the decision boundaries.
The proposed approach of perturbing the decision boundaries a mere dual view for adversarial attacks. That is say, to flip network prediction for sample Xg. can either adversarially perturb the sample (add noise) to cross the decision boundary to a new classification region or one can perturb the decision boundaries to move closer to the sample Xo to appear as if it is in new classification region. Figure 5, demonstrates the later visually through perturbing the decision boundary polytope. One can observe that perturbing the correct edge in the polytope in Figure 5, corresponds to altering a specific decision boundary. Figure 5, indeed as correctly pointed out of RI, is a feasibility study showing that one can perturb decision boundary by perturbing the dual subdiviosn polytope. However, the real take away message that these two views (perturbing the input or the parameter space) are intimately related through linear system as discussed in the subsection titled "Dual View to Adversarial Attacks". We propose objective function (Problem 5) and an algorithm (Algorithm 1) to tackle this problem. The solution to problem (5) provides an INPUT perturbation that results in altering the network prediction. That is to say. the new framework allows for incorporating geometrically motivated objective function towards constructing classical adversarial attacks.
Regarding the future extension on CNNs and GCNs.
We are currently investigating efficient extension of the current results to convolutional layers. Note that while convolutional layers can be represented with large structured topelitz/circulant matrix, we are interested in extensions that allow for similar analysis but as function of the convolutional kernel surpassing the need to constructing convolutional matrix. The GCNs is definitely an exciting excellent future direction that we have not yet entertained.
Minor style issues, We have addressed all the style issues in the revised version.
32


Reviews:
[{"review_id": "rylL75J0FH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nOverall, 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. \nHowever, there are several caveats in this paper that need further clarification.\n\n1) 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?\n\n2)  The second part of Theorem 2 should be explained straightforwardly and clearly as it plays an important role in the subsequent results and applications. \n\n3) 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. \nFurthermore, 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. \n\n4) 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.  \n\n5) 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. \n\nMinor comments:\nIn the abstract, \"We utilize this geometric characterization to shed light and new perspective on three tasks\" --> unclear, needs to be revised.\n\nProposition 1, \"the zonotope formed be the line segments\" --> \"the zonotope formed by the line segments\"\n\nPage 7. Results. \"For VGG16, we perform similarly on both SVHN and CIFAR10 CIFAR100.\" --> \"For VGG16, we perform similarly on both SVHN and CIFAR10.\"\n\n\n\n\nReferences:\n[1] @article{li2018decision,\n  title={On the decision boundary of deep neural networks},\n  author={Li, Yu and Richtarik, Peter and Ding, Lizhong and Gao, Xin},\n  journal={arXiv preprint arXiv:1808.05385},\n  year={2018}\n}\n[2] @article{beise2018decision,\n  title={On decision regions of narrow deep neural networks},\n  author={Beise, Hans-Peter and Da Cruz, Steve Dias and Schr{\\\"o}der, Udo},\n  journal={arXiv preprint arXiv:1807.01194},\n  year={2018}\n}\n\n[3] @article{khoury2018geometry,\n  title={On the geometry of adversarial examples},\n  author={Khoury, Marc and Hadfield-Menell, Dylan},\n  journal={arXiv preprint arXiv:1811.00525},\n  year={2018}\n}\n\n[4] @inproceedings{\nhe2018decision,\ntitle={Decision Boundary Analysis of Adversarial Examples},\nauthor={Warren He and Bo Li and Dawn Song},\nbooktitle={International Conference on Learning Representations},\nyear={2018},\nurl={https://openreview.net/forum?id=BkpiPMbA-},\n}\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hyg__4H0KH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI have some questions:\n\nQ1: 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.\n\nQ2: 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. \n\nQ3: 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.\n\n\n\n===================================================================\nThanks the authors for the response. I still have two questions:\n\nQ1: 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]?\n\nQ2: 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. \nAlso, 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.\n\n[1] Rethinking the Value of Network Pruning. Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, Trevor Darrell. ICLR 2019.\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Hkg1J89ptH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Summary of the paper\n\nThis paper describes the decision boundaries of a certain class of\nneural networks (piecewise linear, non-linear activation functions)\nthrough the lens of tropical geometry.\nAn earlier result by Zhang et al. (2018) is extended to multi-class\nclassification problems (technically, only the result for a binary\nclassification is given in the main text, though).\n\nSimilar to this earlier work, the network is shown to be represented as\na tropical rational function. The dual subdivision of this function is\nshown to be represented as the convex hull of two zonotopes.\n\nThis characterisation is used to explain different phenomena of neural\nnetwork training, viz. the 'lottery ticket hypothesis', network\npruning, and adversarial attacks.\n\n2. Summary of the review\n\nThis is a highly interesting paper with a very relevant subject. I think\nthat the perspective of tropical geometry leads to valuable insights. My\nbackground is *not* in tropical geometry, so this paper required several\npasses to fully grasp.\n\nI like the novel insights that this paper creates; it is very interesting\nto observe known phenomena via tropical geometry. I appreciate the\nthorough description of all concepts in this paper. This is to some\nextent both 'boon and bane': on the one hand, the paper contains a lot\nof information and concepts that need to be understood; on the other\nhand, the experiments go *wide* but not *deep*. I suggest to accept the\npaper, but to fully endorse it, I would recommend to work on the\nfollowing issues:\n\n- Clarity & exposition: In some places, the paper could build intuition\n  for non-experts (such as myself) better. This is closely tied to the\n  second point.\n\n- Focus: I would maybe pick *one* or *two* of the experimental areas and\n  use the remaining space to explain all concepts in more detail, build\n  some intuition, and provide a more in-depth setup. Nothing has to\n  removed of course; it could still be put in the appendix.\n\nThis paper has the potential to be a very strong insightful contribution\nto to our community; the authors are to be commended!\n\n3. Detailed comments (clarity)\n\nThe paper describes its concepts well and has a high information\ndensity. At times, there is the risk that readers are provided with too\nmuch information in the main text, leaving the necessary intuition\nsomewhat lacking (unless they are already experts in the subject matter,\nin which case a lot of the information can be skipped).\n\nI realise that writing a paper based on methods that are not yet\nwell-established is no small feat; the authors are to be commended for\nthat!\n\nHere are some suggestions from someone with a background in differential\ntopology:\n\n- The introduction and contributions are somewhat repetitive; I would\n  suggest merging the 'Contributions.' paragraph with the one preceding\n  it\n\n- Even though it *should* be a well-known definition, I would briefly\n  explain that the semiring lacks an additive inverse\n\n- Add an explanation of the tropical quotient to Definition 1; I find\n  the current phrasing of Definition 3 to be confusing at first glance\n\n- What are *upper faces*? Faces with a specific coordinate fixed?\n\n- A definition of $\\pi$ is required. It is my understanding that $\\pi$\n  is a projection function that 'drops' the last coordinate. Is this\n  correct? If so, it should be briefly mentioned on p. 3; else, the\n  discussion about the bias-free case on p. 4 cannot be understood.\n\n- Theorem 2 lacks an 'intuitive' formulation; the results are stated in\n  a terse mathematical fashion, but it would be helpful (also in light\n  of the subsequent discussion) to briefly comment on their *meaning*.\n\n  For example, the first result could be restated as 'the decision\n  boundary is a subset of a tropical hypersurface of the polynomial\n  $R(x)$'.\n\n  The paragraph 'Theorem 2 bridges the gap...' could maybe also be moved\n  to _precede_ the theorem statement.\n\n- The paper refers to $\\mathcal{T}(R(x))$ as a super-set, but in my\n  understanding, it is a *level set* because Definition 4 uses an\n  equality, not an inequality. Am I misunderstanding this? One potential\n  misinterpretation of my part could be that superset refers to the fact\n  that $\\mathcal{B} \\subseteq \\mathcal{T}(R(x))$; so not a superset\n  in the sense of level set analysis, but rather a superset in terms of\n  set theory. If this is the case, maybe rephrase the sentence above to\n  something like 'boundaries $\\mathcal{B}$ through their superset\n  $\\mathcal{T}(R(x))$ according to the first statement of Theorem 2'.\n\n- What does the colour map in Figure 2 depict? The number of iterations?\n  Moreover, I find the polytope though to understand at first glance;\n  how is it related to the decision boundaries that are shown in the\n  leftmost figure?\n\n- I would suggest to place Figure 1 after stating Theorem 2, since it is\n  only referenced later on. Furthermore, the red structures are somewhat\n  confusing. According to Theorem 2, the decision boundary is a subset\n  of the hypersurface, right? What is the relation of the red structures\n  in the convex hull visualisation? The caption states that they are\n  normals, but as far as I can tell, this has not been formalised\n  anywhere in the paper (it is used later on, though).\n\n- To what extent is the existence of the functions described by Theorem 2\n  unique? On p. 5, in Section 4, the paper alludes to *not* using the\n  functional form of the network directly because it does not seem to be\n  unique. I would like this to be explained a in more details, as\n  I found the justification of why the dual subdivision is used quite\n  hard to follow.\n\n- In Section 4, how many experiments of the sort were performed? I find\n  this a highly instructive view so I would love to see more experiments\n  of this sort. Do these claims hold over multiple repetitions and for\n  (slightly) larger architectures as well?\n\n  Please also see my comments on Figure 2 above.\n\n- The claim that orientations are preserved should be formalised.\n  I immediately understand the intuition behind this concept, but\n  if possible, I would like a quantification of this. Might it be\n  possible to *measure* changes in orientation with respect to an\n  original polytope? If so, it should be possible to provide more\n  experiments about these effects and summarise them accordingly.\n  Maybe it would also be interesting to investigate whether other\n  initialisations can be compared in terms of their orientations?\n\n- In Section 5, I would give a brief link to the appendix for the\n  definition of a Minkowski sum.\n\n- Section 5 has (in contrast to the other sections) a lot of details\n  containing the experimental setup, but it is missing a description of\n  the competitor methods. Adding to what I wrote above, I feel that the\n  paper should rather pick *one* area in which experiments are\n  performed; the pruning (together with the lottery ticket hypothesis\n  explanation, which could be seen as a motivating example) strikes me\n  as a good candidate for this.\n\n  I really like this concept of tropical pruning, by the way---it is an\n  elegant, principled description!\n\n- The plots in Figure 4 should summarise multiple pruning runs, if\n  possible. Why not show a standard deviation as well? Given the\n  stochasticity of training, I would think this highly necessary.\n\n- In Section 6, I find the comment on normals generating a superset to\n  the decision boundaries hard to understand.\n\n-  The perspective of perturbing the network such that the decision\n   boundaries change is really interesting, but I am missing\n   a 'take-away message' or a discussion of the insights. Currently,\n   this section seems more like a feasibility study: it appears to be\n   possible to use the tropical description to find new parameters that\n   misclassify a given input. I would propose a discussion of the\n   implications of these findings. \n\n- Concerning future extensions of this work, are there some promising\n  results or directions for CNNs or GCNs? If so, it would strengthen\n  the conclusion if they were mentioned.\n\n4. Minor style issues\n\nThe paper is well-written. I found some minor style issues:\n\n- 'piece-wise' --> 'piecewise' (occur multiple times)\n- 'recently demonstrated' --> 'demonstrated'\n- 'Thereafter, tropical hypersurfaces divide' --> 'Tropical hypersurfaces divide'\n- 'If set $B$ --> 'Letting B'\n- I am not sure if I would call adversarial attacks a 'nuisance'; maybe rather a 'problem'?\n- Use '\\operatorname' or '\\mathrm' to typeset the loss in Eq. 5\n\n5. Update after rebuttal\n\nThe 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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