On the Decision Boundaries of Neural Networks. A Tropical Geometry Perspective
Authors: Motasem Alfarra
Adel Bibi
Hasan Abed Al Kader Hammoud
Mohamed Gaafar
Bernard Ghanem
Venue:  (2021)
Keywords: Tropical Geometry
Decision Boundaries
Neural Networks

Abstract: This work tackles the problem of characterizing and understanding the decision boundaries of neural networks with piecewise linear non-linearity activations. We use tropical geometry, a new development in the area of algebraic geometry, to characterize the decision boundaries of a simple network of the form (Affine, ReLU, Affine). Our main finding is 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 these zonotopes are functions of the network parameters. This geometric characterization provides new perspectives to three tasks. Specifically, we propose a new tropical perspective to the lottery ticket hypothesis, where we view the effect of different initializations on the tropical geometric representation of a network's decision boundaries. Moreover, we propose new tropical based optimization problems that directly influence the decision boundaries of the network for the tasks of network pruning (removing network parameters not contributing to the tropical geometric representation of the decision boundaries) and the generation of adversarial attacks.

Under review as a conference paper at ICLR 2021
ON THE DECISION BOUNDARIES OF NEURAL NET- WORKS. 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 non-lineare -on-iiicar activations. We use tropical geometry, new development in the area of algebraic geometry, characterize the decision boundaries of a simple network of the form (Affine, ReL.U, Affine). Our main finding is that the decision boundaries are subset of a tropical hypersurface, which is intimately related to a polytope formed by the convex hull of two zonotopes. The generators of these zonotopes are functions of the network parameters. This geometric characterization provides new perspectives to three tasks. (i) We propose a new tropical perspective to the lottery ticket hypothesis, where we view the effect of different initializations on the tropical geometric representation of a network's decision boundaries. (ii) Moreover, we propose new tropical based optimization reformulations that directly influence the decision boundaries of the network for the task of network pruning. (iii) At last, we briefly discuss the reformulation of the generation of adversarial attacks in a tropical sense, where we elaborate on this in detail in the supplementary material.'
INTRODUCTION
Deep Neural Networks (DNNs) have demonstrated outstanding performance across a variety of research domains, including computer vision (Krizhevsky et al., 2012), speech recognition (Hinton et al., 2012), natural language processing (Bahdanau et al., 2015; Devlin et al., 2018), quantum chemistry Schütt et al. (2017), and healthcare (Ardila et al., 2019; Zhou et al., 2019) to name a few (LeCun et al., 2015). Nevertheless, rigorous interpretation of their success remains elusive (Shalev- Shwartz & Ben-David, 2014). For instance, in an attempt to uncover the expressive power of DNNs, the work of Montufar et al. (2014) studied the complexity of funetions 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 to understand some of the subtle behaviours DNNs exhibit, e.g. the sensitive reaction DNNs to small input perturbations, several works directly investigated the decision boundaries induced by a DNN for classification. The work of Moosavi-Dezfoo (2019) showed that the smoothness of these decision boundaries and their curvature can play a vital role in network robustness. Moreover, the expressiveness of these decision boundaries at perturbed inputs was studied in He et al. (2018), where it was shown that these boundaries do not resemble the boundaries around benign inputs. The work of Li 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.
et al.
More recently, and due the popularity of the piecewise linear ReLU as activation function, there has been a surge in the number of works that study this class of DNNs in particular. As a 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, 2019), enumerative geometry (Mikhalkin, 2004), and economics (Akian et al., 2009; Mai Tran & Yu, 2015), it has only been recently used
CCode regenerating all our experiments is attached in the supplementary material.

---

