Neural Network Approximation based on Hausdorff distance of Tropical Zonotopes
Authors: Panagiotis Misiakos
Georgios Smyrnis
George Retsinas
Petros Maragos
Venue: ICLR 2022 Poster (2022)
Keywords: Tropical Geometry
Zonotopes
Hausdorff Approximation
Neural Network Compression

Abstract: In this work we theoretically contribute to neural network approximation by providing a novel tropical geometrical viewpoint to structured neural network compression. In particular, we show that the approximation error between two neural networks with ReLU activations and one hidden layer depends on the Hausdorff distance of the tropical zonotopes of the networks. This theorem comes as a first step towards a purely geometrical interpretation of neural network approximation. Based on this theoretical contribution, we propose geometrical methods that employ the K-means algorithm to compress the fully connected parts of ReLU activated deep neural networks. We analyze the error bounds of our algorithms theoretically based on our approximation theorem and evaluate them empirically on neural network compression. Our experiments follow a proof-of-concept strategy and indicate that our geometrical tools achieve improved performance over relevant tropical geometry techniques and can be competitive against non-tropical methods. 

Published as a conference paper at ICLR 2022
NEURAL NETWORK APPROXIMATION BASED ON HAUSDORFF DISTANCE OF TROPICAL ZONOTOPES
Panagiotis Misiakos Georgios Smyrnis?, Georgios Retsinas Petros Maragos
'ETH Zurich, PUniversity of Texas Austin, Natiioal Technical University of Athens panagiotis misiakossinf wtt.kksssnn..nhe....e... ch, gretsinas@cent ntua. gr, maragosecs ntua.gr
edu,
ABSTRACT
In this work we theoretically contribute to neural network approximation by pro- viding a novel tropical geometrical viewpoint to structured neural network com- pression. In particular, we show that the approximation error between two neural networks with ReLU activations and one hidden layer depends on the Hausdorff' distance of the tropical zonotopes of the networks. This theorem comes as a first step towards purely geometrical interpretation of neural network approxima- tion. Based on this theoretical contribution, we propose geometrical methods that employ the K-means algorithm to compress the fully connected parts of Rel.U activated deep neural networks. We analyze the error bounds of our algorithms theoretically based on our approximation theorem and evaluate them empirically on neural network compression. Our experiments follow proof-of-concee strategy and indicate that our geometrical tools achieve improved performance over relevant tropical geometry techniques and can be competitive against non-tropical methods.
INTRODUCTION
Tropical geometry (Maclagan & Sturmfels 2015)
a mathematical field based on algebraic geometry and strongly linked to polyhedral and combinatorial geometry. It is built upon the tropical semiring which originally refers to the min-plus semiring (Rainn: A, +), but may also refer to the max-plu semiring [Cuninghame- Green 2012, Butkoviž 2010). In our work, we follow the convention of the max-plus semiring (Baaxx V, +) which replaces the classical operations addition and multiplication by max and sum respectively. These operations turn polynomials into piecewise linear functions making them directly applicable in neural networks.
Tropical mathematics cover wide range of applications including dynamical systems weighted lattices (Maragos) 2017), finite state transducers (Theodosis & Maragos] 2018 2019) and convex regression (Maragos & Theodosis 2020: T'ilivis al. 2021). Recently, there has been remarkable theoretical impact of tropical geometry in the study of neural networks and machine learning (Maragos) et al. 2021). Zhang al. (2018) prove the equivalence of ReLU activated neural networks with tropical rational mappings. Furthermore, they use zonotopes to compute a bound on the number of the network's linear regions, which has already been known in (Montáfar al. 2014). In similar context, Charisopoulos & Maragos (2018) compute an upper bound to the number of linear regions of convolutional and maxout layers and propose randomized algorithm for linear region counting. Other works employ tropical geometry to examine the training and further properties of morphological perceptron (Charisopoulos & Maragos 2017) and morphological neural networks (Dimitriadis & Maragos 2021).
Pruning or, generally, compressing neural networks gained interest recent years due to the surprising capability of reducing the size of a neural network without compromising performance (Blalock et al., 2020). As tropical geometry explains the mathematical structure of neural networks, pruning may also be viewed under the perspective of tropical geometry. Indeed, Alfarra et al. (2020) propose an unstructured compression algorithm based on sparsifying the zonotope matrices of the network. Also,
Conducted research student in National Technical University of Athens.

---

Published as a conference paper at ICLR 2022
Smyriis al. (2020) construct novel tropical division algorithm that applies to neural network minimization. generalization of this applies to multiclass networks (Smyrnis & Maragos 2020).
Contributions In work, contribute structured neural network approximation from the mathematical viewpoint of tropical geometry:
We establish a novel bound on the approximation error between two neural networks with ReLU activations and one hidden layer. To prove this we bound the difference of the networks' tropical polynomials via the Hausdorff distance of their respective zonotopes.
We construct two geometrical neural network compression methods that based zonotope reduction and employ K-means algorithm for clustering. Our algorithms apply on the fully connected layers of ReLU activated neural networks.
Our algorithms are analyzed both theoretically and experimentally. The theoretical eval- uation is based on the theoretical bound neural network approximation error. On the experimental part, we examine the performance of our algorithms on retaining the accuracy convolutional neural networks when applying compression on their fully connected layers.
BACKGROUND ON TROPICAL GEOMETRY
We study tropical geometry from the viewpoint of the max-plus semiring (Fmax. V, +) which is defined as the set 1mmax = R U {-oo] equipped with two operations (V,+), Operation V stands for max and stands for sum. max-plus algebra we define polynomials in the following way.
Tropical polynomials the function
A tropical polynomial f in variables x = (I1, 02, .... ra) is defined as 22....,
f(x) = max b₁}
(1)
(E[m]
where [n]] = ........,,,, a, are vectors in Rd and b; is the corresponding monomial coefficient in Bamax R U (-o)). The set of such polynomials constitutes the semiring Ra [x] of tropical polynomials. Note that each term af x + b; corresponds to a hyperplane in IR.. We thus call the vectors {ai) the slopes of the tropical polynomial, and [b:) the respective biases. We allow slopes to be vectors with real coefficients rather than integer ones, as it is normally the case for polynomials in regular algebra. These polynomials are also referred to as signomials (Duffin & Peterson 1973) in the literature.
Polytopes Polytopes have been studied extensively (Ziegler 2012 Grünbaum 2013) and occur as geometric tool for fields such as linear programming and optimization. They also have an important role the analysis of neural networks. For instance, /Zhang al. (2018); Charisopoulos & Maragos (2018) show that linear regions of neural networks correspond vertices of polytopes. Thus, the counting of linear regions reduces to a combinatorial geometry problem. what follows, we explore this connection of tropical geometry with polytopes.
Consider the tropical polynomial defined in l]. The Newton polytope associated to f(x) is defined as the convex hull of the slopes of the polynomial
Newt (J) canv(a [ni]]
Furthermore, the extended Newton polytope of fxx defined as the convex hull of the slopes the polynomial extended in the last dimension by the corresponding bias coefficient.
ENewt (f) := conv (af" b.) [n]]
The following proposition computes the extended Newton polytope that occurs when tropical operation is applied between two tropical polynomials. It will allow us to compute the polytope representation corresponding to a neural network's 's hidden layer.
Proposition 1. (Zhang et al. 2018 Charisopoulos & Maragos 2018) Let f.g 1mmax [x] be two tropical polynomials. Then for the extended Newton polytopes it is true that
ENewt (f V g) = conv ENewt (f) U ENewt (g)}
ENewt (J + g) ENewt (f) @ ENewt (g)
2