Under review as a conference paper at ICLR 2021
to analyze DNNs. For instance, the work of Zhang et al. (2018) showed equivalency between the family of DNNs with piecewise linear activations and integer weight matrices and the family of tropical rational maps, i.e. ratio between two multi-variate polynomials in tropical algebra. This study was mostly concerned about characterizing the complexity of a DNN by counting the number of linear regions, into which the function represented by the DNN can divide the input space. This was done by counting the number of vertices of a polytope representation recovering the results of Montufar al. (2014) with simpler analysis. More recently, Smyrnis & Maragos (2019) leveraged this equivalency to propose heuristic for neural network minimization through approximating the tropical rational map.
Contributions. In this paper. we take the results of Zhang et al. (2018) several 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 a DNN in the form (Affine, ReLU, Affine). (ii) We demonstrate support for the lottery ticket hypothesis (Frankle & Carbin, 2019) from a geometric perspective. (iii) We leverage the geometric representation of the decision boundaries, referred to the decision boundaries polytope, in two interesting applications: network pruning and adversarial attacks. For tropical pruming, we design a geometrically inspired optimization to prune the parameters of a given network such that the decision boundaries polytope of the pruned network does not deviate too much from its original network counterpart. We conduct extensive experiments with AlexNet (Krizhevsky al., 2012) and VGG16 (Simonyan & Zisserman, 2014) on SVHN (Netzer et al., 2011), IF,RRO, and CIFAR 100 (Krizhevsky & Hinton, 2009) datasets, in which 90% pruning rate achieved with marginal drop in lesting accuracy. For tropical adversarial attacks, we show that one can construct input adversaries that can change network predictions by perturbing the decision boundaries polytope.
2 PRELIMINARIES TO TROPICAL GEOMETRY
For completeness, we first provide preliminaries to tropical geometry (Itenberg et al., 2009; Maclagan & Sturmfels, 2015).
Definition 1. (Tropical Semiring") The tropical semiring T is the triplet {R ( 0 }) where @ and @ define tropical addition and tropical multiplication, respectively. They are denoted as:
x ① y max yx,
3 B y: Vx, T.
It can be readily shown that co is the additive identity and 0 is the multiplicative identity.
Given the previous definition, tropical power can be formulated as x000 = x ② x ... ② x = a.v. for T, N, where is standard multiplication. Moreover, tropical quotient can be defined as: I tQy y = x - y. where I is standard subtraction. For ease of notation, we write I as x".
Definition 2. (Tropical Polynomials) For x E TV, & E R and a, E Nd, a d-variable tropical polynomial with nt monomials f T + T can be expressed as:
a, + aj when i i j. We use the more compact vector notation x 2 @ x. C x. Moreover and for ease of notation, will denote c; @ x c: throughout the paper.
f(x) = (a1 @ x²1 @ (Cg 3 x²2) @ ... ① (cn, ④ x""),
Definition 3. (Tropical Rational Functions) A tropical rational is standard difference or a tropical quotient of two tropical polynomials: f(x) gxx) ) = f(x) @ 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 a tropical polynomial f(x) Pm is the set of points x where f is attained by two or more monomials in f. i.e. c + ... 2 C,xx
T() = (x Rdd C; - f(x), for some a; + #aj).
Tropical hypersurfaces divide the domain of f into convex regions, where f is linear in each region. Also, every tropical polynomial can be associated with Newton polytope.
A semiring is ring that lacks an additive inverse.
2

---

Under review as a conference paper at ICLR 2021
20y00 [(
() (e0 0) (x- 1
f(x (e ( [1-1 2
TU:
Tu:
Figure Tropical Hypersurfaces and their Corresponding Dual Subdivisions. We show three tropical polynomials, where the solid red and black lines are the tropical hypersurfaces T(f) and dual subdivisions 6(f) to the corresponding tropical polynomials, respectively. T(f) divides The domain of f into convex regions where f is lincar. Morcover, each region is in one-to-one correspondence with each node of 5(f). Lastly, the tropical hypersurfaces are paralicl the normals of the edges of 8(f) shown by dashed red lines.
Definition 5. (Newton Polytopes) The Newton polytope of a tropical polynomial f(x) c1x" ① @ Cnx" is the convex hull of the exponents a, E N4 regarded as points in R i.e.
A(f) ComHuull(a E R i I...., and c, -20}.
A tropical polynomial determines dual subdivision, which can be constructed by projecting the collection of upper faces (UF) in P(f) := ConvHull( is to say, the dual subdivision determined by I' is given as 8( == [x(p) C Rd p UF(P())), where π IRd xR -> R2d the projection that drops the last coordinate. has been shown by Maclagan & Sturmfels (2015) that the tropical hypersurface T(f) is the (d- 1)--kklettton of the polyhedral complex dual to 8(f). This implics that each node of the dual subdivision 8(f) corresponds to one region in R where f is linear. This is exemplified in Figure 1 with three tropical polynomials, and to see this clearly, we will elaborate on the first tropical polynomial example f(r y) = x @ y tb 0. Note that as per Definition 4, the tropical hypersurface is the set of points (z, y) where
xR q.) E x i I..... n3 onto Rd That
y. y 0, and This indeed gives rise to the three solid red lines indicating the tropical hypersurfaces. As for the dual subdivision (.). we observe that @ y 0 can be written as (x²
0.
(z @ ) e (x g Thus, and since the monomials are bias free (c: = 0), then P(f) = ConvHull( (1. 0. 0), (0, 1, 0). (0.0. It is then easy to see that 8(f) ConvHull (1, 0), (0, 1). 0)). since UP(P(()) = P(f). which is the black triangle in solid lines in Figure 1. One key observation in all three examples in Figure is that the number of regions where f linear (that is 3, 6 and 10, respectively) is equal to the number of nodes in the corresponding dual subdivisions. Second, the tropical hypersurfaces are parallel to the normals to the edges of the dual subdivision polytope. This observation will be essential for the remaining part of the paper. Several other observations are summarized by Brugallé & Shaw (2014). Moreover, Zhang et al. (2018) showed an equivalency between tropical rational maps and a family of neural network R + RR with piecewise linear activations through the following theorem.
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 : E + R whose coordinates are tropical rational functions of the input, i.e. fxx = H(x) @ Q(x) = H(x) - Q(x), where H and Q are tropical polynomials.
While this new in the context of tropical geometry, not surprising, since any piecewise linear function can be written as difference of two max functions over a set of hyperplanes (Melzer, 1986).
Before any further discussion, we first recap the definition of zonotopes.
Definition 6. Let u² ...., - E R". The zonotope formed by u² u'...., u² is defined as Z(u' ......u)) = 1EE, D.u' : : S 2, S 1}. Equivalently, Z can be expressed with respect to the generator matrix U Rixa, where U(i,:) = =u Zu = x Vx e0,
u²)
Another common definition for a zonotope is the Minkowski sum of the set of line segments {ul ......,. 2 (refer to appendix), where line segment of the vector u' in R2" defined as (au' Va E [0, 1]]. It is well-known that the number of vertices of zonotope is polynomial in the number of line segments, iee. |vert (Zu) S E (1 O (I==1) (Gritzmann & Sturmfels, 1993).
3

---

Under review as a conference paper at ICLR 2021
Tropical Geometric View to Decision Doundaries
(x 6x" (xx) - f2(xi)
Hoden
2G,
2G,
1000 = Hilk0 Qujal)
4
Asbi - Ralaa Quin
ZG2
Zui Re. MDL18) Qx())))
((6(0) Q100))
(( ConvestBull 2r,, 2oy,)
Figure 2: Decision Boundaries as Geometric Structures. The decision boundaries B (in red) comprise two linear pieces separating classes C1 and C2. As per Theorem 2, the dual subdivision of this single hidden neural network the convex hull between the zonotopes 2c, and Za,. The normals to the dual subdivison d (((())) are in one-to-one correspondence to the tropical hypersurface T(H(x)), which a superset to the decision boundaries B. Note that some of the normals to 8( (R)x) (in red) are parallel to the decision boundaries.
3 DECISION BOUNDARIES OF 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 ease, 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 an element- wise operator. The outputs of the network f are the logit scores. Throughout this section, For ease of notation, we only consider networks with two outputs, i.e. B²xp, where the extension to multi-class output follows naturally and is discussed in the appendix. Now, since f' is a piecewise linear function, each output can be expressed as a tropical rational as per Theo- rem If fi and f2 refer to the first and second outputs respectively, we have (x) H1 (x) S Q (x) and f2(x)= = (x) S Q2(x), where H1, H2, Q1 and Q2 are tropical polynomials. In what follows and for ease of presentation, we present our main results where the network has no biases, i.e.
assume* that A E ZPxn B E Zdxp,
C E R" and C2 E
C1 = 0 and C2 = 0, and we leave the generalization to the appendix.
Theorem 2. For a bias-free neural network in the form f(x) IR. RR2, where A E Zpxa and B E Z2xp, let R(x)= (x) @ Q2(x) ① Hz(x) o Qi be a tropical polynomial. Then:
Let = {x E R" fi(x) = fx()) define the decision boundaries of f. then B T (R(x)).
8 (R(x))
ConvHull (Za,: Zo.). Zc, is zonotope in R" with line segments
((B+( + B (2.,))) A- (]::))} and shift (B + B++(2:)) where A+ max(A,0) 0) and A
max(-A,D0 O..). ZG. is a zonotope in R" with line segments (1,5) + B (2. (A))))) A -- (f,:))] and shift (B+(1;) + B (2.:)))
Digesting Theorem 2. This theorem aims at characterizing the decision boundaries (where fi(x) = f2(x)) of a bias-free neural network of the form (Affine, ReLU, Affine) through the lens of tropical geometry. In particular, the first result of Theorem 2 states that the tropical hypersurface T(R(x)) of the tropical polynomial R(x) a superset to the of points forming the decision boundaries. i.e. B. Just as discussed earlier and exemplified in Figure 1, tropical hypersurfaces are associated with a corresponding dual subdivision polytope 8(R(x)). Based on this, the second result of Theorem states that this dual subdivision is precisely the convex hull of two zonotopes denoted as ZG, and ZG2, where each zonotope is only a function of the network parameters A and B.
Theorem 2 bridges the gap between the behaviour of the decision boundaries B, through the superset T (R(x)), and the polytope (Rx)),, which is the convex hull of two zonotopes. It is worthwhile to mention that Zhang et al. (2018) discussed 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 a tropical geometric formulation of superset containing the decision boundaries of a multi-class classification neural network. In particular, the first result of Theorem 2 states that one can perhaps study the decision boundaries, B, directly by studying their superset T..(x)). While studying T(R(x)) can be equally difficult, the second result of Theorem 2 comes in handy. First, note that, since the network is bias-free, π becomes with (x)(x)) ((R()), and thus the dual subdivision ó (((())). which is the Newton polytope A(H(x) in this case, becomes a well-structured geometric object that can be exploited preserve
identity mapping
All proofs are left for the appendix.
Without loss of generality, one very well approximate real weights as fractions and multiply by the least common multiple of the denominators as discussed in Zhang et al. (2018).
4

---

Under review as a conference paper at ICLR 2021
Seace
lettery
PONDON Ioom
Figure 3: Effect of Different Initializations on the Decision Boundaries Polytope. From left to right: training datasct, decision boundaries polytope of original network (before pruning), followed by the decision boundaries polytope for networks pruned different pruning percentages using different initializations. Note that in the original polytope there are many more vertices than just 4, but they are very close to each other forming many small edges that are not visible in the figure.
decision boundaries as per the second part of Theorem 2. Now, based on the results of Maclagan & Sturmfels (2015) (Proposition 3.1.6) and as discussed in Figure I, the normals to the edges of the polytope R(x)) (convex hull of two zonotopes) are in one-to-one correspondence with the tropical hypersurface T (.(())). Therefore, one can study the decision boundaries, or at least their superset T(((x)). by studying the orientation of the dual subdivision 8{{(x)).
While Theorem 2 presents 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 of 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 al. (2016). Since the line segments generating the zonotopes 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 in Definition 6. This result is essential for an efficient computation of the zonotopes in Theorem 2.
Proposition 1.
The zonotope formed by p line segments R" with arbitrary end points {[ui, up Diz) equivalent the zonotope formed by the line segments {[u} - V with shift of E u2
We can now represent with the following corollary the arbitrary end point line segments forming the zonotopes Theorem with generator matrices, which allow us to leverage existing algorithms that enumerate zonotope vertices Stinson et al. (2016).
Corollary 1. The generators of ZG, Zg. in Theorem 2 can be defined as G1 =
Diag (B (1,:) ) + (B (2.:)) and G2 Diag((B (B=u)( (1,))),) both with shift
(B (1,:) + (2::)++ B+ B (2,:)) A- where Diag arranges v in a diagonal matrix.
Next, we show several applications for Theorem by leveraging the tropical geometric structure.
TROPICAL PERSPECTIVE TO THE LOTTERY TICKET HYPOTHESIS
The lottery ticket hypothesis was recently proposed by Frankle & Carbin (2019), in which the authors surmise the existence of sparse trainable networks of dense, randomly-initializee initializedd feed- forward networks that when trained isolation perform as well as the original network in a similar number of iterations. To find such sub-networks, Frankle & Carbin (2019) propose the following 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 results in smaller network with a similar accuracy. In other words, a sub-network can have decision boundaries similar to those of the original larger network. While we do not provide theoretical reason why this pruning algorithm performs favorably, we utilize the geometric structure that arises from Theorem
reaffirm such behaviour. In particular, we show that the orientation of the dual subdivision 8{ [(x)) (referred to as decision boundaries polytope),
where the normals to its edges are parallel to T (R(x)) that a superset to the decision boundaries, is preserved after pruning with the proposed initialization algorithm of Frankle & Carbin (2019). Conversely, pruning with a different initialization at each iteration results a significant variation in the orientation of the decision boundaries polytope and ultimately in reduced accuracy.
To this end, we train a neural network with 2 inputs (n = 2), 2 outputs, and a single hidden layer with 40 nodes = 40). We then prune the network by removing the smallest x% of 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 Gaussian, and
5

---

Under review as a conference paper at ICLR 2021
(iv) zero mean Gaussian with variance 0.1. Figure 3 shows the decision boundaries polytope, i.e. 5( ((R(x)), as we perform more pruning (increasing the x%% with different initializations. First, we show the decision boundaries by sampling and classifying points in grid with the trained network (first subfigure). We then plot the decision boundaries polytope 8 R())) as per the second part of Theorem 2 denoted as original polytope (second subfigure). While there are many overlapping vertices in the original polytope, the normals to some of the edges (the major visible edges) are parallel to the decision boundaries shown in the first subfigure of Figure We later show the decision boundaries polytope for the same network under different levels of pruning. One can observe that the orientation of ó (R(x)) for all different initialization schemes deviates much more from the original polytope compared to the lottery ticket initialization. This gives an indication that lottery ticket initialization indeed preserves the decision boundaries, since it preserves the orientation of the decision boundaries polytope throughout the evolution of pruning. An alternative means to study the lottery ticket could be to directly observe the polytopes representing the functional form of the network, i.e. ò ((H11,2) (x)) and (1,22 (x)), in lieu of the decision boundaries polytopes. However, this strategy may fail to provide a conclusive analysis of the lottery ticket, since there can exist multiple polytopes 5( 6(H(12) (1.2 (x)) and 5(Q (1.2) (x)) for networks with the same decision boundaries.
This highlights the importance of studying the decision boundaries directly. Additional discussions and experiments are left for the appendix.
TROPICAL NETWORK PRUNING
Network pruning has been identified as an effective approach to reduce the computational cost and memory usage during network inference. While it dates back to the work of LeCun et al. (1990) and Hassibi & Stork (1993), network pruning has recently gained more attention. This is due to the fact that most neural networks over- ver-parameterize commonly used datasets. In network pruning, the task is to find a smaller subset of the network parameters, such that the resulting smaller network has similar decision boundaries (and thus supposedly similar accuracy) to the original over-parameterized network. In this section, we show a new geometric approach towards network pruning. In particular and as indicated by Theorem 2. preserving the polytope 5 (([(x)) preserves a superset to the decision boundaries, T(((x)), and thus the decision boundaries themselves.
Motivational Insight. For single hidden layer neural network, the dual subdivision the decision boundaries is 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 shows an example, where pruning a neuron in the network has no effect on the dual subdivision polytope and hence no effect on performance. This occurs, since the tropical hypersurface T(R(x)) before and after pruning is preserved, thus, keeping the decision boundaries the same.
Problem Formulation. In light of the motivational insight, a natural question arises: Given an wver-paramelerized binary outpul neural nelwork f(x) = B max (Ax, 0), can one construct new neural network, parameterized by sparser weight matrices À and B. such that this smaller network has dual subdivision 8( [(x)) that preserves the decision boundaries of the original network?
To address this question, we propose the following optimization problem to compute Å and B:
min ((((((x))) 8(H(x)) = min d d(ConvHull A.B
Za,) ZZ,) ConvHull (Zc, Zo.)).
(1)
A,B
The function d(.) defines a distance between two geometric objects. Since the generators G and G2 are functions of A and (as per Theorem 2), this optimization problem can be challenging to solve. However, for pruning purposes, can observe from Theorem 2 that if the generators G2 and G2 had fewer number of line segments (rows), this corresponds to a fewer number of rows in the weight matrix À (sparser weights). So, observe that if G x G₁ and G2 v G2. then 8 ((()))) z 8( (()())) and thus the decision boundaries tend to be preserved as a consequence. Therefore, we propose the following optimization problem as a surrogate to the one in Problem (I):
min A.B
2 [[]
- G |== c22 -eal-- G=al()) +
G
A2
G
(2)
2,1
2,1
The matrix mixed norm for C E Ru is defined as |C = Σn= the matrix C to be sparse, iee. complete rows of C are zero The first two terms in Problem
I[C Il2 which encourages

---

Under review as a conference paper at ICLR 2021
Hidden
Hidden
Output
ZG
Zc:
Output
ZGa
ZGa
([(()) ConvesHall 2a,) 6(R())) Convexffull 26,)
Figure 4: Tropical Pruning Pipeline. Pruning the 4th node, equivalendy removing the two yellow vertices of zonotope 2a, does not affect the decision boundaries polytope, which will lead to change in accuracy.
(2) aim at approximating the original dual subdivision 8 (([(x)) by approximating the underlying generator matrices, 1₁ and G2. This aims preserve the orientation of the decision boundaries of the newly constructed network. On the other hand, the second two terms in Problem (2) act as regularizers control the sparsity of the constructed network by controlling the sparsity in the number of line segments. We observe that Problem (2) is not quadratic in its variables, since as + ReLU(-B(C (B()))))
per Corollary, 1 G1 DDaag
and G2 Diag (Be,) However, since Problem (2) is separable in the rows of Á and B, we solve Problem (2) via alternating optimization over these rows, where each sub- problem can be shown to be convex and exhibits a closed-form solution leading
) + -+LLU(((B(LL.)))
very efficient solver. For case of notation, we refer to ReL,(B((,;) and (ELU(B((i.)) as B a (i, and B (i, (i. respectively, As such, the per row update for A (first linear layer) is given as follows:
1 1ay
/2 (c) + ch)
c Ci.,) + cfG)((,))) [c] + cb)
(i,:)) max 1
G (is) [(c +
where ct is the 8thh element of c₁ = ReLU((((,)) +
and c2 ReL
)) + (eLUU(B((1.)). Similarly, the closed form update for the 5th element of the second linear
layer is as follows:
B B1(1) max (,. A(G.: (G,:))GG--AA (1..) A|A0,011
[|A().))
where G1+ = Diag(B B (1,:)) A similar argument can be used to update the variables (2, B (I, and B (2, :). The details of deriving the aforementioned update steps and the extension to the multi-class case are left to the appendix. Note that all updates are cheap, as they are expressed in closed form single step. In all subsequent experiments, we find that running the alternating optimization for single iteration is sufficient converge to a reasonable solution, thus, leading to very efficient overall solver.
Extension to Deeper Networks. While the theoretical results Theorem 2 and Corollary I only hold for shallow network in the form of (Affine, ReLU, Affine), we propose greedy heuristic to prune much deeper networks by applying the aforementioned optimization for consecutive blocks of (Affine, ReL.U, Affine) starting from the input and ending the output of the network. This extension from a theoretical study of 2 layer network was observed in several works such as (Bibi et al., 2018).
Experiments Tropical Pruning. Here, evaluate the performance of the proposed pruning approach as compared to several classical approaches on several architectures and datasets. In particular, we compare our tropical pruning approach against Class Blind (CB), Class Uniform (CU) and Class Distribution (CD) (Han et al., 2015; See et al., 2016). In Class Blind, all the parameters of layer are sorted by magnitude where the 2% with smallest magnitude are pruned. In contrast, Class Uniform prunes the parameters with smallest æ% magnitudes per node in a layer. Lastly. Class Distribution 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 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, we restrict our focus to pruning fully connected layers. We train AlexNet and VGG16 on SVHN, CIFARIO, and CIFAR 100 datasets. We observe that we can prune more than 90% of the classifier parameters for both networks without affecting the accuracy. Since pruning is often a single block within a larger compression scheme that in many cases involves inexpensive fast fine tuning, demonstrate experimentally that approach can is competitive
7

---

Under review as a conference paper at ICLR 2021
Alextter on SVHN
Alextlet on CIFAR1O
Alexilet on CIFARIDO
40
80
60
Accurssy
60
Acturaccy
10 30
30
AUCC- 0.857
CS- 0.63
AUC C.359
40
CU- AUC 0.852
CU-AUC 0.61
CU-AUC = 00.4
AUC 0.843
AUC 0.000
AUC 0.338
20
Ours AUC 0.885
Ours AUX 0.668
Ours AUC 0.375
30
60
70
80
90
100
30
60
70
80
50
100
20
40
60
DU
100
Pruning Rate %
Pruning Rate
Pruning Rate
VGG16 on SVHN
VEG16 CIFAR1O
VG616 on CIFARLOD
80
80
Accursy
60
CB. AUC 0.893
Arcunayy
60
AUC 0.974
50
AUC C.994
40
CU AUC 0.882
40
CU AUK. 0.875
20
CU- ALIC 0.866
0.881
0.e9
Fhrrs AIx: 0.88
20
Ours AUC = 0.09C
Ours -UC = 0.922
50
60
70
50
90
100
50
60
70
8D
90
100
20
40
60
BG
100
Pruning Rate %
Pruning Bate
Pruning Rate
Figure 5: Results of Tropical Pruning, Pruning- accuracy plots for AlexNet (top) and VGG16 (bottom) trained on SVHN, CIFARIO, and CIFARIO0, pruned with our tropical method and three other pruning methods.
and sometimes outperforms other methods even when all parameters or when only the biases are fine-tuned after pruning. These experiments in addition to many others are left for the appendix.
Setup. To account for the discrepancy in input resolution, we adapt the architectures of AlexNet and VGG16, since they were originally trained on ImageNet (Deng et al., 2009). The fully connected layers of AlexNet and VGG16 have sizes (256,512,10) and (512.512,10) for SVHN and CIFAR1O, respectively, and with the last dimension increased to 100 for CIFAR 100. All networks were trained to baseline test accuracy of (92%, 43%) for AlexNet on SVHN, CIFARIO, and CIFAR 100, respectively and 192%%92%,70995 previous work 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 a single alternating iteration to identify the rows in A and elements of B that will be pruned.
for VGGI6. To evaluate the performance of pruning and following
Results. Figure 5 shows the comparison between our tropical approach and the three 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, we achieve much better performance in pruning as compared to other methods. In particular, we are better in AUC by 3%, 3%, and 2% over other pruning methods on SVHN, CIFARIO I and CIFAR 100, 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 CIFAR10 10 and slightly worse on CIFAR100. While the performance achieved here is comparable to the other pruning schemes, not better, we emphasize that our contribution does not lie in outperforming state-of-the-art pruning methods, but in giving new geometry -based perspective to network pruning. More experiments were conducted where only network biases or only the classifier fine-tuned mieettned after pruning. Retraining only biases can be sufficient, they do not contribute to the orientation of the decision boundaries polytope (and effectively the decision boundaries), but only to its translation. Discussions biases and more results are left for the appendix.
Comparison Against Tropical Geometry Approaches. recent tropical geometry inspired approach was proposed to address the problem of network pruning. In particular, Smyrnis & Maragos (2019; 2020) (SM) proposed an interesting yet heuristic algorithm to directly approximate the tropical rational by approximating the Newton polytope. For fair comparison and following the setup of SM, we train LeNet on MNIST and monitor the test accuracy as we prune its neurons. We report (neurons kept. SM, ours) triplets in (%) as follows: (100, 98.60. 98.84), (90, 95.71, 98.82), (75, 95.05, 98.8), (50, 95.52, 98.71), (25, 91.04. 98.36), (10, 92.79, 97. 97.99), and (5, 92.93, 94.91). It is clear that tropical pruning outperforms SM by a margin that reaches 7%. This demonstrates that our theoretically motivated approach is still superior to more recent pruning approaches.
6 TROPICAL ADVERSARIAL ATTACKS
DNNs are notorious for being sensitive to imperceptible noise their inputs referred to adversarial attacks. Several works investigated DNNs decision boundaries in the presence of such adversaries. For instance, Khoury & Hadfield-Menell (2018) analyzed the high dimensional geometry of adversar-
8

---

Under review as a conference paper at ICLR 2021
ial examples by means of manifold reconstruction while He et al. (2018) crafted adversarial attacks by estimating the distance to the decision boundaries using random search directions. this work, we show how Theorem 2 can be leveraged to construct tropical geometric adversarial attack. Due to the space limitation, we leave the extensive formulation, the algorithm to find the adversary, and the experimental results synthetic and real datasets to the appendix.
CONCLUSION
We leverage tropical geometry to characterize the decision boundaries of neural networks in the form (Affine, ReLU, Affine) and relate it to geometric objects such zonolopes. We then provide tropical perspective to support the lottery ticket hypothesis, prune networks, and design adversarial attacks. A natural extension is compact derivation for the characterization of the decision boundaries of convolutional neural networks and graphical convolutional networks.

---

Under review as a conference paper at ICLR 2021
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, Sujeeth Bharadwaj. Bokyung Choi, Joshua J. 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 computed 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 align and translate. In International Conference 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: 194, 2018.
Leonard Berrada, Andrew Zisserman, and M Pawan Kumar. Trusting svm for piecewise linear cnns. arXiv preprini 161 1.02./1.11.......111111 2016.
Adel Bibi, Modar Alfadly, and Bernard Ghanem. Analytic expressions for probabilistic moments of pl-dnn with gaussian input. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9099-9107, 2018
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine learning, 2011.
Erwan Brugallé and Kristin Shaw. A bit of tropical geometry. The American Mathematical Monthly, 2014.
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.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 1rXiv:1810.04805 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. Proceedings of 13th International Conference on Artificial Intelligence and Statistics, 2010.
Peter Gritzmann and Bernd Sturmfels. Minkowski addition of 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 International Conference Learning Representations (ICI.), 2018.
10

---

Under review as a conference paper at ICLR 2021
G. Hinton, L. Deng, D. Yu, G. E. Dahl, A. Mohamed, N. Jaitly, A. Senior, V. Vanhoucke, P. Nguyen, N. Sainath, and B. Kingsbury. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal Processing Magazine, 2012.
Ilia Itenberg, Grigory Mikhalkin, and Eugenii I 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 arXiv:1904.01062, 2019.
Mare Khoury and Dylan Hadfield-Menell. On the geometry of adversarial examples. arXiv preprint arXiv:1811.000525, 2018.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. ImageNet classification with deep con- volutional neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2012.
Yann LeCun, John S Denker, and Sara Solla. Optimal brain damage. In Advances neural information processing systems, 1990.
Yann LeCun, Bengio, and Geoffrey Hinton. Deep learning. Nature, 2015.
Yu Li, Peter Richtarik, Lizhong Ding, and Xin Gao. On the decision boundary deep neural networks. arXiv preprint arXiv:1888.05388, 2018.
Qinghua Liu, Xinyue Shen, and Yuantao Gu. Linearized admm for nonconvex nonsmooth optimiza- tion with convergence analysis. IEEE Access, 2019.
D. Maclagan and B. Sturmfels. Introduction Tropical Geometry. Graduate Studies in Mathematics. American Mathematical Society, 2015.
Ngoc Mai Tran and Josephine Yu. Product-mix auctions and tropical geometry. Mathematics of Operations Research, 2015.
D Melzer: On the expressibility of piecewise-linear continuous functions as the difference of two piecewise-linear convex functions. In Quasidiffereniaa Calculus. Springer, 1986.
Grigory Mikhalkin.
Enumerative tropical algebraic geometry r2. Journal of the American Mathematical 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.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robust- ness via curvature regularization, and vice versa. CVPR, 2019.
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 Chmiela, Klaus-Robers Müller, and Alexandre Tkatchenko. Quantum-chemical insights from deep tensor neural networks. Nature Communications, 2017.
Abigail See, Minh-Thang Luong, and Christopher D. Manning, Compression of neural machine translation models via pruning. CoRR, 2016.
Shai Shalev-Shwarzz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.

---

Under review as a conference paper at ICLR 2021
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556 2014.
Georgios Smyrnis and Petros Maragos. Tropical polynomial division and neural networks, arXiv preprint arXiv:
2019.
Georgios Smymis and Petros Maragos. Multiclass neural network minimization via tropical newton polytope approximation. International Conference on Machine Learning, ICML 2020, 2020.
Kerrek Stinson, David F Gleich, and Paul G Constantine. A randomized algorithm for enumerating zonotope vertices. arXiv preprint arXiv:160..06620, 2016.
Kaidi Xu, Sijia Liu, Pu Zhao, Pin- Yu Chen, Huan Zhang, Deniz Erdogmus, Yanzhi Wang, and Xue Lin. Structured adversarial attack: Towards general implementation and better interpretability. arXiv preprint 1rXXvv880..01660 2018.
Liwen Zhang, Gregory Naitzat, and Lek- Heng Lim. Tropical geometry of deep neural networks, In International Conference on Machine Learning, ICML. 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 Damelll, and Olga G. Troyan- skaya. Whole-genome deep-learning analysis identifies contribution of noncoding mutations to autism risk. Nature Genetics, 2019.
12

---

Under review as a conference paper at ICLR 2021
X
1.4
0.5
0.3
0.4
1.5
0.2
0.5
3.5
Y
X
0.5
1.5
(a)
(b)
Figure 6: The Newton Polygon and the Corresponding Dualsubdivision. The Figure the left shows the newton polygon PJ)) for the tropical polynomial defined in the second example in Figure The dual subdivision (f constructed by projecting the upper faces of P(f), shadowing, on R?.
PRELIMINARIES AND DEFINITIONS.
Fact P+Q = (p + Vp E P and g E Q} is the Minkowski sum between two sets P and Q.
Fact 2. Let f be tropical polynomial and let a E N. Then
=
Let both f and g be tropical polynomials. Then Fact
PU
Fact
P(f + g) = ConvexHull UVP
(4)
Note that V(P(f)) is the set of vertices of the polytope P(f).
Definition 7. Upper Face of Polytope P: UF(P) is an upper face of polytope P in 12 if x te, $ P for any x E UF(P), t > 0 where en a canonical vector. Formally,
UF(P) = {x: X P. x le, <L> 0}
EXAMPLES
We revise the second example in Figure 1. Note that the dimensional tropical polynomial [(x v) can be written as follows:
f(, v)
1) O)
x
(a2
= (x²
13

---

Under review as a conference paper at ICLR 2021
First equality follows since multiplication is distributive in rings and semi rings. The second equality follows since 0 is the multiplication identity. The penultimate equality follows since y @ 2 y. ④ y @ O & 1 and x 2 x @ 1 z, y. Therefore, the tropical hypersurface T(f) (f)) is defined as the of (zr, y) where f achieves its maximum at least twice in its monomials. That is to say,
= [[(_:)))(((")))--oaaaaaaa1f1f-
((f(z,)) = =
This set T(f) is shown by the red lines in the second example in Figure 1. As for constructing the dual subdivision {(.), we project the upperfaces in the newton polygon P( to R22 Note that P()) with biases per the definition in Section 2 is given P(f) = ConvHull (a,, ci) TR2 x R Vi
1. 1.....6) 6) where (a,, c.) are the exponents and biases in the monomials of f. respectively. Therefore,
P()) ConvHull (2, 0, 1), (1, 1), (1, 0, 0), (0, 2, 1), (0, 1), 00, as shown in Figure 6(a).
As per Definition 7, the set of upper faces of P is:
11, UP(P()) = ConvHull (0, 2, 1), (1,1,)), (0, 1, 1)] U ConvHull (,, (0,0, 0)} (2,,),
U ConvHull (0, 1,)
This set UP)P(f) is then projected, through æ, to R2 shown in the yellow dashed lines in Figure 6(a) construct the dual subdivision 8(f) in Figure 6(b). For example, note that the point (0, 1) UF(f) and thereafter, x (0, 2, 1) = 20, E 8(f).
10 PROOF OF THEOREM 2
Theorem 2. For a bias-free neural network in the form of f(x) RR - R² where A E 2 and B E 72xp, let R(x) = (x) @ Q2(x) 4 H2(x) @ Q Q1(x) ) be a tropical polynomial. Then:
Let B {x TR f((x) fa(x)} define the decision boundaries of J, then B C (R(x)).
5 (R(x)) ConvHull (2. 2c,). 2g, is zonotope in IR" with line segments +).:))))) Za,
((B(11,) + B- (2, AJ,;)))) and shift is a zonotope in RR with line segments {(B (1,5) + B (2, (J..)) (. and shift (B+(1,)) + B A- The line segment (B+(1,) + B (2, [A +(j;: (j.)) has end points A (j.::) and (j.:) in Te and scaled by (B + (1,J) + B {),
Note that A = max A, 0) and A- = max( - A,,0) where the max(.) is element-wise, The line segment (B(,,))+ B(2, (A(, A(j.:)-)
one that has the end points A(j.:)+ and A(j.:) in IR" and scaled by the constant B(1,))+ + B(2.))
Proof. For the first part, recall from Theoreml I that both fi and f2 are tropical rationals and hence,
fi(x) = (x) - (x) fa(x) = H2(x) - Q2(x)
Thus
B = {I E R. fi(x) = f2()) = {a EI Hx(x) - Qi(x) = -2(x)) Q2(x))
-
{ R" Hi(x) + Q2(x)) H2(x) + Qi(x))
= (IER" R" Hx)x) O (x(x) = H2(x) @ (x(x)}
Recall that the tropical hypersurface is defined the set of x where the maximum is attained by two or more monomials. Therefore, the tropical hypersurface R(x) is the set of x where the maximum attained by or more monomials in (H, (x) @ Q2(x)). attained by two more monomials in
14

---

Under review as a conference paper at ICLR 2021
(H2(x) O (x)),, 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)) (x) o UT(
Qx))) BB.
Therefore B T (((x))). For the second part of the Theorem, first the decomposition pro- posed 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 tropical rational follows
f(x) (B+ -B) max A
A
ATX)
B t max A x, x
X
B max (A A x B A
Therefore, have that
Hi(x) + Q2(x) = B (1,:) B (2,))) I x
B (L,)). ([.:)++BB (B..) A
+Q(x))) =
max Aax(AxxxAAx Axx
(B* (B Axx.
Therefore, note that:
6(R(x)) = (11(()) (H)()))((()())))))))))))))))))))
@ (((s)QQ11 (
ConvexHull (())))))0(2)))))(((((())
ConvexHull
Now observe that Hx(x) En= B (1(
B (2.1)
max (A+().), A (.)))) tropically is
B (1,))B (2.5)
given as follows Hi (x) = 00-11 x @ XA (1:)
thus we have that
x (1:)) +... (x)) (B* + B (2, 1)) )(
(x**(1)))
[BB((1,)) +B (2.p) (6(xA+(A)) @x ((::)))
= -BB'(1,1) +B +B 322,11) ConvexHull A AI,;;,, A (1,::) +...
((B+(L.P) (1.p) B (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 2" with end points that are (A+(i,) A -ii,:)) (i.:)} scaled with B of line segments which a zonotope. Moreover, note that Q2(x) (B (1,:) + B (2. :))
g (1, i) + B (2, i). Observe that ((F is Minkowski sum
tropically is given as follows (x x (G.))m" aanon (9.1)) One can see that ((Q(xx)) is Vi in R" (which is a standard sum) resulting in point. Lastly, 5(H, (x))x())(())))) (8(2(xx) is Minkowski sum between zonotope and a single point which corresponds to a shifted zonotope. A similar symmetric argument can be applied for the second part 5( (-((
the Minkowski sum of the points {B -Bt ((l.))(AA-)))))))
15

---

Under review as a conference paper at ICLR 2021
is also worthy mention that the extension 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 {o E R (x) = fy(x)) and the rest of the proof will be exactly the same.
PROOF OF PROPOSITION
Proposition 1.
The zonotope formed by p line segments in RRth with arbitrary end points {[ui, uz]) equivalent to the zonotope formed by the line segments { - u., 0, with a shift of Ei uz
Proof. Let Uj be matrix with (;(;,t) = l,,.. P. w a column-vector with w(i) W4. i = 1, . and p is a column-vector of ones of length Then, the zonotope 2 formed by the
Minkowski sum of line segments with arbitrary end points can be defined as:
w + (1 - w;)us; E [0, diA
3 =
Am
Uww U2w U21p, We (0, 1j
(U, U2) w U21p, w 1e 11²)
- U2) w, we (0, 11 {
Since the Minkowski sum of between polytope and point is translation; thereafter, the proposition follows directly from Definition
Corollary 2. The generators of EG, Zc, in Theorem 2 can be defined as Gi
Diagl [ (1,:) + (B (2,, and G2 Diagl(B (2,:)) (1;)),,) both with shift
(B (1.:) B (2.:) +B (1,:) +B (2. A where Diag (v) arranges v in diagonal matrix.
Proof. This follows directly by applying Proposition to the second bullet point of Theorem
11.1 OPTIMIZATION OF OBJECTIVE 2 OF THE BINARY CLASSIFIER
min A, 2
G G1 + G2 G2
+ G1 2,1
+
+
G2 2,1
(5)
Note that G. Diag (eL,)(((,))) ReLU( (BLLU,BB(2)))) 1)) A, G2 Diag ReLU((((.:)
ReLU( CLLUU-B(U B(1 A. Note that G. Diag ReLU(B((,:)) ReLLU(-B(2.)) A and G.
Diag ReLU(B (2, :)) ReLU(-B(L.))) A. For ease of notation, we refer ReLU :)) and
ReLU(- (ii:)) as B (i,:) and B (t,:), respectively. We solve the problem with co-ordinate descent alternate over variables.
Update Á.
Diag (c,) Á G, ||2 +
1 Diag( cy A G2|l² Aı Diag(ci)A 2,1
Á < arg min
+ de Diag(cz)
2,1
where C₁ = ReLU(((1,:) + ReLU(-B(2B. :)) and C2 = ReLU ReLU ReLU(-B(L,.).. Note that the problem is separable per-row of Á. Therefore, the problem reduces to updating rows À independently and the problem exhibits closed form solution.
16

---

Under review as a conference paper at ICLR 2021
Ai, - Gi [ c,A(i,))) G2(L,)) (aivec + )e A(i.))
(ii,)) arg min ((a:))
A(i,)) (G. c (2.
1 1t +
A(i.))
arg min A(i.)) 2
[c] + c
[c + cb)
2
(1 1 1ivve + 22V
cc) (c (i, + G2
max
-
1
.0
[c) + +02)
cj Co(tt))) Ga(i)) (cf
[ + cb)
Update (1,;)).
B (1,,1)) = arg min 1 Diag B (1,,)) (+,))) 2
A- C₁ + A Diag B (1,)), A C. 2,1
Callan- s.t. (1 0.
Note that C G. Diag B (2,:) Á and where Diag (B-(2.)) Å. Note the problem is
separable in the coordinates of B B+ (1,:) and a projected gradient descent can be used to solve the problem in such way as:
1 -+(1))A(:)- - Ci + (+(,))A(j.)) + C2(..)) s.. B*(1,)) 20 0.
B (1,5)) = arg min B+(15) 2
similar symmetric argument can be used update the variables B (2,:), B2,:)),B+(1,) and (2,),)
12 ADAPTING OPTIMIZATION 2 FOR MULTI-CLASS CLASSIFIER
Note that Theorem 2 describes a superset to the decision boundaries of a binary classifier through the dual subdivision R(x), i.e. 5 (((()). For neural network with classes, natural extension for it is to analyze the pair-wise decision boundaries of of all k-classes. Thus, let T T(RG be the superset the decision boundaries separating classes and j. Therefore, natural extension the geometric loss in Equation is to preserve the polytopes among all pairwise follows:
Σ a( ((ConvexHull 22 (2G Zo zo,t ConvexHull (Z 2a (a.=..))) (6)
min viFjlss
The set S is all possible pairwise combinations of the k classes such that S = ([i,)), * j, = kij = I,..., kj. The generator ((G((,))) is the zonotope with the generator matrix G -Daa (eLLU(B(i:)) ReLU(-B(j.:)) Á. However, such an approach is generally computationally expensive, particularly, when is very large. To this end, we make the following observation that G(itg-) can be equivalently written as Minkowski sum between two sets zonotopes with the generators G Diag ReL.)((i.:)) Á and G,- Diag ReLLU(B,)) Á. That is to say, Za ZG = Z fZg... This follows from the associative property of Minkowski sums given as follows:
Fact 5. Let (8:)7 be the set of n line segments. Then we have that
$ = 5 ...S... ..........= PPV
where the sets P = Sy and V Fjecs Sj where C₁ and C2 are any complementary partitions of the set {5:)
17

---

Under review as a conference paper at ICLR 2021
Hence, G j expanded as follows:
( can be seen concatenation between G₁- and Gj-. Thus, the objective in can be
min A.B. viisles
E
d(ConvexHull (2 2G g.,)..)) ConvexHull (Zo 2a(tt.)))
-min A,B Y(JJes
Σ
ConvexHull
(2a 22 2o,
ConvexHull (Za,+ 22 f22.-)
(c;t,.));
Σ
G++
G++
- +
Gi-
G 2
|=
min A,B
G
G--
G
Vi.jJEs
min A.B
Σ
G
G
2
1
G G,-
2
+
1
G
Gy+
|| F
1 +
1 G G 1
2
F
2
F
v(idEES
1-1
2 + G G G.
1
min
G - G21
2
The approximation follows in similar argument to the binary classifier case. The last equality follows from a counting argument. We solve the objective for all multi-class networks in the experiments with alternating optimization in similar fashion to the binary classifier case. Similarly to the binary classification approach, we introduce the 1|-1|2,1 to enforce sparsity constraints for pruning purposes. Therefore the overall objective has the form:
min A.B
G. - G. ||- + +
- Gi
l + +1(G.
|
+
+
12a) 2211
2
For completion, derive the updates for Å and B.
Update Å.
Σ (1 (IDing Diag B+,::)) A Gi+ 1 + Diag (B (c.:) A Gi- 1:-1(
À = arg min
A
Am
Diag B (1,:)) A 112111111111 + +|Diag (B.(..)) (i.:) A Al1.))
+ >
Similar to the binary classification, the problem is separable in the rows of Å. and a closed form solution in terms of the proximal operator of &a norm follows naturally for each (i,
Update (i,:).
B (i,:) arg min Diag (B+(i.)) À- G, A-Q. (+():)
|= F
A Diag (B+(i.)) A 2.1 s.t. B+ 0.
Note that the problem is separable per coordinates of B (i,:) and each subproblem is updated as:
B (+.j))A (i.)) 2
B arg min (t,)))
+ B (i.j))
s.t. B B
2
= arg min
B (i.j))) G.+
|
+ B(i.s) A(r.)) s.t. B+ 2
2
(t.)))
max 0, AG.:)) G,+(1.)) AIAAG.))
!)
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-
18