---

Published as a conference paper at ICLR 2022
(3,1,2)
UF(ENew((fVg)
(2.1.1)
(2,2.1)
(0,1,0)
(2,1,1)
(0.0,1)
(8,1,1)
(0.1.0)
(1.0.0)
(0,0,0)
(0,0,0)
(1,0,0)
(1,000)
ENewt (f)
ENewt (g)
ENewt (f V g)
ENewt (f +
Figure I: Illustration of tropical operations between polynomials, The polytope of the max (V) of f and g corresponds to the convex hull of the union of points of the two polytopes and the polytope of sum (+) corresponds to their Minkowski sum.
Here @ denotes Minkowski addition. particular, for two sets A, B S IR it is defined as A B= {a a A, b B} Corollary 1. This result can be extended to any finite set of polynomials using induction.
Example 1. Let J.g be two tropical polynomials in 2 variables, such that (xx y) max(2r + + 1,0), g(z. v) max(2, y, 1)
The tropical operations applied to these polynomials give
fV g = max (2x + y + 1, v,
J + g max + 1,,, 2x + 2y 1, 2x + 2,
Fig. 7 iillustrates the extended Newton polytopes of the original and the computed polynomials.
The extended Newton polytope provides a geometrical representation of a tropical polynomial. In addition, may be used to compute the values that the polynomial attains, as Proposition 2 indicates.
Proposition 2. Charisopoulos & Maragos 2018) Let f E Bmmax [x] be a tropical polynomial variables. Let FF(NNew (f)) be the points in the upper envelope of ENewt (f). where upward direction is taken with respect to the last dimension of Tdd+1, Then for each i E [m] there exists a linear region of f which fxx a. x by if and only if (aT bx) is vertex of U (ENewt (f))- Example Using the polynomials from Example ! we compute a reduced representation for J.V g.
fVV g max + y + 1, 1,0, y, 1) max(2x + y + 1,1,,,1) Indeed, the significant terms correspond to the vertices of F(Neewt (f g)) shown in Fig.
2.1 TROPICAL GEOMETRY OF NEURAL NETWORKS
Tropical geometry has the capability of expressing the mathematical structure of ReI.U activated neural networks. We review some of the basic properties of neural networks and introduce notation that will be used in analysis. For this purpose, consider the ReLU activated neural network of Fig. 2 with one hidden layer.
Network tropical equations The network of Fig. consists of an inpul layer (#1 .... F.). hidden layer f = (f....,,f, with ReLU activations, an output layer = (V1, Um) and two linear layers defined by the matrices A, C respectively. As illustrated in Fig. 2 we have A,: = (af, b,) for the first linear layer and Cj.: (Cji, Cj.,..., Cjn) for the second linear layer, we ignore its biases. Furthermore, the output of the i- th component of the hidden layer ff is computed as
d auaz k + 6,,0 max (a, + by, 0)
(x) = max
Σ
(2)
We deduce that each fa is a tropical polynomial with two terms. It therefore follows that ENewt (ft) linear segment in d+1 The components of the output layer may be computed as
My (x)x = Σ cxl((x)= = Σ lex.lf(xx) - Σ [cxaff(xx) = p,(x) - 9; (x)
(3)
0,30
6.50
3

---

Published as a conference paper at ICLR 2022
Tropical rational functions In Eq. (3), functions Pj. are both linear combinations of [f,] with positive coef- ficients, which implies that they are tropical polynomials. We conclude that every output node vl can be written as difference of two tropical polynomials, which is defined as a tropical rational function. This indicates that the output layer of the neural network of Fig. 2 is equivalent to tropical rational mapping. In fact, this result holds for deeper networks, in general, as demonstrated by the following theorem.
J2
f
Theorem 1. (hang et al.
2018) ReLU activated deep R equivalent to tropical
neural network F 1
Jn
rational mapping.
It is not known whether a tropical rational function r(x) admits an efficient geometric representation that deter- mines its values {r(x)} for E R&, it holds for tropi- cal polynomials with their polytopes in Proposition 2 For this reason, we choose to work separately the polytopes of the tropical polynomials pj. 4--
Figure 2: Neural network with one hid- den ReLU layer. The first linear layer has weights (a. } with bias {b,} correspond- ing to i-th node Vi [ma and the second
has weights {eych, Vjj E [m]] i E [n]]
Zonotopes Zonotopes are defined the Minkowski sum of a finite set of line segments. They are a special case of polytopes that occur building block for network. These geometrical structures provide a representation of the polynomials Pj. in (3) that further allows extended Newton polytopes of tropical polynomials Pj, lj. respectively, Notice from (3) that for each component 2 of the output Pjs qj are written as linear combinations of tropical polynomials that correspond to linear segments. Thus P, and Q2 are zonotopes. We call P, the positive zonotope, corresponding to the positive polynomial pj and Q, the negative one.
build our compression algorithms. We the notation P, Qj for the
Zonotope Generators Each neuron of the hidden layer represents geometrically a line segment contributing to the positive or negative zonotope. We thus call these line segments generators of the zonotope. The generators further receive the characterization positive or negative depending on the zonotope they contribute to. It is intuitive to expect that zonotope gets more complex as its number of generators increases. In fact, each vertex of the zonotope can be computed as the sum of vertices of the generators, where we choose a vertex from each generating line segment, either or Cy. (af), b.). We summarize the above with the following extension of (Charisopoulos & Maragos 2018).
Proposition 3. Pj. Qj are zonotopes in Rd+1, For each vertex of P3 there exists a subset of indices 14 of (1, n with Cji 0, Vi E I+ such that EsEL= Cji (a7 b.). Similarly, vertex u of Qj can be written as 11 Eier_ Cje (a. bi) where T_ corresponds to Cjz 0, L_.
APPROXIMATION OF TROPICAL POLYNOMIALS
In this section we present our central theorem that bounds the error between the original and approximate neural network, when both have the architecture of Fig. 2 To achieve this we need to derive bound for the еттог of approximating simpler functional structure, namely the tropical polynomials that represent the neural network. The motivation behind the geometrical bounding of the error of the polynomials is Proposition 2 It indicates that a polynomial's values determined at each point of the input space by the vertices of the upper envelope of its extended Newton polytope. Therefore, it is expected that two tropical polynomials with approximately equal extended Newton polytopes should attain similar values. In fact, this serves as the intuition for our theorem. The metric use define the distance between extended Newton polytopes is the Hausdorff distance.
Hausdorff distance The distance of point u E Rd from the finite set V C Rd is denoted by either dist. (u, V) dist. (V, u) and computed minvey [|u -v]] which is the Euclidean distance of
4

---

Published as a conference paper at ICLR 2022
from its closest point V. The Hausdorff distance HVV)20) of two finite point sets V.u R is defined as
H (V,4) -max
max dist (v,4), max dist (V, u)
veV
uell
Let P.P be two polytopes with their vertex sets denoted by Vp, Vy respectively. We define the Hausdorff distance H. (P.P) of the two polytopes as the Hausdorff distance of their respective vertex sets Vp, Vp. Namely,
H (P.PP) == (Vp.VP))
(4)
Clearly, the Hausdorff distance is metric of how close two polytopes are to each other. Indeed, becomes zero when the two polytopes coincide. According to this metric, the following bound on the error of tropical polynomial approximation is derived.
Proposition 4. Lei p. E Rmaa[x] [x] be two tropical polynomials and let P -Newt (p) P ENewt (p). Then,
max lp(x) - -x() S (P)P)
xEB
where B = (x E : ||x|| I <r is the hypersphere of radius and p = V +T.
The above proposition enables us to handle the more general case of neural networks with one hidden layer, that are equivalent with tropical rational mappings. By repeatedly applying Proposition 4 to each tropical polynomial corresponding to the networks, we get the following bound.
Theorem 1.
Let v, i E [xma[[] be two neural networks with architecture as in Fig. we denote the positive and negative zonotopes of u. The following bound holds.
With Pj. Q
m n (Pp.P)) (2),,))
max
[[((x) x(x)]1 p. ZEB
Remark 1. The reason we choose compute the error of the approximation on bounded hyper- sphere B is twofold. Firstly, the unbounded error of linear terms always diverges to infinity and, secondly, practice the working subspace of our dataset usually bounded, e.g. images.
NEURAL NETWORK COMPRESSION ALGORITHMS
Compression problem formulation The tropical geometry theorem on the approximation of neural networks enables to derive compression algorithms for ReLUU activated neural networks. Suppose that we want to compress the neural network Fig. by reducing the number of neurons in the hidden layer, from to K. Let us assume that the output of the compressed network is the tropical
rational map 0 = (01 ..., 3.
). Its j j-th th component may be written as (x()) = (>) (x() where using Proposition 3 the zonotopes of P/, are generated by (, by), Vi. The generators need
to be chosen in such a way that (x) Ri (x) for all x E B. Due to Theorem it suffices to find
generators such that the resulting zonotopes have H. (P,, H (z), as small as possible Vj.
We thus formulated neural network compression as geometrical zonotope approximation problem.
Our approaches Approximating zonotope with fewer generators is a problem known as zonotope order reduction (Kopetzki al. 2017). In our case approach this problem by manipulating the zonotope generators Cji (a be) Vi. Each of the algorithms presented will create a subset of altered generators that approximate the original zonotopes. Ideally, we require the approximation to hold simultaneously for all positive and negative zonotopes of each output component uy However, this is not always possible, in the case of multiclass neural networks, and it necessarily leads to heuristic manipulation. Our first attempt to tackle this problem applies the K-means algorithm to the
Dealing with the full generated zonotope would lead exponential computational overhead.
5

---

Published as a conference paper at ICLR 2022
Rlubesautt
Original network.
Original zonotopes.
(c) Resulting zonotopes. (d) Compressed network.
Figure 3: Illustration of Zonotope K-means execution. The original zonotope P is generated by
c (af', 6,) for i l,.., and the negative zonotope generated by the remaining ones 5, 7. The approximation P of P is colored in purple and generated by 2 a?"'. b.) = 1, where the first generator is the K-means center representing the generators 1, 2 of P and the second is the representative center of 3, 4. Similarly, the approximation Q of Q is colored in green and defined by the generators ē a. b.) = 3, 4 that stand as representative centers for {5, 6} and 7 respectively.
positive and negative generators, separately. This method is restricted applying to single output neural networks. Our second approach further develops this technique to multiclass neural networks. Specifically, it utilizes K-means the vectors associated with the neural paths passing from node in the hidden layer, as we define later. The algorithms we present refer to the neural network of Fig. with one hidden layer, but we may repeatedly apply them compress deeper networks.
4.1 ZONOTOPE APPROXIMATION
Zonotope K-means The first compression approach uses K-means to compress each zonotope of the network, and covers only the case of single output neural network, egg as in Fig. but with 1. The algorithm reduces the hidden layer size from to K neurons. We use the notation e; 1,....,A n for weights of the second linear layer, connecting the hidden layer with the output node. Algorithm Tis presented below and a demonstration of its execution be found in Fig.
Algorithm 1: Zonotope K-means Compression
1. Split generators into positive {c (af, b.) > 0} and negative { (a. b.) c, < 0}.
2. Apply K-means for K 2 centers, separately for both sets of generators and receive
{ & (af (af, b.): à >0 { [a7 b.) ž < 0} as output.
3. Construct the final weights. For the first linear layer, the weights and the bias which correspond the i-th neuron become the vector à a?. 6,)
4. The weights of the second linear layer are 1 for every hidden layer neuron where
a bz) occurs from positive generators and -1, elsewhere.
Proposition 5. Zonotope K-means produces compressed neural network with output satisfying
1 max [x)) T(x) < K -8mar +
(1 (1--
max Σ leill (aF. b.)
P xEB
where the total number of centers used in both K-means, 8max is the largest distance from a point its corresponding cluster center and Nmax is the maximum cardinality of cluster.
The above proposition provides an upper bound between the original neural network and the one that is approximated with Zonotope K-means. In particular, if K centers the bound of the

---

Neural Path K-means To overcome this obstacle we apply simultaneous approximation of the zonotopes. The method is called Neural Path K-means and directly applies K-means to the vectors of the weights (a.", 6; Clé .... Cmi) associated to each neuron i of the hidden layer. The name of the algorithm emanates from the fact that the vector associated to each neuron consists of the weights of Published as a conference paper at ICLR 2022
approximation error becomes 0, because then 6max = 0 and Nmax 1. Also, if K 0 the bound gets a fixed value depending on the magnitude of the weights of the linear layers.
4.2 MULTIPLE ZONOTOPE APPROXIMATION
The exact positive and negative zonotope approximation performed by Zonotope K-means algorithm has a main disadvantage: it can only be used in single output neural networks. Indeed, suppose that we want to employ the preceeding algorithm multiclass neural network. That would require 2m separate executions of K-means which are not necessarily consistent. For instance, it is possible to have Cjii 0 and C)aí components 1/ 2/2- That means that in the compression procedure of U/ the i-th neuron belongs to the positive generators set, while for 1/2. it belongs to the negative one. This makes the two compressions incompatible. Moreover, the drawback of restricting to single output only allow us to compress the final ReLU layer and not any preceeding ones.
approach the zonotopes of each output in
for some output
all the neural network paths passing from this neuron. The procedure is presented in Algorithm
Algorithm 2: Neural Path K-means Compression
1. Apply K-means for K centers to the vectors (af', b,, C.) = 1,... n,, and get the centers
(af' b,, 0% I...,
2. Construct the final weights. For the first linear layer matrix the i th row becomes aff be). while for the second linear layer matrix, the - th column becomes Č.
Null Generators Neural Path K-means does not apply compression directly to each zonotope of the network, but is rather a heuristic approach for this task. More precisely, if we focus on the set of generators of the zonotopes of output j. Neural Path K-means might mix positive and negative
generators together in the same cluster. For instance, suppose (aT be, C.T)) is the cluster center Then regarding output j. it is not necessary that Vi E I all Cjs have the same sign. Thus, the compressed positive zonotope P, might contain generators of the original negative zonotope Q; and vice versa. We will call generators Cja (al", b.) contributing to opposite zonotopes, null generators.
corresponding vectors (af", bi, C. for
Proposition 6. Neural Path K-means produces a compressed neural network with output satisfying
1 max [lu(x) o(x)]l1 & VmK52 max + m (1- Nmnxx xEB
IC [l b))l+
mmmaa (1 b:)l |[C,,)
Σ 2-1 -INN
1cyll (aT b.)ll
Nmin
where K is the number of K-means clusters, 8max the maximum distance from any point to its corresponding cluster center, N Nmav, Nmi the maximum and minimum cardinality respectively of cluster and N₂ the set of null generators with respect to output j.
The performance of Neural Path K-means is evaluated with Proposition 6 The result we deduce is analogous to Zonotope K-means. The bound the approximation error becomes zero when K approaches Indeed, for K values K, the upper bound reaches a value depending on the magnitude of the weights the linear layers together with weights corresponding to null generators.
get &max 0, Nmax and NV 0. vjj [m]. For lower
7

---

Published as a conference paper at ICLR 2022
Table Reporting accuracy of compressed networks for single output compression methods.
Percentage of
MNIST 3/5
MNIST 4/9
remaining neuroms
Smsrnis al.
Zonotope K-means
Noural Path K-means
Smyynis et al. 20:00
Zonotope K-means
Noural Path K-means
20.00
100% (Original)
99.18 + 00:27
99.38 + 0.09
99.38
+ 0.00
99.53 + 0.00
99.53 + 0.00
90.53 + 0.00
5%
99.12 1: 0.37
99.42 1: 0:07
99.25
0.04
98.99 1 0.00
99.52 1. 0.09
99.48 1 0.15
1%
99.11 :: 0.36
99.39 1: 0.05
99.32
0.03
99.01
0.09
99.46 1: 0.05
99.35 +: 0.17
0.3%
99.18 0.36
99.11 = 0.05
99.22
0.11
98.81 0.09
99.35 + 0,24
98.81 + 1.18
0.3%
99.18 0.36
99.25 +: 0.37
99.19 0.41
98.81 0.00
98.22 + 1.38
98.22 + 1.33
Table 2: Reporting theoretical upper bounds of Propositions
Percentuge remaining neurons
MNIST 3/5
MNIST 4/9
Zonotape K K-means
Neural Path K K-means
Zonotope m-aass
Neural Path K-means
100%
0.00
0.00
0.00
0.00
10%
17.07
246.74
18.85
229.37
2.5%
15.35
59.42
17.02
63.37
1%
14.79
42.22
16.44
45.58
0.5%
14.37
36.47
16.20
39.71
5 EXPERIMENTS
We conduct experiments on compressing the linear layers of convolutional neural networks. Our experiments serve as proof-of-concept and indicate that our theoretical claims indeed hold in practice. The heart of our contribution lies presenting novel tropical geometrical background for neural network approximation that will shed light for further research towards tropical mathematics.
Our methods compress the linear layers of the network layer by layer. They perform functional approximation of the original network and thus they are applicable for both classification and regression tasks. To compare them with other techniques in the literature we choose methods with similar structure, i.e. structured pruning techniques without re-training. For example, Alfarra et al. (2020) proposed a compression algorithm based on the sparsification of the matrices representing the zonotopes which served as an intuition for part of our work. However, their method is unstructured and incompatible for comparison. The methods we choose to compare are two tropical methods for single-output (Smyrnis et al. 2020) and multi-output (Smyrnis & Maragos 2020) networks, Random and L11 Structured, and modification of ThiNet (Luo et al. (017) adapted to linear layers. (Syynni al. (2020); [Smyrnis& & Maragos (2020) proposed novel tropical division framework that aimed the reduction of zonotope vertices. Random method prunes neurons according to uniform probability, while L1 prunes those with the lowest value of L1 norm of their weights. Also, ThiNet uses greedy criterion for discarding the neurons that have the smallest contribution to the output of the network.
MNIST Dataset, Pairs 3-5 and 4-9 The first experiment is performed on the binary classification tasks of pairs 3/5 and 4/9 of the MNIST dataset and so we can utilize both of our proposed methods. In Table we compare our methods with a tropical geometrical approach of Smyrnis al. 22020). Their method is based on a tropical division framework for network minimization. For fair comparison, use the same CNN with two fully connected layers and hidden layer of size 1000. According to T our techniques seem to have similar performance. They retain the accuracy of the network while reducing its size. Moreover, in Table we include experimental computation of the theoretical bounds provided by Proposition 6 We notice that the bounds decrease as the remaining weights get less. The behaviour of the bounds was expected to be incremental because the less weights we use, the compression gets worse and the error becomes larger. However, the opposite holds which means that the bounds are tighter for higher pruning rates. It is also important to mention that the bounds become ( when we keep all the weights, as expected.
MNIST and FaSHion-MNIST Datasets For the second experiment employ MNIST and Fashion-MNIST datasets. The corresponding classification is multiclass and thus Neural Path K-means may only be applied. In Table 3 we compare it with the multiclass tropical method of Smyrnis & Maragos (2020) using the same CNN architecture they do. Furthermore, in plots 4a 4b we compare Neural Path K-means with ThiNet and baseline pruning methods by compressing
8

---

Published as a conference paper at ICLR 2022
Table 3: Reporting accuracy of compressed networks for multiclass compression methods.
Pereentage of remniining neurons
MNIST
Fashion-MNDD MNIST
Smyrnis & Maragos
2020
Noural Path K-means
Smyrmis & Maragos 2020
Noural Path K K-means
100% (Original)
98.60
0.03
98.61 0.11
88.66
0.54
89.52 +: 0.19
0.28
0.32
25%
95.15
2.36
08.42 0.42
82:22 -285
86.67 + 1.12
10%
93.48 2.57
96.89 =: 0.55
80.43 3.27
86.04 :: 0.94
1.29
1998). To get better idea of how method performs in deeper architectures we provide plots 4c 4d that illustrate the performance of compressing a deep neural network with layers of size 28 28, 512, 256, 128 and 10, which we refer as deepNN. The compression is executed on all hidden layers beginning from the input and heading to the output. From Table we deduce that our method performs better than (Smyrnis & Maragos 2020p. Also, achieves higher accuracy scores and experience lower variance as shown in plots| 4a 4d Neural Path K-means, overall, seems have good performance, even competitive to ThiNet. Its worst performance occurs on low percentages of remaining weights. An explanation for this is that K-means provides a high-quality compression as long as the number of centers is not less than the number "real" clusters.
LeNet5 (LeCun al.
Asoneo
Asaroo
Ranken Stnekani
Radie Bratwed
Jadee Urarard
Sroder Gratent
Seatwed
(a) LeNet5, MNIST
(b) LeNet5, F-MNIST
(c) deopNN, MNIST
(d) deepNN, F-MNIST
Irioun Seratared
Soutardd
(3 Seuchand
Ne Put
Nawd
Ceers
(h) CIGAR-VGG, CI-
(e) AlexNet, CIFARIO (I) CIFAR- VGG, CIFARIO (g) AlexNet. CIFARI00
FARIO0
Figure 4: Neural Path K-means compared with baseline pruning methods and ThiNet. Horizontal axis shows the ratio of remaining neurons in each hidden layer of the fully connected part.
We conduct our final experiment on CIFAR datasets using CIFAR-VGE (Blalock 2020) and an altered version of AlexNet adapted for CIFAR. The resulting plots are shown in et al.
CIFAR Dataset
Fig. 4e 4h We deduce that Neural Path K-means retains good performance on larger datasets. In particu ar, in most cases it has slightly better accuracy an lower deviation than the baselines, but has worse behaviour when keeping almost zero weights.
6 CONCLUSIONS AND FUTURE WORK
We presented a novel theorem on the bounding of the approximation error between two neural networks. This theorem occurs from the bounding of the tropical polynomials representing the neural networks via the Hausdorff distance of their extended Newton polytopes. We derived geometrical compression algorithms for the fully connected parts of ReLU activated deep neural networks, while application to convolutional layers is an ongoing work. Our algorithms seem to perform well in practice and motivate further research towards the direction revealed by tropical geometry.

---

Published as a conference paper at ICLR 2022
REFERENCES
Motasem Alfarra, Adel Bibi, Hasan Hammoud, Mohamed Gaafar, and Bernard Ghanem. On the decision boundaries of deep neural networks: A tropical geometry perspective. arXiv preprint arXiv:2002.08838,, 2020.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? arXiv preprint arXiv:2003.03333, 2020.
Peter Butkovič. Max-linear systems: theory and algorithms. Springer monographs in mathematics. Springer, 2010. ISBN 978-1 98811-8996--298-8
Vasileios Charisopoulos and Petros Maragos. Morphological perceptrons: geometry and training algorithms. In International Symposium Mathemalical Morphology and Its Applications to Signal and Image Processing, pp. 3-15. Springer, 2017.
Vasileios
Charisopoulos and Petros Maragos. A tropical approach to neural networks with piecewise linear activations. arXiv preprint 18X5v:8805.0877 2018.
Raymond Cuninghame-Gres -Grenn Minimax algebra, volume 166. Springer Science & Business Media, 2012.
Nikolaos Dimitriadis and Petros Maragos. Advances in morphological neural networks: Training, pruning and enforcing shape constraints. In Proc. 46th IEEE Int'l Conf. Acoustics, Speech and Signal Processing (CCASSP-20211 Toronto, June 2021.
Richard James Duffin and Elmor L Peterson. Geometric programming with signomials. Journal of Optimization Theory and Applications, 11(1):3-35, 1973.
Branko Grünbaum. Convex polytopes, volume 221. Springer Science & Business Media, 2013.
Anna-Kathrin Kopetzki, Bastian Schürmann, and Matthias Althoff. Methods for order reduction of zonotopes. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp. 5626-5633. IEEE, 2017.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2323 1998.
Jian-Hao Luo, Jianxin Wu, and Weiyao Lin. ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression. In 2017 IEEE International Conference on Computer Vision (ICCV), pp. 5068-5076, 2017. doi: 10.1 10.1109//CC222017.....
Diane Maclagan and Bernd Sturmfels. Introduction to tropical geometry, volume 161. American Mathematical Soc., 2015.
Petros Maragos. Dynamical systems on weighted lattices: general theory. Mathematics of Control, Signals, and Systems, (9): 2017.
Petros Maragos and Emmanouil Theodosis. Multivariate tropical regression and piecewise-linear surface fitting. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3822-38228888 3826. IEEE, 2020.
Petros Maragos, Vasilcios Charisopoulos, and Emmanouil Theodosis. Tropical geometry and machine learning. Proceedings of the IEEE, 109(5):728 725, 2021. doi: 10. 1111////R...222..33025252222
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of lincar regions of deep neural networks. arXiv preprint arXiv: /402. 2014.
Georgios Smymiss and Petros Maragos. Multiclass neural network minimization via tropical newton polytope approximation. In Proc. Int'l Conf. Machine Learning. PMLR, 2020.
Georgios Smymis, Petros Maragos, and George Retsinas. Maxpolynomial division with application to neural network simplification. In /CASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4192-4196. IEFF, 2020.
10

---

Published as a conference paper at ICLR 2022
Emmanouil Theodosis and Petros Maragos. Analysis of the viterbi algorithm using tropical algebra and geometry. In 2018 IEEE 19th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), pp. 1-5. IEEE, 2018.
Emmanouil Theodosis and Petros Maragos. Tropical modeling of weighted transducer algorithms graphs. In ICASSP 2019 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8653 1153- 2019. doi: 0..1009ICAASSP22098888131
Nikos Tsilivis, Anastasios Tsiamis, and Petros Maragos. Sparsity max-plus algebra and applications in multivariate convex regression. In Proc. 46th IEEE Ini'l Conf. Acoustics, Speech and Signal Processing (ICASSP-200) 2021), Toronto, June 2021.
Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim. Tropical geometry of deep neural networks. In International Conference Machine Learning, pp. 5824-5832. PMLR, 2018.
Günter M Ziegler. Lectures on polytopes, volume 152. Springer Science & Business Media, 2012.

---

Published as a conference paper at ICLR 2022
A PROOFS FOR THE SECTION "BACKGROUND ON TROPICAL GEOMETRY" "
A.1 PROOF OF PROPOSITION
3
Proof. The first argument follows from the fact that both py. 9j are linear combinations of tropical polynomials consisting of two terms. Indeed, we compute
(x())= = Σ
Cjs max( + 0) = Σ
max(e, + tzbb,, Prop.
eyc30
Pj ENewt (max(caaa) + cjbb,, 0))
Each ENewt (max(ey:aa"x + Crib,, 0)) is line segment with endpoints 0 and (exaī, ojub.) = Cji (af" 6;). Therefore P3 is written as the Minkowski sum of line segments, which is zonotope by definition. Similarly Qj is a zonotope.
Furthermore, from the definition of the Minkowski sum, each point E Pj may be written as Enyso Vi, where each v; is a point in the segment ENewt (max x + eaali, 0j). A vertex of Pj can only occur if v. is an extreme point of ENewt (max((;;a?"> + cjub, 0)) for every which is equivalent to either V; 0 or v, = Cjs (a.", b.). This means that every vertex of P3 corresponds to subset 4 S [n] of indices i with Cja O, for which we choose v. = Cja (af b,) and for the rest it holds V, = 0. Thus,
Σ eja (a,", bi) iEI+
In the same way we derive the analogous result for the negative zonotope Q3.
Corollary 2. The geometric result concerning the structure of zonotopss can be extended max- pooling layers. For instance, max- max-pooling layer of size 2 x 2 corresponds to a polytope that is constructed as the Minkowski sum of pyramids which could stand as generalized case of zonotope.
B PROOFS FOR THE SECTION " "APPROXIMATION OF TROPICAL POLYNOMIALS"
B.1 PROOF OF PROPOSITION
Proof. Consider point x E B and assume that p(x) = a²'x + b, p(x) = c='x
x + d. Then,
b) aa'xx x + b- (u" v) (x)
x 1
p(x) p(x)= = p(x) max (a" bje,,
where (uT, .)) may be any vertex of P. Similarly, we derive
(rT
s)
( (c
x
p(x)
for any vertex (s) of P. Therefore, we may select the vertices (u" w) E (FT, E P so that their respective distances from (aT, b) and (cT, d). respectively, are minimized. Choosing them in such a way gives
pxx) p(x) < a x + b (uT, v) (x)
1 ((aT. b) (u", u))
(1)
x
(5)
$ a|( b) (uT,, w)]l
xx (+) S d (a", b), P) +1
In similar manner we deduce
f(x) f(x) 2 (rT 8) (x) - cxx d= ((FT, 8) - (c),d)) (x)
1
(6)
(1) 2 (P.,(c d)) Vr2+1
2 2-1((T, 8) - (c a))
12

---

Published as a conference paper at ICLR 2022
Notice, that for the relations (5) and (6) we used Cauchy-Schwarte inequality
xx, | |||||
||y - (x, y) |x|||
Inequality 5 holds at any point E B for some vertex (a", b) E P. therefore
p(x) x(x) p max d ((a", b). Vp) (a b/EVp
for all x E B. Similarly, we derive
p(x) p(x) 2 min Combining
-p. d (Vp, ,d) = (o",d)EVp
max
p d (Vp, (d),
(8)
(e,d)EVy
and gives
p. d (Ve, (o", d)) p(xx) -p(x)= S (n" M)V,,
max P d ((a", .b) [>p)
(c" ,dVV,
1p(x) - xxxx S p. max
max baF/
p. ((a", b) Vp)
max (ef ()VV,
p d (Vr, (c" d))
Hence, from the definition of the Hausdorff distance of two polytopes we derive the desired upper bound
1p(x) - x(x)1 S p. H P. B
max [p(x) - x(xx) S p. H. (P.P)
xE8
Remark Note that with similar proof one may replace Hausdorff distance of the two polytopes by the Hausdorff distance of their upper envelopes. This makes our theorem exact generalization of Proposition 2 However, this format is difficult to use in practice, because is computationally harder to determine the vertices of the upper envelope.
B.2 PROOF OF THEOREM 1
Proof. Notice that we may write
[|e(x) 6(x)]1
[x(x)= 0xxx)] > (x, (x)) (x, 26 (x))
j=1
1=1
(p)(x) - (x)) - (x) - 7 - Σ 1x((x) -3) + lx5(x) - (x)l
1=1
Thus from from Proposition we derive
H (Pr.P))) + (Qr, (2))
max [e((x) ūxx)[11 p. Σ x
C PROOFS AND FIGURES FOR THE SECTION "NEURAL NETWORK COMPRESSION ALGORITHMS"
C.1 ILLUSTRATION OF ZONOTOPE K-MEANS
Below present larger version of Fig. demonstrating the execution of Zonotope K-means.
13

---

Published as a conference paper at ICLR 2022
fi
62
f3
f.
Drd
f4
f2
17
fs
05
fa
f6
Eaba
b6
(o)))et..).cct.....)
(a) Original network.
(b) Minimized network.
ca(a5 b2)
(a (1)
alff. bi)
cata 64)
Cg bz)
ca(ag bb)
ea (a Aa)
Fa (a ba)
colag bi))
(nF (b)
(a Ra) cr(a7
(c) Original zonotopes
(d) Approximating zonotopes.
Figure 5: Illustration of Zonotope K-means execution. The original zonotope P is generated by
e, (a?' b,) for I...., and the negative zonotope Q generated by the remaining ones 5, 6,
The approximation of P is colored in purple and generated by ē (a") b.). i 1, where the first generator is the K-means center representing the generators 1,2 2 of P and the second is the representative center of 3, 4. Similarly, the approximation Q of Q is colored in green and defined by the generators é aa b.) = 3, 4 that stand as representative centers for {5, 6} and 7 respectively.
C.2 PROOF OF PROPOSITION 5
Proof. We remind that for the output functions holds
u(x) = p(x) q(x) o(x) = p(x) - q(xx)
From triangle inequality we deduce
|o(x) - 6(x)) Ip(x) q(x) (f(x) [(x)) lp(x) -((x) l4(x) -(x))
Prop bounds pp(x) - -(x)) and lq(x) - q(x)) are bounded by H (P.P) and H. (Q.Q) respec- tively. Therefore, it suffices get upper bound for these Hausdorff distances. Let consider any
14

---

Published as a conference paper at ICLR 2022
vertex EiEr, C: (a.. bi) of P. For the vertex P we need choose vertex E P as close to u as possible, in order to provide an upper bound for dist. 11. P) Vertex v is selected as follows.
For each 1+ we select k such that č& (aī 6x) is the center of the cluster where (af' b;) belongs to. We denote the set of such clusters by C+. where each cluster center appears only once.
Then, vertex v is constructed as v Exec. Ck (a7 bk) E P. We have that:
dist u, P)
Σ iEI+
(af
Σ REC+
ck aak bk)
ci
Σ k sETx+
Σ
(af b:)
2x aak bLe)
Ck a%. bR)
Σ Σ
(a bi)
REC iEl2
cs (a." Ds) +
Σ Σ
(a7, b))
|Tx_
REC+ iEl2
[1--
1
||3/||
|cs
[1 be)ll
[xx
[xx
KEC+ iElA
$ 10+1 8max +
(1-
Σ lca (a 6:)ll SEL+
Nmax
where denote by I++ the set of indices 4 that belong to the center E C+ and e; Th (TT bz) -ca c; (a." 6.) is the vector of the difference of the i-th generator, with its corresponding K-means cluster center.
The maximum value of the upper bound occurs when 1 contains all indices that correspond to G > 0. This value gives per bound for maxvev, d(P, v) assume
upper bound for maxue d(u, P). To compute up-
Σkec, č₁ (ag by) and consider the vertex Eier, e (a., b:) E P where 14 is the set of indices of positive generators corresponding to the union of all clusters corresponding to the centers of C+. Note that the occurring distance
Σ c (aT, b.) iEL+
Σ Th aTT bi)
AEC+
was taken into account when computing the upper bound for maxuev, d(u, P), and thus both values obtain the same upper bound. Therefore,
H P, (P.P) S K+ 8max
(1-N
Σ laa (a b:)
Nmux
VEL+
where K2 is the number of cluster centers corresponding P and 1 the indices corresponding to all positive generators of P. Similarly,
H (o. @) < K_ 6max
(1
Σ Icil || (a7 b:)
N
max
SEl_
where K_II I_ are defined in analogous way for the negative zonotope. Combining the relations gives the desired bound.
1 (H( (P.P) 7 (2.00) K. 5max (1-
1 Nmax
n
0 |x(x) x(x)] H
Ical [1 be)
15

---

Published as a conference paper at ICLR 2022
C.3 ILLUSTRATION FOR NEURAL PATH K-MEANS ALGORITHM
Below we illustrate the vectors on which K-means is applied for the multi-output case. The vectors that are compressed are consist of all the edges associated to hidden layer neuron. The corresponding edges contain all the possible neural paths that begin from some node of the input, end in some node of the output and pass through this hidden node.
f.
11
f
1/
:
fx
4/
fx
the
Figure 6: Neural Path K-means for multi-output neural network compression, In green color we highlight the weights corresponding to the -h vector used by Neural Path K-means.
In the main text we defined the null generators zonotopes that occur by the execution of Neural Path K-means. Below provide an illustration for them.
Null Generatios
Figure 7: Visualization of K-means IR where d is the input dimension and n the hidden layer size. We color points according to the j-th output component of the network. Black and white points correspond to generators of P3 and Q, respectively. White vertices in positive (brown) clusters and black vertices in negative (blue) clusters null generators regarding j-th output.
C.4 PROOF OF PROPOSITION 6
Proof. Let us first focus on a single output, say j-th output. the proof for Zonotope K-means, will bound H Pz P3 H (Q; (Q;:2;) for all [m.). From triangle inequality get
(u,(x) - (x)) < (x) 8z (x)) + lx, (x))
Any vertex of E P3 can be written as u = Exe,,- Cja (a. by) where the set of indices I satisfy Cjt > O, vi E 1s+ and thus correspond to positive generators. To choose nearby vertex from P; we perform the following. For each E Ij+ we select the center (a by ((A)T) of the cluster to where (af b, (U)T belongs, only if Zzz O. Such center only exists if eje (af. bi) is not
16

---

Published as a conference paper at ICLR 2022
null generator. Else, choose representation the vector O. Each cluster center, O, is taken into account once and the vertex Ekec,, Eik (a., bz) E Pj is formed. We derive:
max dist P3 S "CVP,
Σ Ic1
Si (af bi) -E
Esst a bx)
RCCs+
Cji (af bz)
Ezk (ak ba)
Σ
(a b:)ll
kECs+ TETyA+
i NE
Cyg (8T Bxs)
Σ E
Oys (af', bi)
Σ
le (a b.)ll
|1
kECH iElsit
ieNst
(czz + Eze) [[a?
bz) + +2o1 Ad]
Σ Σ
Ogs (a bi)
Σ
leal (aall(aa") 4:)l
|1stt|
VENg+
1egillAel
(1
1 (1-1ZArT)
<
Σ
lexel (a7, bi]l +
|1x+1
k iEls++
Lexe (a bi)ll + leall
+ Σ REC REI
Σ
Σ
Icd (a 6.)
[1
iEN+
where for all E 1ik+ the i-th vector of K-means is represented by the k-th center & Cj+, We also assumed (+) C,fi + cl0) Eji Cji + Egi and aa!"' b.) (a." bi) + As
The maximum value of the upper bound occurs when Lj+ contains all indices that correspond to Cj. > O. To compute an upper bound for maXveV,, dist (P,, v) we write the vertex as v = Exec, Czk (a7 by) E P, and choose the vertex u = Eier, Cja (aT, b.) of P, where 1 is the set of all indices corresponding to generators that belong to these clusters. As in the proof of Proposition their distance was taken account when computing the upper bound for maxueVe, dist u, P,
Hence, both obtain the same upper bound which leads to
EEsllAall + (1-
1 ) |csal | b.]l|] +
H (Pp.P)) v Σ Σ
|
kEC++ iEI
lEgal (aaf T. bi)ll + lesil ||lll
Σ
|لد [| b.)l
[1
kEC) #ETsI
NENY
where Is+ contains all indices corresponding positive Czz- Similarly, we deduce
|eg:lllaall + (1 1-124 lesal (aaf b.)1| +
(Q), < Σ Σ
1-=-1
[-p-
kEC t
J (aT be) lesal Mell
lesil
(a7 bz)
kEC,- T
VEN,
where 1z- contains all such that eje In total these bounds together with Proposition give
17

---

Published as a conference paper at ICLR 2022
1
max (x)(x) - [x)(x] z xEB
Σ Σ
|
+ (1 (1-
1
lesil (| bi]l
11
[T
kEC iEdie
|esal (a. bi)ll legal |
Σ
cgdl |I(af. bi)ll
[15al
REO; TET
KEN;
Here we used the notation Cj = CC- - (1.2.... K) and J5x is either equal to I or J depending on k Cj. Note that {ili E Tsk: h E C2} (1.2.....) \ N, E {1, 2, n), since every generator that is not null corresponds to some cluster center with the same sign. Also, using Nmax 2 | 2 Nmin follows that
max (x((x)) (x)x = xEB
|alllalll + (1 Niman
)
Ia bi)
Nmin
T
Lxyal (af b.)]l + legul Aell
leyal (a b.)
Nmin
iNN
We will compute the total cost that combines all outputs by applying the inequality
Σ
|usl
S
m
Mgl
Mgll S /m (11,,,... um))
which is a direct application of Schwar- inequality.
Together with the relations
00 8mxxs ||>il| < 8max, we get
m
m
n
esallAell (1 Nomns)
1
leyel ((a bi]l| +
max (x) (x(xxl XEB
Nmi
j=1
legal (aT b:)ll + Iogal Dell
m
ΣΣ
lexll ll (aT 6:)
Nmin
1=
mm [(0) | + (1-N Naux
1
Am... [I b:)l +
Nmin
7
vml ||o60:|| (aa , bi)ll + vmm ||C,
m +
lesel [a]] 6:)
+
Nmin
EEN
+ Vmm (1 (1- Nmax
I Vm max
Σ
IIC. (1 be) l[
i=1
Vmdmaxx
(Il(ff' be]l + (l,,,
Σ
|csal (| b.)
Nnin
j J-1
as desired.
18


Reviews:
[{"review_id": "yn_XO2mJC72", "reviewer": "Reviewer_mhFZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Strengths: \n1. This is a novel idea that has not been explored widely for structured network compression.\n2. A proper introduction to tropical geometry and the related tool has been done for non-domain experts.\n3. Illustrations are very helpful in understanding the method.\n\nWeaknesses:\n1. Comparison with non-tropical methods has not been performed.\n2. Please report the wall clock time of finding a pruned network and inference time.\n3. Without pseudo-code or code segment(s) for zonotope generators part, it is hard to reproduce the experiments. The paper will also be more accessible to non-domain experts if included. The experimental setup is very short and not enough to reproduce the results.", "summary_of_the_paper": "In this paper, a novel method of structured pruning of neural networks using tropical geometry has been proposed. The core idea is to use the tools from tropical geometry to represent a neural network as tropical polynomials and then apply k-means clustering using some distance metrics that work on such representation. \n\nThe paper contains background information on tropical geometry and related tools. Experiments have been performed on linear layers of a binary classification network trained on MNIST (3/5 and 4/9) and LeNet5 and VGG trained on MNIST and Fashion-MNIST. The proposed method is compared with $L1$ structured pruning, Smyrnis & Maragos (2020), and ThiNet (Luo et al., 2017). ", "summary_of_the_review": "I am leaning towards acceptance of the paper as it provides a very interesting and new idea. As I am not a domain expert in tropical geometry, I would wait for other expert reviewers to judge the theoretical part. If authors can provide pseudo-code or code segment that makes this paper more accessible for me leading to better understanding, then I am willing to change my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RkAH0sEPJnv", "reviewer": "Reviewer_srEK", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Pros: The proposed method seems novel and has theoretical guarantees. \n\nCons: \n- The paper is a bit hard to process for general audience in machine learning, and the topic of the work does not seem to align well with ICLR. it would be nice if the authors could explain why this work would be good match to this conference.\n- The emprical study is only performed on small scale datasets (a.k.a., MNIST and Fashion-MNIST). To compare with more modern compression techniques, experiments on more large scale datasets (e.g., CIFAR-10/100, COCO, Imagenet, etc) would better demonstrate the superiority of the proposed method.", "summary_of_the_paper": "***This is a educated guess review as the paper is outside my domain expertise.\n\nThis paper proposes a compression method using a framework based on geometrical zonotope reduction. The authors further analyze the error bounds of the proposed methods and compare its performance with modern pruning techniques. I think the main contribution of the work would be novelty of the proposed method.", "summary_of_the_review": "As this work is outside my domain of expertise, this is only an educated guess type of review, and I am willing to hear how other reviewers' opinions. \n\n===Update after the authors' response===\nThe summary of the paper in the authors' response is very helpful for the reader to grasp the main message of this work. Still, I have decided to keep my score as a) the empirical contribution is a bit limited, and as mentioned by the authors, the experiments are mainly proof-of-concept; and b) though the theoretical contribution is novel, it still needs a bit more work to justify its significance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AqKYVFRB6B4", "reviewer": "Reviewer_ayne", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "### Strengths\n1. The paper presents a mathematically solid analysis of neural networks (seen as tropical rational mappings), including a bound for the approximation error of the compressed network.\n2. The presented algorithm seems to outperform a recent tropical baseline in terms of test accuracy of the pruned network.\n3. Since the tropical viewpoint is a pretty new perspective on ReLU networks, the paper may inspire more interesting theoretical work in the area and may thus be of interest for theoretical researchers in the field.\n\n### Weaknesses/Suggestions for Improvement\n1. The CNNs used in the comparison in Figure 4 are quite old. It would be good to remove LeNet and have a more modern architecture, like a ResNet instead.\n2. The paper neither mentions the computational and storage (memory) complexity nor the runtimes of the introduced algorithm. Having a comparison between the paper’s algorithm and the one from Smyrnis & Maragos would be beneficial.\n3. Related to the previous point: All the networks used in the evaluation section are pretty small. Is it possible to run the algorithm on larger networks? Transformer networks contain only fully-connected layers, so it would be really interesting to apply the algorithm to them.\n4. The paper states that the algorithm is only applicable to fully-connected layers, but it is tested on multiple CNN architectures in the experimental section. Are only nodes from the fully-connected layers pruned in the experiments? ThiNet is a filter pruning method, so I assume that at least some of the methods also prune the convolutional layers.\n5. The paper should state in the abstract that the algorithms only apply to networks with only ReLU activations.\n6. The last sentence of the abstract says: “We deduce that our methods (1) show an improvement over relevant tropical geometry techniques, (2) advance baseline pruning methods, and (3) have competitive performance against a modern pruning technique.” I agree with point (1): The proposed method seems to work better than the tropical one from Smyrnis & Maragos. Regarding (2): I cannot see how the method advances any baseline apart from the tropical one already mentioned in (1) - neither in terms of test accuracy nor in terms of speed. Regarding (3): The most “modern” pruning technique the authors compare to is ThiNet from 2017 which is clearly not state of the art by looking at Figure 3 of the pruning survey [1]. The statements in (2) or (3) should either be backed up by more concrete evidence or removed.\n[1] What is the State of Neural Network Pruning? Blalock, Gonzalez Ortiz, Frankle, Guttag.\n\n**Minor**\n\n7. The captions to the tables should be self-explanatory. It is not clear from the captions that the figures in Table 1 and 3 are the test accuracies after pruning and that the figures in Table 2 are the left hand side of Proposition 5.\n", "summary_of_the_paper": "The paper studies neural networks from the perspective of tropical geometry and applies its theoretical results to develop a novel algorithm for the compression of neural networks with ReLU activations. The presented algorithm outperforms a previous tropical network compression algorithm in terms of the accuracy of the compressed network.", "summary_of_the_review": "The paper seems to be mathematically solid, but I see room for improvement in the experimental section. Since the experiments focus on small architectures, it is unclear to me whether the proposed algorithm can be used to compress larger networks. Since theoretical work has an important value on its own, the compression algorithm is not required to be of immediate practical interest. However, it should be made clear what the limitations of the presented method are. Judging from the presented experiments, the last sentence of the abstract may be overclaiming the experimental results. Nonetheless, the tropical geometry section seems intriguing and may be of interest to theorists.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9QKMzQ1Bk0R", "reviewer": "Reviewer_FTWK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "Questions:\n- Why do the bounds decrease as the percentage of remaining weights decreases? This is pointed out but not explained. This suggests that the bounds of Prop. 4 and 5 aren't very useful. We should expect that if we can use more weights, we can at least avoid making the error worse, but this is not borne out by the computations in Table 2.\n\n- Why was Alfarra et al. (2020) not compared to experimentally? The empirical comparison seems highly relevant. A discussion and comparison of the techniques should also be included since this work is quite related.\n\n- What is deepNN? This is in the plot captions 4c and 4d but is never explained.\n\nFeedback:\n- The experimental results on CIFAR datasets are not very convincing. Compression of networks such as AlexNet and VGG is of limited interest as such architectures have been out-of-date for years. It would be much better to evaluate on modern architectures such as ResNets, Vision Transformers, etc.\n\n- On MNIST and Fashion-MNIST, ThiNet generally does better except on Fashion-MNIST for LeNet.\n\n- For all experiments, the authors should clearly state the current SOTA method for pruning and include those results as well. While beating SOTA is not necessarily a requirement, it at least needs to be provided for comparison.\n\n- Also, the supplementary material was not submitted separately but instead included in the main PDF. While I actually prefer this approach for convenience, I believe they are supposed to be submitted separately. Also, it would be better to include the code for reproducibility.\n\nPositive feedback:\n- The background on tropical geometry is well-explained.\n\n- Theorem 2 has a very clean statement. Q: Do related statements exist in the literature?", "summary_of_the_paper": "This paper proposes to study neural network compression through the lens of zonotope reduction. They present approximation bounds for tropical polynomials based on Hausdorff distance and use this to motivate the development of two neural network compression methods. These methods are evaluated on the MNIST, Fashion-MNIST, CIFAR-10, and CIFAR-100 datasets.", "summary_of_the_review": "This paper has some interesting results (such as Theorem 2) and the techniques are interesting and seem well-motivated (although this paper is not the first to study tropical geometric neural compression). However, the bounds from Propositions 4 and 5 seem to be not practically useful, and the experimental results have limitations. Thus, I hesitate to recommend acceptance at this time. It would be great if the authors can provide clear responses to my questions above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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

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

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