---

Under review as a conference paper at ICLR 2021
13 TROPICAL ADVERSARIAL ATTACKS.
Dual View to Adversarial Attacks. For a classifier f R - R and input xo classified as c, a standard formulation for targeted adversarial attacks to different class is defined as:
min D(n) s.t. arg max (xx + n) = 1 #
This objective aims to compute the lowest energy input noise 1) (measured by 'D such that the the new sample (Xo + ')) crosses the decision boundaries of f to a new classification region. Here, we present dual view adversarial attacks. Instead of designing a sample noise 17 such that (xo + 7) belongs to a new decision region, one can instead fix X and perturb the network parameters to move the decision boundaries in a way that X appears in new classification region. In particular, let A1 be the first linear layer of f. such that f(xo) = (A) One can now perturb A to alter the decision boundaries and relate this parameter perturbation to the input perturbation as follows:
g((A1 EA. (xo) (Aix0 + xo) x + Ain) = fxx + 17).
(8)
From this dual view, we observe that traditional adversarial attacks are intimately related to perturbing the parameters of the first linear layer through the linear system: A {A, Xo. The two views and formulations are identical under such condition. With this analysis, Theorem 2 provides explicit means to geometrically construct adversarial attacks by perturbing the decision boundaries. In particular, since the normals to the dual subdivision polytope 5( (R(x)) of given DNN represent the tropical hypersurface T (R(x)), which is a superset to the decision boundaries set B, εA, can be designed to sufficiently perturb the dual subdivision resulting in a change the network prediction of Xg the targeted class t. Based on this observation, we design an optimization problem that generates two sets of perturbations, an input perturbation and parameter perturbation, that are equivalent to each other.
Formulation. Based on this observation, we formulate the problem as follows:
min TiEAA
D1(1) (EA.) s.t.
-loss(g(A1()) n)). -1; I1 Sii
loss(g((A + EA, x). )x,
S 11; (xo + 1) E 10, (EA.llo,, E A Xo-
The loss is the standard cross cross-entropy loss. The first row of constraints ensures that the network prediction is the desired target class when the input X perturbed by y,, and equivalently by perturbing the first linear layer A by EA,, This is identical to f1 as proposed by Carlini & Wagner (2016). 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 ÇA,- For a single hidden layer neural network parameterized as (A, + (A, R and B 2 for the first and second layers
respectively, D2 can capture the perturbations in each of the two zonotopes discussed in Theorem 2 and we define it as:
2 Σ j=l
D2(EA,)
Diag (B+ BBagg(++tr) (J.:))
Diiaag (B (..:))a,,l
(10)
We solve Problem (9) with a penalty method on the linear equality constraints, where each penalty step is solved with ADMM Boyd et al. (2011) in similar fashion to the work of Xu et al. (2018).
The function D2(EA) captures the perturbation in the dual subdivision polytope such that the dual subdivision of the network with the first linear layer A₁ is similar to the dual subdivision of the network with the first linear layer A₁ + EAi- This can generally formulated as an ap-
proximation the following distance function di ConvHull (Za, Za.) .ConvHull (ZG, Zo.)).
where G = Diag ReLU(B(1,:) + ReLUU-B((2,))) :)) A A G2 = Diag (e2, )) + ReLU -B(L:)) A + ( G1 = Diag ReLU(B((,:)) - ReLU(-B((..)) À and G2 = Diag ReL ReL,((((2:) + ReLU(-B(1;)) A. In particular, to approximate the function d, one can
19

---

Under review as a conference paper at ICLR 2021
similar argument in used in network pruning 5 such that D2 approximates the generators of the zonotopes directly as follows:
D2(EA,)
1
G1 G1
|| +
1
G2
G2
2
2
F
1
12
1
Diag
B B1,,, EA.
Diag
B (1, EA,
2
2
Diag B (2,
En,
+
Diag BT (2, Ea,
This thereafter be extended multi-class network with k classes follows D2(EA,) S Diag B (+(.))))a.)) I|= + Diag B BB-():))
F Following Xu et al. (2018), we take (1) 1/2 |1 Therefore, we can write 9 as follows:
min n.EA
Di(1) + Σ Diag (+. EA
F +
Diag B (i. EA
12 F
5=1
s.t.
- -loss(g(AA + 1)), < -1,
-loss(o((A) + EA, (x)),)) S -1,
[]", |1 S El
1EA E2, A EA, = 0.
To enforce the linear equality constraints A - Xo O. we penalty method, where each iteration of the penalty method we solve the sub-problem with ADMM updates. That is, we solve the following optimization problem with ADMM with increasing À such that À For ease of notation, lets denote L(xo + 7) -loss(gg ((oss(((A1(x))) + 1)), and L(Ai) = (loss(g((A) + EA, )x,),
Diag ReLL((((.:)) 12 + +||Diag (ReLU(-B(j.))) CA,
min R.A,MEE
11r122
1=1
+ L(xo + 2) hi(w) + h2(EA,) + A/AAn EA, x C(A,).
s.t.
n = z 2 w.
where
00
if (xo + 7) E [0, 1]", || Se
h2(EAi)= = 00 if IKEA 100,00 S 100,
(n())
xe,
else
else
The augmented Lagrangian given follows:
L(1, w, 2, E,, v) = ||>/33 + L(xo + 2) + (w) +
Diag B (j,:))EA, ||- --IDDiag(B (B ((,:)) ()):ag(B 11?
+ E(An) + (2( A1|A Ea, X + u T (n 2) + + (w z)
+ P (1n z ||w -
2
Thereafter, ADMM updates are given as follows:
(n) k+1 w xtl] arg min L(), w, 2² ek u vh),
n.w
z k+1
arg arg C(1 wk+ z, St ut vt),
ckl arg
arg min [(n k+1 w+t 2 EA, u² v²).
EA.
20

---

Under review as a conference paper at ICLR 2021
u ++ uº + p(n 2et1), vh+ = v + p(wh+1 -2 2
Updating y/:
*+1 arg min |/ll2 + A|| Ea. xol12 +u u 17 P
z112
2
(2AA A + (2 (2) -1 (22ATTE Et + pz" u²)
Updating w:
w w arg min v RT
h1(w) + 1| z²" =2111
vk
2
arg min W
w
z
+ - h1 (w).
2
2
The update w is separable in coordinates as follows:
min(1 x1 z 1/00k > min(1 x0x c1)
b+1
max - Xp,
(1)
x 1/ovk max -X0; - 61
z² 1/2v
otherwise
Updating z:
k+1 arg min L(xo + z) ut v 2 (11)) z/12 |||w
z
Liu et al. (2019) showed that the linearized ADMM converges for some non-convex problems. Therefore, by linearizing L and adding Bergman divergence term 'f' /²/2/1 * we then update as follows:
1/=2*
+ 1 'u + wh p
+ v*) VL(z* + xxo)
17th + 2p
P
is worthy mention that the analysis until this step inspired by el. (2018) with modifications to adapt our new formulation.
Updating Ex:
<x
arg min |&,, 11: + AI|EA, X0 Amile [(Ai) s.t. |EA,, S 62.
EA
The previous problem can be solved with proximal gradient methods.
Experimental Setup. For the tropical adversarial attacks experiments, there are five different hyper parameters which are
6 The upper bound for the infinite norm of 8.
62 : The upper bound for chell-lloc,ao of 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.
21

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Solving Problem (9)
Input: A RRx= B E TRxx,, xo E AR".,, 0,7 1, 12,K00 0,E 0 =0pxn 11 x² = w
z²= u² w = On.
Output: 1); CA,
Initialize: Po
while converged do for k < K do
7 update: n (2AA A + (2 p) -)))) Ex, xo + p2 -u²)
min(1
61
2 1/Ovk min(1 X0, 61)
w update: wh+1 max X0; =1) xz - 1/ov/ max( -Xo, -EI)
1/pv/
:otherwise
update:
2 *+1
t1
*h=
pla + 1/pu" + w + +//04+) - vL(zz + xo))
+2p
EA, update:
ck+1 arg m IKEA, 11 >llEA, 1 ((A1) s.t. 1100 5E2
SA
u update: u u + p( - =z
update: v v + p(wk+1 -2 ))
P 4++17 7P
P - Pu
Figure 7: Dual View of Tropical Adversarial Attacks. We show the effects of tropical adversarial attacks synthetic binary dataset two different input points (in black). From left to right: decision regions of the original and perturbed models, and decision boundaries polytopes (green for original and blue for perturbed).
For all of the experiments, we set the values of E2, A, 1 and p to 1, 1,10,,,,, 2.5 and 1, respectively, As for 61 is set to 0.1 upon attacking MNIST images digit 4 set to 0.2 for all other MNIST images.
Motivational Insight to the Dual View. We train network with 2 inputs, 50 hidden nodes and outputs on a synthetic dataset where we then then solve Equation for a given X shown in black in Figure 7. We show the decision boundaries with and without the perturbation ÇA, the first linear layer. As show in Figure 7, perturbing an edge of the dual subdivision polytope, by perturbing the first linear layer, corresponds to perturbing the decision boundaries and results in the misclassification of Xo. As expected, perturbing different decision boundaries corresponds to perturbing different edges of the dual subdivision. Note that the generated input perturbation is sufficient as well into fooling the network in classifying Xy + 77, and by construction is equivalent to perturb the decision boundaries of the network. We show later another example where we alternate the position of x and construct successful adversaries in both the input space, and the parameter space. Furthermore, we conduct later section, which show that successful adversarial attacks
experiments on MNIST images 77 can be designed by solving Problem (9). Figure 7 shows another example where the sampled to be attacked is closer to a different decision boundary. Observe how the edge corresponding to that decision boundary of the decision boundary polytope has respectively been altered.
MNIST Experiments. Here, we design perturbations to misclassify MNIST images. Figure 8 shows
several adversarial examples that change the network prediction for digits 8 and 9 to digits 7, 5, and 4, respectively. In some cases, the perturbation is as small as 0.1, where xo E [0, 1]". Several other adversarial results reported in Figure 9. We again emphasize that approach is
22

---

Under review as a conference paper at ICLR 2021
not meant to be compared with (or beat) state of the art adversarial attacks but rather to provide novel geometrically inspired perspective that can shed new light in this field.
Figure 8: Effeet of Tropical Adversarial Attacks on MNIST Dataset. We show qualitative examples of
adversarial attacks, produced by solving Problem (9), 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.
S
5
S
Figure 9: Effect 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 [9,8,7,5,3] respectively. Fourth row from left: Clean image, perturbed images classified as [9,4,3,211] respectively. Fifth row from left: Clean image, perturbed images classified [8.4,3,2,1] respectively.
14 EXPERIMENTAL DETAILS AND SUPPLEMENTAL RESULTS
In this section, describe the settings and the values of the hyper parameters used in the experiments. Moreover, we will show some further supplemental results to the results in the main manuscript paper.
23

---

Under review as a conference paper at ICLR 2021
14.1 TROPICAL VIEW TO THE LOTTERY TICKET HYPOTHESIS.
We first conduct some further supplemental experiments to those conducted in Section In particular, we conduct further experiments re-affirming the lottery ticket hypothesis on three more synthetic datasets similar experimental setup to the one shown Figure 3. The new supplemental experi- ments are shown in Figure 10, A similar conclusion is present where the lottery ticket initialization consistently better preserves the decision boundaries polytope compare to other initialization schemes over different percentages of pruning.
Spare
Origiall hojtase
guundaan inBleiratton 10.33 gasssaan Indjatodiis
Effect 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.
Figure 10:
A natural question is whether it is necessary to visualize the dual subdivision polytope of the decision boundaries, i.e. 8 (((())), where R(x) H1 (x) @ Q2(x) @ (2(x) Q1 (x) as opposed visualizing the tropical polynomials (122 (x)) and 8(Q (1.2) (x)) directly for the tropical re-affirmation of the lottery ticket hypothesis. That is similar to asking whether is necessary visualize and study the decision boundaries polytope ([)))) as compared to the the dual subdivision polytope of the functional form of the network since for the 2-output neural network described Theorem we have that fi (x) H₂ (x) S Q1 (x) and fx(x) (x)x) & (x(... We demonstrate this with an experiment that demonstrates the differences between these two views. For this purpose, we train a single hidden layer neural network on the same dataset shown in Figure 3. We perform several iterations of pruning in similar fashion to Section 5 and visualise at each iteration both the decision boundaries polytope and all the dual subdivisions of the aforementioned tropical polynomials representing the functional form of the network, i.e. 5(H (1,2)(x) (x)) and 5(Q (12 (x)). It is to be observed from Figure 11 that despite that the decision boundaries were barely affected with the lottery ticket pruning, the zonotopes representing the functional form of the network endure large variations. That is to say, investigating the dual subdivisions describing the functional form of the networks through the four zonotopes 5( (12 (x)) and (Q2 (x)) is not indicative enough to the behaviour of the decision boundaries.
14.2 TROPICAL PRUNING
Toy Setup. To verify our theoretical work, we first start by pruning small networks that are in the form of Affine followed by ReLU followed by another Affine layer. We train the aforementioned network two 2D datasets with varying number of hidden nodes (100, 200, 300). In this setup, we observe from Figure that when Theorem 2 assumptions hold, our proposed tropical pruning is indeed competitive, and in many cases outperforms, the other non decision boundaries aware pruning schemes.
Experimental Setup. In all experiments of the tropical pruning section, all algorithms are run for only a single iteration where À increases linearly from 0.02 with a factor of 0.01. Increasing corresponds to increasing weight sparsity and we keep doing until sparsification is 100%.
24

---

Under review as a conference paper at ICLR 2021
8(71(x)
(1C))
((H))()))
((Q)(00)
Figure 11: Comparison between the decision boundaries polytope and the polytopes represent- ing the functional representation of the network. First column: decision boundaries polytope 5( ((R(x)) while the remainder of the columns are the zonotopes 5 H (x)). 5(Q1 (x)). 6 (x)) and (x)2xx)) respectively. Under varying pruning rate across the rows, is be observed that the changes that affected the dual subdivisions of the functional representations are far smaller compared the decision boundaries polytope.
serter
96
ALC
28 ALC
C2-
50
300
50
300
Parkcc
maric
Figure 12: Pruning Ressults on Toy Networks. We apply tropical pruning on the toy network that the form of Affine followed by ReLU followed by another Affine. From left right: (a) dataset used for training (b) pruning networks with 100 hidden nodes (c) 200 hidden nodes (d) 300 hidden nodes.
Supplemental Experiments. We conduct more experimental results AlexNet and VGG16 SVHN, CIFARIO and CIFARI00 datasets. We examine the performance for when the networks have only the biases of the classifier fine tuned after tuning as shown in Figure 13. Moreover, similar experiments is reported for the same networks but for when the biases for the complete networks are fine tuned in Figure 14.
25

---

Under review as a conference paper at ICLR 2021
AlexNet on SVHN
AlexNet on CIFAR10
AlexNet on CIFAR100
Accuracy N6
80
Accuracy %
60
Accuracy %
30
CB AUC 0.808
40
CB-AUC 0.672
CB AUC 0.375
CU AUC 0.831
CU AUC 0.659
CU AUC 0.362
40
20
10
Our AUC 0.838
Our AUC
0.706
AUC
0.308
20
50
60
70
80
100
60
80
90
100
20
40
60
80
100
Pruning Rate
Pruning Rate
%
Pruning Rate
VEG18 SVHN
VGG16 CIFARIO
80
80
Accurary
60
-60
CU AUC 0.852
40
CU AUC 0.914
40
CD AUC 0.852
CD. AUC 0.914
20
20
80
100
Pruning
Pruning
Figure 13: Results of Tropical Pruning with Fine Tuning the Biases of the Classifier. Tropical pruning applied on AlexNet and VGG16 trained on SVHN, CIFARIO, CIFAR100 against different pruning methods with fine tuning the biases of the classifier only. AlexNet on CIFAR10
AlexNet on SVHN
AlexNet on CIFAR100
600
Accuracy*
Accurccy
30
Accuracy
60
AUC 0,854
40
AUC 0.675
CB AUC 0.377
CU AUC = 0.87
CU AU-C = 0.663
CU AUC 0.365
40
AUC 0.859
20
AUC 0.66
10
CD AUC 0.365
20
100
Pruning
Pruning
Pruning
VGG16 SVHNN
VGG16 CIFAR10
80
60
Accuracy
-60
CU AUC 0.882
CU AUC 0.912
40
CD AUC 0.803
CD
AUC 0.914
Our AUC 0.897
20
Our AUC 0.908
60
80
100
60
80
100
Pruning Rate %
Pruning Rate %
Figure 14: Results of Tropical Pruning with Fine Tuning the Biases of the Network. Tropical pruning applied on AlexNet and VGGI6 trained on SVHN, CIFARIO, CIFAR 100 against different pruning methods with fine tuning the biases of the network.
26


Reviews:
[{"review_id": "slCEFDKqZtc", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 shows the decision boundary of a shallow ReLU network is a subset of a tropical hypersurface, and this tropical hypersurface is dual to a convex hull of two zonotopes given by the weights of the network.  The paper then considers various learning tasks and real data sets, most notably neural network pruning by using an interesting optimization to preserve the tropical hypersurface.  The tropical geometry content seems mostly about language to me.  In particular, the containment of the decision boundary in the tropical hypersurface (first part of Theorem 2) is quite evident, once notation is unpacked.  Also Proposition 1 and Corollary 1 in my opinion can be removed from the document.  On the other hand, the network pruning application that seeks to preserve the convex hull of the zonotopes seems rather substantial to me, with a nice derivation in the appendix.  I would put more emphasis on this myself.\n\nItemized comments follow.\n\n\nPage 3: Please be more clear about what type of objects $UF(\\mathcal{P}(f))$ and $\\delta(f)$ are.  Polyhedral complexes?\n\nPage 3: “For ease, we use ReLUs as the non-linear activation, but any other piecewise linear function can also be used.”  Is it not required for the tropical viewpoint that the slopes of the piecewise linear function be integers?  “Without loss of generality, as one can very well approximate real weights as fractions and multiply by the least common multiple of the denominators as discussed in Zhang et al. (2018).”  Can you remark whether the decision boundaries are stable to such approximations?  A brief discussion on how tropical is using the integral weights assumption may help the reader.\n\nPage 4: typo, “each output can be expressed as a tropical rational as per Theorem 1.”  Tropical rational function\n\nPage 4, Theorem 2: $\\delta(R(x)) = ConvHull(\\mathcal{Z}_{G_1}, \\mathcal{Z}_{G_2})$.  The LHS is a polyhedral complex or subdivision, the RHS looks like just a polytope?  Confusing, until some bit below where it is stated $\\delta(R(x))$ actually is not subdivided because there is no bias (so it is just a polytope).\n \nI worry there is only a fine line between “decision boundary” (this paper) and the boundary between the linearity regions of a single output ReLU network (I think early works).  In particular, is $T(R(x))$ also a superset for the boundary between the linearity regions of $(f_1 + f_2)(x)$?\n\nPage 5: “fast algorithms for enumerating these vertices are still restricted to zonotopes with line segments starting at the origin Stinson et al. (2016).”  I find it disingenuous to describe this as a restriction and then to present Proposition 1 as a fix.  This issue is very minor, and I think polytopes people would just say “without loss of generality…”\n\nPages 7-8: Tropical pruning sounds significantly more computationally intensive than the other simple pruning methods it is being compared to, even when the separability in rows is used.  There also seems to be some awkwardness with the biases since the tropical approach assumes no biases.  While not knowing about pruning of NNs, I still actually found this to be the most substantial and interesting part of the paper and appendix.  It uses the zonotope description of the tropical superset, and involves interesting optimization.  I would suggest the authors emphasize this subsection more. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "bDSkERqLueW", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Building upon the observation of Zhang (2018) that a class of deep neural networks have decision boundaries that correspond to tropical rational maps, the paper proposes new methods for pruning networks and constructing adversarial attacks that are based on the idea of minimizing or maximizing the changes to the decision boundary.  The methods focus on optimizing objectives related to the dual polytopes for the networks.\n\nThe strength of this paper is in its ambitious agenda: it is difficult to reason about the nonlinear functions learned by neural networks, so the paper’s proposal to use tropical algebra to try to provide new insights is a worthy goal.  Extending beyond Zhang 2018, the paper works out an explicit characterization of the two-layer two-dimensional dual polytopes which is good to see.  The experimental results on pruning of small networks (e.g., Figure 3,Appendix Figure 7) are suggestive that geometric issues may be important for understanding the success of lottery ticket pruning.  The simple observation (beginning with Appendix Eq 9) that adversarial attacks can also be analyzed as attacks on the first layer weights is interesting, although seems like a second separate topic.\n\nWhile the tropical geometry perspective is welcome, this reviewer found several lines of reasoning insufficiently convincing or unclear in the submitted paper.  The central assertion is that tropical geometry can lead to promising new pruning methods (or at least promising new insights about pruning methods).  However, why the proposed tropical pruning (Section 5) should be expected to work (or why it should be expected to provide insights on the pruning problem) is unclear for several reasons.\n\n1. The tropical pruning method is inspired by the explicit analysis of small networks in the paper, but the method is tested only on deep networks that are beyond the reach of this explicit analysis. This skips an important step in the analysis: is tropical pruning effective on small toy problems?  For example, in the small cases illustrated in Figure 3, tropical pruning is not one of the methods compared.  The paper would be strengthened if the new pruning method could be developed and either explicitly proved or experimentally verified on the small cases which are closer to the settings where the geometry has been explicitly characterized, before exploring claims and experiments in large networks.\n\n2. Why would insights about the geometry of the boundaries be preserved after retraining?  The method reasons about the geometry of the network after it is initially trained but then the paper measures the effect on the network after it is retrained.  The paper would be strengthened if it explained or argued why the lengthy retraining process would be expected to preserve rather than obliterate any geometric properties of the function.\n\n3. The paper does not provide enough intuition and explanation behind the unproved leap from Theorem 2 to Eq 1, and then from Eq 1 to Eq 2.  The text refers to subfigures of Figure 3 (e.g., a first subfigure showing explicit decision boundaries) that seem to be missing.  Figure 4 is a good illustration of the idea, but how the selection of the best change in geometry is related to the proposed objective in Eq 2 is not explained beyond the assertion that “decision boundaries tend to be preserved.”  This assertion should be backed up by more explicit reasoning, more explicit examples or some statistical data.\n\nThe work in the appendix bringing in analysis of adversarial examples is interesting but seems to be a second major topic that is not fully developed in the main paper and could be the subject of a different paper.\n\n**edit, based on revision and after discussion**.  Thanks to the authors for answering questions 2 and 3 in discussion and adding an experiment to the paper validating the tropical pruning method in a small setting.  The additional experiment provides some evidence that the tropical pruning method is working as argued, and I change my rating of the paper to 6.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "7Cg7wvc5zEo", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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 submission proposes the use of tropical geometry to understand the decision boundaries of neural networks. The targeted problem is quite interesting and the proposed method looks to be solid; however, I didn't thoroughly check the correctness of the proposed theorems. \n\nIn the experiments on tropical pruning, since for VGG16, the proposed method only shows better performance on the CIFAR10 dataset, more experiments are desired to make a strong conclusion. For instance, performing experiments on ResNet. \nWhy changing to use LeNet when comparing to Tropical geometry approaches?\n\nHow about the efficiency of the proposed approach? Is it practical to use the proposed method in a deep neural network?\n\nA minor issue: In the results section, \"Figure 4\" should be \"Figure 5\". ", "extra_scores": {}, "extra_text": {}}, {"review_id": "1FjLPpFmBl_", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "Summary:  This work studies the decision boundaries of neural networks (NN) with piecewise linear (ReLU) activation functions from a tropical geometry perspective. Leveraging the work of [1], the authors show that NN decision boundaries form subsets of tropical hypersurfaces. This geometric characterization of NN decision boundaries is then leveraged to better understand the lottery ticket hypothesis, and prune deep NNs. The authors also allude to the use of tropical geometric perspectives on NN decision boundaries for the generation of adversarial samples, but do not explicitly discuss it in any detail within the main text of the paper.\n\nStrengths: \n+ The paper is insightful and novel. \n+ Tropical geometry (TG) promises to be a particularly convenient language to study (ReLU) DNNs, and this work does a good job of showcasing the versatility afforded by a principled, geometric approach in improving our understanding of DNNs. \n+ The efforts put into making this paper accessible to readers unfamiliar with TG are also worth appreciating.\n\nWeaknesses: \n- The paper perhaps bites off a little more than it can chew. It might be best if the authors focused on their theoretical contributions in this paper, added more text and intuition about the extensions of their current bias-free NNs, fleshed out their analyses of the lottery ticket hypothesis and stopped at that.\n\n- The exposition and experiments done with tropical pruning need more work. Its extension to convolutional layers is a non-trivial but important aspect that the authors are strongly encouraged to address. This work could possibly be written up into another paper. Similarly, the work done towards generating adversarial samples could definitely do with more detailed explanations and experiments. Probably best left to another paper. \n\nContributions:  The theoretical contributions of the work are significant and interesting. The fact that the authors have been able to take their framework and apply it to multiple interesting problems in the ML landscape speaks to the promise of their theory and its resultant perspectives. The manner in which the tropical geometric framework is applied to empirical problems however, requires more work.\n\nReadability: The general organization and technical writing of the paper are quite strong, in that concepts are laid out in a manner that make the paper approachable despite the unfamiliarity of the topic for the general ML researcher. The language of the paper however, could do with some improvement; Certain statements are written such that they are not the easiest to follow, and could therefore be misinterpreted.\n\nDetailed comments: \n- While there are relatively few works that have explicitly used tropical geometry to study NN decision boundaries, there are others such as [2] which are similar in spirit, and it would be interesting to see exactly how they relate to each other.\n\n- Abstract: It gets a little hard to follow what the authors are trying to say when they talk about how they use the new perspectives provided by the geometric characterizations of the NN decision boundaries. It would be helpful if the tasks were clearly enumerated.\n\n- Introduction: “For instance, and in an attempt to…” Typo – delete “and”. Similar typos found in the rest of the section too, addressing which would improve the readability of the paper a fair bit.\n\n- Preliminaries to tropical geometry: The preliminaries provided by the authors are much appreciated, and it would be incredibly helpful to have a slightly more detailed discussion of the same with some examples in the appendix. To that end, it would be a lot more insightful to discuss ex. 2 in Fig. 1, in addition to ex. 1. What exactly do the authors mean by the “upper faces” of the convex hull? The dual subdivision and projection $\\pi$ need to be explained better.\n\n- Decision boundaries of neural networks: The variable ‘p’ is not explicitly defined. This is rather problematic since it has been used extensively throughout the rest of the paper. It would make sense to move def. 6 to the section discussing preliminaries.\n\n- Digesting Thm. 2: This section is much appreciated and greatly improves the accessibility of the paper. It would however be important, to provide some intuition about how one would study decision boundaries when the network is not bias-free, in the main text. In particular, how would the geometry of the dual subdivision $\\delta(R({\\bf x}))$ change? On a similar note, how do things change in practice when studying deep networks that are not bias free, given that, “Although the number of vertices of a 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”? Can Prop. 1 and Cor. 1 be extended to this case trivially?\n\n- Tropical perspective to the lottery ticket hypothesis: It would be nice to quantify the (dis)similarity in the shape of the decision boundaries polytopes across initializations and pruning using something like the Wasserstein metric.\n\n- Tropical network pruning: How are $\\lambda_1, \\lambda_2$ chosen? Any experiments conducted to decide on the values of the hyper-parameters should be mentioned in the main text and included in the appendix. To that end, is there an intuitive way to weight the two hyper-parameters relative to each other?\n\n- Extension to deeper networks: Does the order in which the pruning is applied to different layers really make a difference? It would also be interesting to see whether this pruning can be parallelized in some way. A little more discussion and intuition regarding this extension would be much appreciated.  \n\n- Experiments: \n- The descriptions of the methods used as comparisons are a little confusing – in particular, what do the authors mean when they say “pruning for all parameters for each node in a layer” Wouldn’t these just be the weights in the layer?\n- “…we demonstrate experimentally that our approach can outperform all other methods even when all parameters or when only the biases are fine-tuned after pruning” – it is not immediately obvious why one would only want to fine-tune the biases of the network post pruning and a little more intuition on this front might help the reader better appreciate the proposed work and its contributions. \n- Additionally, it might be an unfair comparison to make with other methods, since the objective of the tropical geometry-based pruning is preservation of decision boundaries while that of most other methods is agnostic of any other properties of the NN’s representational space.\n- Going by the results shown in Fig. 5, it would perhaps be better to say that the tropical pruning method is competitive with other pruning methods, rather than outperforming them (e.g., other methods seem to do better with the VGG16 on SVHN and CIFAR100)\n- “Since fully connected layers in DNNs tend to have much higher memory complexity than convolutional layers, we restrict our focus to pruning fully connected layers.” While it is true that fully connected layers tend to have higher memory requirements than convolutional ones, the bulk of the parameters in modern CNNs still belong to convolutional layers. Moreover, the most popular CNNs are now fully convolutional (e.g., ResNet, UNet) which would mean that the proposed methods in their current form would simply not apply to them.\n- Comparison against tropical geometry approaches for network pruning – why are the accuracies for the two methods different when 100% of the neurons are kept and the base architecture used is the same? The numbers reported are à (100, 98.6, 98.84)\nTropical adversarial attacks: Given that this topic is not at all elaborated upon in the main text (and none of the figures showcase any relevant results either), it is strongly recommended that the authors either figure out a way to allocate significantly more space to this section, or not include it in this paper. (The idea itself though seems interesting and could perhaps make for another paper in its own right.)\n\n- References:  He et al. 2018a and 2018b seem to be the same.\n\n[1] Zhang L. et al., “Tropical Geometry of Deep Neural Networks”, ICML 2018.\n[2] Balestriero R. and Baraniuk R., “A Spline Theory of Deep Networks”, ICML 2018.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the decision boundaries of shallow ReLU network using the formalism of tropical geometry. Its main takeaway is to provide a new interpretation of the lottery ticket hypothesis in terms of network pruning strategies that preserve certain geometric structure. 

Reviewers were appreciative of the clarity of the exposition, and the novel perspective on interesting and elusive phenomena such as the lottery ticket hypothesis. On the other hand, they also expressed some doubts about the significance of some aspects of the theory (such as proposition 1 and corollary 1), as well as the computational considerations required to elevate the analysis to large-scale architectures from applications. 

Ultimately, and after taking into consideration all the reviewing discussions, the AC believes that this submission is not yet ready for publications, but it is in a trajectory to become an important piece of work. In particular, the AC encourages delving deeper into the tropical network pruning. Additionally, the authors might want to discuss [Breaking the Curse of Dimensionality with Convex Neural Networks, Bach'17] in the related work, since this is the first instance the AC is aware of where the connection between zonotopes and shallow ReLU networks is established. 
Decision: Reject