Year: 2021

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.

text: 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.

heading: 1 INTRODUCTION
text: Tropical geometry (Maclagan & Sturmfels, 2015) is 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 (Rmin,∧,+), but may also refer to the max-plus semiring (Cuninghame-Green, 2012; Butkovič, 2010). In our work, we follow the convention of the max-plus semiring (Rmax,∨,+) which replaces the classical operations of addition and multiplication by max and sum respectively. These operations turn polynomials into piecewise linear functions and, thus, having direct applications in neural networks.
Tropical mathematics have a wide range of applications including game theory (Akian et al., 2012), dynamical systems on weighted lattices (Maragos, 2017), finite state transducers (Theodosis & Maragos, 2018; 2019) and convex regression (Maragos & Theodosis, 2020; Tsilivis et 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 et al. (2018) prove the equivalence of ReLU activated neural networks with tropical rational mappings. Furthermore, they show that zonotopes may serve as a computational mean for applications such as computing the bound shown in (Montúfar et al., 2014) regarding the number of the network’s linear regions. In a similar context, Charisopoulos & Maragos (2018) compute an upper bound to the number of linear regions of convolutional and MaxOut layers and propose a randomized algorithm for linear region counting. Moreover, Charisopoulos & Maragos (2017) study the morphological perceptron tropically and propose a training algorithm using the convex-concave procedure. Also, Dimitriadis & Maragos (2021) examine the training, pruning and shape properties of Morphological neural networks.
Pruning (Blalock et al., 2020) or, generally, compressing neural networks gained interest in recent years due to the surprising capability of reducing the size of a neural network without compromising performance. As tropical geometry explains the mathematical structure of neural networks, pruning may be revisited tropically. Indeed, Alfarra et al. (2020) study the lottery ticket hypothesis (Frankle & Carbin, 2018) from the tropical geometrical perspective and propose an unstructured compression algorithm based sparsifying the zonotope matrices of the network. Further, Smyrnis et al. (2020) propose a novel tropical division algorithm that applies to neural network minimization. A generalization of this method applies to multiclass networks (Smyrnis & Maragos, 2020).
Contributions In our work, we contribute to 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.
• Motivated by the geometrical bound, we derive two geometrical neural network compression methods that are based on zonotope reduction and employ K-means algorithm for clustering. Our algorithms are applied on the fully connected layers of ReLU activated neural networks.
• Our geometrical algorithms are analyzed both theoretically and experimentally. The theoretical evaluation is based on the bounding theorem of neural network approximation error by the Hausdorff distance of the zonotopes. On the experimental part, we examine the performance of our algorithms on retaining the accuracy of convolutional neural networks when applying compression on their fully connected layers.
Proofs, illustrations and experimental specifications are included in the supplementary material.

heading: 2 BACKGROUND ON TROPICAL GEOMETRY
text: We study tropical geometry from the viewpoint of the max-plus semiring (Rmax,∨,+) which is defined as the set Rmax = R ∪ {−∞} equipped with two operations (∨,+). Operation ∨ stands for max and + stands for sum. In max-plus algebra we define polynomials in the following way.
Tropical polynomials A tropical polynomial f in d variables x = (x1, x2, ..., xd) T is defined as the function f(x) = max
a∈A {aTx+ ca} (1)
where A is a finite collection of vectors in Rd and ca is the corresponding monomial coefficient in Rmax = R ∪ {−∞}. The set of such polynomials constitutes the semiring Rmax[x] of tropical polynomials. Note that each term aTx + ca corresponds to a hyperplane in Rd. We thus call the vectors a ∈ A the slopes of the tropical polynomial, and ca the respective bias. We allow slopes to be vectors with real coefficients rather than integer ones, as it is normally the case for regular polynomials. 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 a geometric tool for fields such as linear programming and optimization. They also have an important role in the analysis of neural networks. For instance, Zhang et al. (2018); Charisopoulos & Maragos (2018) show that linear regions of neural networks correspond to vertices of polytopes. Thus, the counting of linear regions reduces to a combinatorial geometry problem. In what follows, we explore this connection of tropical geometry with polytopes.
Consider the tropical polynomial defined in (1). The Newton Polytope associated to f(x) is defined as the convex hull of the slopes of the polynomial
Newt (f) := conv{a : a ∈ A} Furthermore, the Extended Newton Polytope of f(x) is defined as the convex hull of the slopes of the polynomial extended in the last dimension by the corresponding bias coefficient.
ENewt (f) := conv{(aT , ca) : a ∈ A} The following proposition computes the Extended Newton Polytope that occurs when a tropical operation is applied between two tropical polynomials. It will allow us to compute the polytope representation corresponding to a neural network’s hidden layer. Proposition 1. (Zhang et al., 2018; Charisopoulos & Maragos, 2018) Let f, g ∈ Rmax[x] be two tropical polynomials . Then for the Extended Newton Polytopes it is true that
ENewt (f ∨ g) = conv{ENewt (f) ∪ ENewt (g)} ENewt (f + g) = ENewt (f)⊕ ENewt (g)
Here ⊕ denotes Minkowski addition. In particular, for two sets A, B ⊆ Rd it is defined as A⊕B := {a+ b |a ∈ A, b ∈ B}
Corollary 1. This result can be generalized to any finite set of polynomials using induction. Example 1. Let f, g be two tropical polynomials in 2 variables, such that
f(x, y) = max(2x+ y + 1, 0), g(x, y) = max(x, y, 1)
The tropical operations applied to these polynomials give
f ∨ g = max(2x+ y + 1, 0, x, y, 1) f + g = max(3x+ y + 1, x, 2x+ 2y + 1, y, 2x+ y + 2, 1)
Fig. 1 illustrates 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, it may be used to compute the values that the polynomial attains, as Proposition 2 indicates. Proposition 2. (Charisopoulos & Maragos, 2018) Let f ∈ Rmax[x] be a tropical polynomial in d variables. Let UF (ENewt (f)) be the points in the upper envelope of ENewt (f), where upward direction is taken regarding the last dimension of Rd+1. Then for each a ∈ A there exists a linear region of f on which f(x) = aTx+ ca if and only if (aT , ca) is a vertex of UF (ENewt (f)). Example 2. Using the polynomials from Example 1 we compute a reduced representation for f ∨ g.
f ∨ g = max(2x+ y + 1, 0, x, y, 1) = max(2x+ y + 1, x, y, 1) Indeed, the remaining terms correspond to the vertices of UF (ENewt (f ∨ g)) shown in Fig. 1.

heading: 2.1 TROPICAL GEOMETRY OF NEURAL NETWORKS
text: Tropical geometry has the capability of expressing the mathematical structure of ReLU activated neural networks. We review some of the basic properties governing neural networks and introduce notation that will be used in our analysis. For this purpose, consider the ReLU activated neural network of Fig. 2 with one hidden layer.
Network tropical equations The network consists of an input layer x = (x1, ..., xd), a hidden layer f = (f1, ..., fn) with ReLU activations, an output layer v = (v1, ..., vm) and two linear layers defined by the matrices A,C respectively. As illustrated in Fig. 2 we have Ai,: = ( aTi , bi ) for the first linear layer and Cj,: = (cj1, cj2, ..., cjn) for the second linear layer, as we ignore its biases. Furthermore, the output of the i−th component of the hidden layer f is computed as
fi(x) = max
( d∑
k=1
aikxk + bi, 0 ) = max(aTi x+ bi, 0) (2)
We deduce that each fi is a tropical polynomial with two terms. It therefore follows that ENewt (fi) is a linear segment in Rd+1. The components of the output layer may be computed as
vj(x) = n∑ i=1 cjifi(x) = ∑ cji>0 |cji|fi(x)− ∑ cji<0 |cji|fi(x) = pj(x)− qj(x) (3)
Tropical rational functions Functions pj , qj are both linear combinations of {fi} with positive coefficients, which implies that they are tropical polynomials. We conclude that every output node vi can be written as a 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 a tropical rational mapping. In fact, this result holds for deeper networks, in general, as demonstrated by Theorem 1. Theorem 1. (Zhang et al., 2018) Consider a ReLU activated deep neural network as a mapping F : Rd → Rm. Then F is equivalent to a tropical rational mapping.
It is not known whether a tropical rational function r(x) admits an efficient geometric representation that determines its values {r(x)} for x ∈ Rd, as it holds for tropical polynomials with their polytopes in Proposition 2. For this reason, we choose to work separately on the polytopes of the tropical polynomials pj , qj .
Zonotopes Zonotopes are defined as the Minkowski sum of a finite set of line segments. They are a special case of polytopes that occur as a building block for our network. These geometrical structures provide a representation of the polynomials pj , qj in (3) that further allows us to build our compression algorithms. We use the notation Pj , Qj for the Extended Newton Polytopes of tropical polynomials pj , qj , respectively. Notice from (3) that for each component vj of the output pj , qj are written as linear combinations of tropical polynomials that correspond to linear segments. Thus Pj and Qj are zonotopes. We call Pj the positive zonotope, corresponding to the positive polynomial pj and Qj the negative one.
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 a 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 0 or cji ( aTi , bi ) . We summarize the above with the following extension of (Charisopoulos & Maragos, 2018). Proposition 3. Pj , Qj are zonotopes in Rd+1. For each vertex v of Pj there exists a subset of indices I+ of {1, 2, ..., n} with cji > 0, ∀i ∈ I+ such that v = ∑ i∈I+ cji ( aTi , bi ) . Similarly, a vertex u of
Qj can be written as u = ∑ i∈I− cji ( aTi , bi ) where I− corresponds to cji < 0, ∀i ∈ I−.

heading: 3 APPROXIMATION OF TROPICAL POLYNOMIALS
text: 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 a bound for the error of approximating a 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 are 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 we use to define the distance between Extended Newton Polytopes is the Hausdorff distance.
Hausdorff distance The distance of a point u ∈ Rd from the finite set V ⊂ Rd is denoted by either dist (u,V) or dist (V,u) and computed as min {‖u− v‖, v ∈ V} which is the Euclidean distance
of u from its closest point v ∈ V . The Hausdorff distanceH(V,U) of two finite point sets V,U ⊂ Rd is defined as
H (V,U) = max { max v∈V dist (v,U) ,max u∈U dist (V,u) }
Let P, P̃ be two polytopes with their vertex sets denoted by VP ,VP̃ respectively. We define the Hausdorff distanceH ( P, P̃ ) of the two polytopes as the Hausdorff distance of their respective vertex sets VP ,VP̃ . Namely, H ( P, P̃ ) := H (VP ,VP̃ ) (4)
Clearly, the Hausdorff distance is a metric of how close two polytopes are to each other. Indeed, it 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. Let p, p̃ ∈ Rmax[x] be two tropical polynomials and let P = ENewt (p) , P̃ = ENewt (p̃). Then,
max x∈B |p(x)− p̃(x)| ≤ ρ · H
( P, P̃ ) where B = {x ∈ Rd : ‖x‖ ≤ r} is the hypersphere of radius r, and ρ = √ r2 + 1.
The above proposition enable us to handle the more general case of neural networks with one hidden layer, that are equivalent with tropical rational mappings. Applying repeatedly Proposition 4 to each tropical polynomial corresponding to the networks, we get the following bound.
Theorem 2. Let v, ṽ ∈ Rmax[x] be two neural networks with architecture as in Fig. 2. With P̃j , Q̃j we denote the positive and negative zonotopes of ṽ. The following bound holds.
max x∈B ‖v(x)− ṽ(x)‖1 ≤ ρ ·  m∑ j=1 H ( Pj , P̃j ) +H ( Qj , Q̃j ) Remark 1. The reason we choose to compute the error of the approximation on a bounded hypersphere B is twofold. Firstly, the unbounded error of linear terms always diverges to infinity and, secondly, in practice the working subspace of our dataset is usually bounded, e.g. images.

heading: 4 NEURAL NETWORK COMPRESSION ALGORITHMS
text: Compression problem formulation The tropical geometry theorem on the approximation of neural networks enables us to derive compression algorithms for ReLU activated neural networks. Suppose that we want to compress the neural network of Fig. 2 by reducing the number of neurons in the hidden layer, from n to K. Let us assume that the output of the compressed network is the tropical rational map ṽ = (ṽ1, ..., ṽm). Its j−th component may be written as ṽj(x) = p̃j(x)− q̃j(x) where using Proposition 3 the zonotopes of p̃j , q̃j are generated by c̃ji(ãTi , b̃i), ∀i. The generators need to be chosen in such a way that ṽj(x) ≈ vj(x) for all x ∈ B. Due to Theorem 2 it suffices to find generators such that the resulting zonotopes haveH ( Pj , P̃j ) ,H ( Qj , Q̃j ) as small as possible ∀j.
We thus formulated neural network compression as a geometrical zonotope approximation problem.
Our approaches Approximating a zonotope with fewer generators is a problem known as zonotope order reduction (Kopetzki et al., 2017). In our case we approach this problem by manipulating the zonotope generators cji ( aTi , bi ) , ∀i, j 1. 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 vj . However, this is not always possible, as 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
1Dealing with the full generated zonotope would lead to exponential computational overhead.
The approximation P̃ of P is colored in purple and generated by c̃i
(
ãTi , b̃i
)
, i = 1, 2 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 c̃i ( ãTi , b̃i ) , i = 3, 4 that stand as representative centers for {5, 6} and 7 respectively.
positive and negative generators, separately. This method is restricted on applying to single output neural networks. Our second approach further develops this technique to multiclass neural networks. Specifically, it utilizes K-means on the vectors associated with the Neural Paths passing from a node in the hidden layer, as we define later. The algorithms we present refer to the neural network of Fig. 2 with one hidden layer, but we may repeatedly apply them to compress deeper networks.

heading: 4.1 ZONOTOPE APPROXIMATION
text: Zonotope K-means The first compression approach is geometrical and utilizes K-means, which is inherently a vector compression algorithm. Consider the case of a single output neural network, e.g as in Fig. 2 but with m = 1, and wish to reduce its hidden layer size from n to K neurons. We use the notation ci, i = 1, ..., n for weights of the second linear layer, connecting the hidden layer with the output node. Algorithm 1 is presented and an example of its execution can be found in Fig. 3.
Algorithm 1: Zonotope K-means Compression 1. Split generators into positive { ci ( aTi , bi ) : ci > 0 } and negative { ci ( aTi , bi ) : ci < 0 } .
2. Apply K-means for K2 centers, separately for both sets of generators and receive{ c̃i ( ãTi , b̃i ) : c̃i > 0 } , { c̃i ( ãTi , b̃i ) : c̃i < 0 } as output.
3. Construct the final weights. For the first linear layer, the weights and the bias which correspond to the i−th neuron become the vector c̃i ( ãTi , b̃i ) .
4. The weights of the second linear layer are set to 1 for every hidden layer neuron where c̃i ( ãTi , b̃i ) occurs from positive generators and −1, elsewhere.
Proposition 5. Zonotope K-means produces a compressed neural network with output ṽ satisfying
1 ρ ·max x∈B |v(x)− ṽ(x)| ≤ K · δmax +
( 1− 1
Nmax ) n∑ i=1 |ci|‖ ( aTi , bi ) ‖
where K is the total number of centers used in both K-means, δmax is the largest distance from a point to its corresponding cluster center and Nmax is the maximum cardinality of a cluster.
The above proposition provides an upper bound for the approximation error of resulting network of Zonotope K-means from the original one. This bound increases as we use fewer cluster centers in
K-means. If we use K ≈ n centers the error approaches 0, because then δmax → 0, Nmax → 1, and if K ≈ 0 the error gets a fixed value depending on the magnitude of the weights of the linear layers.

heading: 4.2 MULTIPLE ZONOTOPE APPROXIMATION
text: 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 to approach the zonotopes of each output in a multiclass neural network. That would require 2m separate executions of K-means which are not necessarily consistent. For instance, it is possible to have cj1i > 0 and cj2i < 0 for some output components vj1 , vj2 . That means that in the compression procedure of vj1 , the i−th neuron belongs to the positive generators set, while for vj2 , 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.
Algorithm 2: Neural Path K-means Compression 1. Apply K-means for K centers to the vectors ( aTi , bi, C T :,i ) , i = 1, ..., n, and get
the centers ( ãTi , b̃i, C̃ T :,i ) , i = 1, ...,K.
2. Construct the final weights. For the first linear layer matrix the i− th row becomes( ãTi , b̃i ) , while for the second linear layer matrix, the i− th column becomes C̃(i).
Neural Path K-means To overcome this obstacle we apply a simultaneous approximation of the zonotopes. The method is called Neural Path K-means and directly applies K-means to the vectors of the weights ( aTi , bi, c1i, ..., 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 all the neural network paths passing from this neuron. The procedure is presented in Algorithm 2.
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. 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 ( ãTk , b̃k, C̃ T :,k ) is the cluster center corresponding
to vectors ( aTi , bi, C T :,i ) for i ∈ I . Then regarding output j, it is not necessary that ∀i ∈ I all cji
have the same sign. Thus, the compressed positive zonotope P̃j might contain generators of the original negative zonotope Qj and vice versa. We will call generators cji ( aTi , bi ) contributing to opposite zonotopes, null generators.
Proposition 6. Neural Path K-means produces a compressed neural network with output ṽ satisfying
1 ρ · m∑ j=1 max x∈B |vj(x)− ṽj(x)| ≤ √ mKδ2max + √ m ( 1− 1 Nmax ) n∑ i=1 ‖C:,i‖ ∥∥(aTi , bi)∥∥+
√ mδmax Nmin n∑ i=1 (∥∥(aTi , bi)∥∥+ ‖C:,i‖)+ m∑ j=1 ∑ i∈Nj |cji| ∥∥(aTi , bi)∥∥
where K is the number of K-means clusters, δmax the maximum distance from any point to its corresponding cluster center, Nmax, Nmin the maximum and minimum cardinality respectively of a cluster and Nj 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 approximation error is eliminated as the number K of centers approaches n. This holds because for K = n we get δmax = 0, Nmax = 1 and Nj = ∅, ∀j ∈ [m]. However, as K is reduced, the upper bound reaches a value depending on the magnitude of the weights of the linear layers together with weights corresponding to null generators.

heading: 5 EXPERIMENTS
text: 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 in 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 a 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 L1 Structured, and a modification of ThiNet (Luo et al., 2017) adapted to linear layers. Smyrnis et al. (2020); Smyrnis & Maragos (2020) proposed a novel tropical division framework that aimed on 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 a 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 1, we compare our methods with a tropical geometrical approach of Smyrnis et al. (2020). Their method is based on a tropical division framework for network minimization. For fair comparison, we use the same CNN with two fully connected layers and hidden layer of size 1000. According to Table 1, our techniques seem to have similar performance. They retain the accuracy of the network while reducing its size. Moreover, in Table 2 we include experimental computation of the theoretical bounds provided by Proposition 5, 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 0 when we keep all the weights, as expected.
MNIST and Fashion-MNIST Datasets For the second experiment we 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 LeNet5 (LeCun et al., 1998). To get a better idea of how our 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 to as deepNN. The compression is executed on all hidden layers beginning from the input and heading to the output. From Table 3, we deduce that our method performs better than (Smyrnis & Maragos, 2020). Also, it achieves higher accuracy scores and experience lower variance as shown in plots 4a-4d. Neural Path K-means, overall, seems to 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 of "real" clusters.
CIFAR Dataset We conduct our final experiment on CIFAR datasets using CIFAR-VGG (Blalock et al., 2020) and an altered version of AlexNet adapted for CIFAR. The resulting plots are shown in Fig. 4e-4h. We deduce that Neural Path K-means retains a good performance on larger datasets. In particular, in most cases it has slightly better accuracy an lower deviation than the baselines, but has worse behaviour when keeping almost zero weights.

heading: 6 CONCLUSIONS AND FUTURE WORK
text: 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.

heading: A PROOFS FOR THE SECTION "BACKGROUND ON TROPICAL GEOMETRY"
text: A.1 PROOF OF PROPOSITION 3
Proof. The first argument follows from the fact that both pj , qj are linear combinations of tropical polynomials consisting of two terms. Indeed, we compute
pj(x) = ∑ cji>0 cji max(a T i x+ bi, 0) = ∑ cji>0 max(cjia T i x+ cjibi, 0) Prop. 1 ====⇒
Pj = ⊕ cji>0 ENewt ( max(cjia T i x+ cjibi, 0) ) Each ENewt ( max(cjia T i x+ cjibi, 0) ) is a line segment with endpoints 0 and ( cjia T i , cjibi ) =
cji ( aTi , bi ) . Therefore Pj is written as the Minkowski sum of line segments, which is a zonotope by definition. Similarly Qj is a zonotope. Furthermore, from the definition of the Minkowski sum, each point v ∈ Pj may be written as∑ cji>0 vi, where each vi is a point in the segment ENewt ( max(cjia T i x+ cjibi, 0) ) . A vertex of
Pj can only occur if vi is an extreme point of ENewt ( max(cjia T i x+ cjibi, 0) ) for every i which is
equivalent to either vi = 0 or vi = cji ( aTi , bi ) . This means that every vertex of Pj corresponds to a
subset I+ ⊆ [n] of indices i with cji > 0, for which we choose vi = cji ( aTi , bi ) and for the rest it holds vi = 0. Thus, v =
∑ i∈I+ cji ( aTi , bi ) In the same way we derive the analogous result for the negative zonotope Qj .
Corollary 2. The geometric result concerning the structure of zonotopes can be extended to maxpooling layers. For instance, a max-pooling layer of size 2 × 2 corresponds to a polytope that is constructed as the Minkowski sum of pyramids which could stand as generalized case of zonotope.

heading: B PROOFS FOR THE SECTION "APPROXIMATION OF TROPICAL POLYNOMIALS"
text: B.1 PROOF OF PROPOSITION 4
Proof. Consider a point x ∈ B and assume that p(x) = aTx+ b, p̃(x) = cTx+ d. Then,
p(x)− p̃(x) = p(x)− max (ãT ,b̃)∈Vp̃
{ãTx+ b̃} ≤ aTx+ b− ( uT , v )(x 1 ) where ( uT , v
) may be any vertex of P̃ . Similarly, we derive(
rT , s )(x
1
) − ( cTx+ d ) ≤ p(x)− p̃(x)
for any vertex ( rT , s ) of P . Therefore, we may select the vertices ( uT , v ) ∈ P̃ , ( rT , s ) ∈ P so that
their respective distances from ( aT , b ) and ( cT , d ) , respectively, are minimized. Choosing them in such a way gives
p(x)− p̃(x) ≤ aTx+ b− ( uT , v )(x 1 ) = (( aT , b ) − ( uT , v ))(x 1 ) ≤
≤ ∥∥(aT , b)− (uT , v)∥∥ ∥∥∥∥(x1 )∥∥∥∥ ≤ d((aT , b) , P̃)√r2 + 1 (5) In similar manner we deduce
p(x)− p̃(x) ≥ ( rT , s )(x 1 ) − cTx+ d = (( rT , s ) − ( cT , d ))(x 1 ) ≥
≥ − ∥∥(rT , s)− (cT , d)∥∥ ∥∥∥∥(x1 )∥∥∥∥ ≥ −d (P, (cT , d))√r2 + 1 (6)
Notice, that for the relations (5) and (6) we used Cauchy-Schwartz inequality
|〈x,y〉| ≤ ‖x‖‖y‖ ⇔ −‖x‖‖y‖ ≤ 〈x,y〉 ≤ ‖x‖‖y‖ Inequality (5) holds at any point x ∈ B for some vertex ( aT , b ) ∈ P , therefore
p(x)− p̃(x) ≤ ρ · max (aT ,b)∈VP
d (( aT , b ) ,VP̃ ) (7)
for all x ∈ B. Similarly, we derive
p(x)− p̃(x) ≥ min (c,d)∈VP̃
−ρ · d ( VP , ( cT , d )) = − max
(cT ,d)∈VP̃ ρ · d
( VP , ( cT , d )) (8)
Combining (7) and (8) gives
− max (cT ,d)∈VP̃
ρ · d ( VP , ( cT , d )) ≤ p(x)− p̃(x) ≤ max
(aT ,b)∈VP ρ · d
(( aT , b ) ,VP̃ ) ⇔
|p(x)− p̃(x)| ≤ ρ ·max {
max (aT ,b)∈VP
ρ · d (( aT , b ) ,VP̃ ) , max (cT ,d)∈VP̃ ρ · d ( VP , ( cT , d ))} Hence, from the definition of the Hausdorff distance of two polytopes we derive the desired upper bound
|p(x)− p̃(x)| ≤ ρ · H ( P, P̃ ) , ∀x ∈ B ⇒
max x∈B |p(x)− p̃(x)| ≤ ρ · H
( P, P̃ )
Remark 2. Note that with similar proof one may replace the Hausdorff distance of the two polytopes by the Hausdorff distance of their upper envelopes. This makes our theorem an exact generalization of Proposition 2. However, this format is difficult to use in practice, because it is computationally harder to determine the vertices of the upper envelope.
B.2 PROOF OF THEOREM 2
Proof. Notice that we may write
‖v(x)− ṽ(x)‖1 = m∑ j=1 |vj(x)− ṽj(x)| = m∑ j=1 |(pj(x)− qj(x))− (p̃j(x)− q̃j(x))|
= m∑ j=1 |(pj(x)− p̃j(x))− (qj(x)− q̃j(x))| ≤ m∑ j=1 |pj(x)− p̃j(x)|+ |qj(x)− q̃j(x)|
Thus from from Proposition 4 we derive
max x∈B ‖v(x)− ṽ(x)‖1 ≤ ρ ·  m∑ j=1 H ( Pj , P̃j ) +H ( Qj , Q̃j )

heading: C PROOFS AND FIGURES FOR THE SECTION "NEURAL NETWORK COMPRESSION ALGORITHMS"
text: C.1 ILLUSTRATION OF ZONOTOPE K-MEANS
Below we present a larger version of Fig. 5 demonstrating the execution of Zonotope K-means .
The approximation P̃ of P is colored in purple and generated by c̃i
(
ãTi , b̃i
)
, i = 1, 2 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 c̃i ( ãTi , b̃i ) , i = 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 it holds
v(x) = p(x)− q(x) , ṽ(x) = p̃(x)− q̃(x) From triangle inequality we deduce
|v(x)− ṽ(x)| = |p(x)− q(x)− (p̃(x)− q̃(x))| < |p(x)− p̃(x)|+ |q(x)− q̃(x)| Prop 4 bounds |p(x)− p̃(x)| and |q(x)− q̃(x)| are bounded by H ( P, P̃ ) and H ( Q, Q̃ ) respec-
tively. Therefore, it suffices to get an upper bound for these Hausdorff distances. Let us consider any
vertex u = ∑ i∈I+ ci ( aTi , bi ) of P . For the vertex u ∈ P we need to choose vertex v ∈ P̃ as close
to u as possible, in order to provide an upper bound for dist ( u, P̃ ) . Vertex v is selected as follows.
For each i ∈ I+ we select k such that c̃k ( ãTk b̃k ) is the center of the cluster where ci ( aTi , bi ) belongs to. We denote the set of such clusters by C+, where each cluster center k appears only once. Then, vertex v is constructed as v = ∑ k∈C+ c̃k ( ãTk b̃k ) ∈ P̃ . We have that:
dist ( u, P̃ ) ≤ ∥∥∥∥∥∥ ∑ i∈I+ ci ( aTi , bi ) − ∑ k∈C+ c̃k ( ãTk , b̃k )∥∥∥∥∥∥ ≤ ∑ k∈C+ ∥∥∥∥∥∥ ∑
i∈Ik+
ci ( aTi , bi ) − c̃k ( ãTk , b̃k )∥∥∥∥∥∥ ≤ ∑ k∈C+ ∑ i∈Ik+ ∥∥∥∥∥∥ci (aTi , bi)− c̃k ( ãTk , b̃k ) |Ik+ |
∥∥∥∥∥∥ = ∑ k∈C+ ∑ i∈Ik+ ∥∥∥∥∥ci (aTi , bi)− ci ( aTi , bi ) + εi |Ik+ |
∥∥∥∥∥ ≤ ∑ k∈C+ ∑ i∈Ik+ [( 1− 1 |Ik+ | ) |ci| ∥∥(aTi , bi)∥∥+ ‖εi‖|Ik+ | ]
≤ |C+| · δmax + ( 1− 1
Nmax )∑ i∈I+ |ci| ∥∥(aTi , bi)∥∥
where we denote by Ik+ the set of indices i ∈ I+ that belong to the center k ∈ C+ and εi = c̃k ( ãTk , b̃k ) − ci ( aTi , bi ) 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 I+ contains all indices that correspond to ci > 0. This value gives us an upper bound for maxu∈P d(u, P̃ ). To compute an upper bound for maxv∈VP̃ d(P,v) we assume v = ∑ k∈C+ c̃k ( ãTk b̃k ) and consider the vertex∑
i∈I+ ci ( aTi , bi ) ∈ P where I+ 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∥∥∥∥∥∥ ∑ i∈I+ ci ( aTi , bi ) − ∑ k∈C+ c̃k ( ãTi , b̃i )∥∥∥∥∥∥ was taken into account when computing the upper bound for maxu∈VP d(u, P̃ ), and thus both values obtain the same upper bound. Therefore,
H ( P, P̃ ) ≤ K+ · δmax + ( 1− 1
Nmax )∑ i∈I+ |ci| ∥∥(aTi , bi)∥∥
where K+ is the number of cluster centers corresponding to P̃ and I+ the indices corresponding to all positive generators of P . Similarly,
H ( Q, Q̃ ) ≤ K− · δmax + ( 1− 1
Nmax ) ∑ i∈I− |ci| ∥∥(aTi , bi)∥∥
where K−, I− are defined in analogous way for the negative zonotope. Combining the relations gives the desired bound.
1 ρ · |v(x)− ṽ(x)| ≤ H
( P, P̃ ) +H ( Q, Q̃ ) ≤ K · δmax + ( 1− 1
Nmax ) n∑ i=1 |ci| ∥∥(aTi , bi)∥∥
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 a 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.
In the main text we defined the null generators of zonotopes that occur by the execution of Neural Path K-means. Below we provide an illustration for them.
C.4 PROOF OF PROPOSITION 6
Proof. Let us first focus on a single output, say j−th output. As in the proof for Zonotope K-means, we will boundH ( Pj , P̃j ) ,H ( Qj , Q̃j ) for all j ∈ [m]. From triangle inequality we get
|vj(x)− ṽj(x)| ≤ |pj(x)− p̃j(x)|+ |qj(x)− q̃j(x)| Any vertex of u ∈ Pj can be written as u = ∑ i∈Ij+ cji ( aTi , bi ) where the set of indices Ij+ satisfy cji > 0, ∀i ∈ Ij+ and thus correspond to positive generators. To choose a nearby vertex from P̃j we perform the following. For each i ∈ Ij+ we select the center ( ãTk b̃k C̃ (k)T )
of the cluster to where ( aTi bi C (i)T ) belongs, only if c̃jk > 0. Such a center only exists if cji ( aTi , bi ) is not a
null generator. Else, we choose as representation the vector 0. Each cluster center, or 0, is taken into account once and the vertex ∑ k∈Cj+ c̃jk ( ãk, b̃k ) ∈ P̃j is formed. We derive:
max u∈VPj
dist ( u, P̃j ) ≤ ∥∥∥∥∥∥ ∑ i∈Ij+ cji ( aTi , bi ) − ∑ k∈Cj+ c̃jk ( ãTk , b̃k )∥∥∥∥∥∥ ≤ ∑
k∈Cj+
∥∥∥∥∥∥ ∑
i∈Ijk+
cji ( aTi , bi ) − c̃jk ( ãTk , b̃k )∥∥∥∥∥∥+ ∑
i∈Nj+
|cji| ∥∥(aTi , bi)∥∥
≤ ∑
k∈Cj+ ∑ i∈Ijk+ ∥∥∥∥∥∥cji (aTi , bi)− c̃jk ( ãTk , b̃k ) |Ijk+| ∥∥∥∥∥∥+ ∑ i∈Nj+ |cji| ∥∥(aTi , bi)∥∥
≤ ∑ k∈C ∑ i∈Ijk+ ∥∥∥∥∥cji (aTi , bi)− (cji + εji) [( aTi , bi ) + λi ] |Ijk+| ∥∥∥∥∥+ ∑ i∈Nj+ |cji| ∥∥(aTi , bi)∥∥
≤ ∑
k∈Cj+ ∑ i∈Ijk+ [ |εji|‖λi‖ |Ijk+| + ( 1− 1 |Ijk+| ) |cji| ∥∥(aTi , bi)∥∥]+ + ∑
k∈Cj+ ∑ i∈Ijk+
[ |εji| ∥∥(aTi , bi)∥∥+ |cji| ‖λi‖ |Ijk+| ] + ∑
i∈Nj+
|cji| ∥∥(aTi , bi)∥∥
where for all i ∈ Ijk+ the i−th vector of K-means is represented by the k−th center k ∈ Cj+. We also assumed C̃(i) = C:,i + ε(i) ⇒ c̃ji = cji + εji and ( ãTi , b̃i ) = ( aTi , bi ) + λi.
The maximum value of the upper bound occurs when Ij+ contains all indices that correspond to cji > 0. To compute an upper bound for maxv∈VP̃j dist (Pj ,v) we write the vertex v as
v = ∑ k∈Cj+ c̃jk ( ãTk b̃k ) ∈ P̃j and choose the vertex u = ∑ i∈Ij+ cji ( aTi , bi ) of Pj where Ij+ is the set of all indices corresponding to generators that belong to these clusters. As in the proof of Proposition 5, their distance was taken into account when computing the upper bound for maxu∈VPj dist ( u, P̃j ) . Hence, both obtain the same upper bound which leads to
H ( Pj , P̃j ) ≤ ∑
k∈Cj+ ∑ i∈Ijk+ [ |εji|‖λi‖ |Ijk+| + ( 1− 1 |Ijk+| ) |cji| ∥∥(aTi , bi)∥∥]+ + ∑
k∈Cj+ ∑ i∈Ijk+
[ |εji| ∥∥(aTi , bi)∥∥+ |cji| ‖λi‖ |Ijk+| ] + ∑
i∈Nj+
|cji| ∥∥(aTi , bi)∥∥
where Ij+ contains all indices corresponding to positive cji. Similarly, we deduce
H ( Qj , Q̃j ) ≤ ∑
k∈Cj− ∑ i∈Ijk− [ |εji|‖λi‖ |Ijk−| + ( 1− 1 |Ijk−| ) |cji| ∥∥(aTi , bi)∥∥]+ + ∑
k∈Cj− ∑ i∈Ijk−
[ |εji| ∥∥(aTi , bi)∥∥ |cji| ‖λi‖ |Ijk−| ] + ∑
i∈Nj−
|cji| ∥∥(aTi , bi)∥∥
where Ij− contains all i such that cji < 0. In total these bounds together with Proposition 4 give
1 ρ ·max x∈B |vj(x)− ṽj(x)| ≤ ∑ k∈Cj ∑ i∈Ijk [ |εji|‖λi‖ |Ijk| + ( 1− 1 |Ijk| ) |cji| ∥∥(aTi , bi)∥∥]+ + ∑ k∈Cj ∑ i∈Ijk [ |εji| ∥∥(aTi , bi)∥∥+ |cji| ‖λi‖ |Ijk| ] + ∑ i∈Nj |cji| ∥∥(aTi , bi)∥∥
Here we used the notation Cj = Cj+ ∪ Cj− = {1, 2, ...,K} and Ijk is either equal to Ijk+ or Ijk− depending on k ∈ Cj . Note that {i|i ∈ Ijk, k ∈ Cj} = {1, 2, ..., n} \ Nj ⊆ {1, 2, ..., n}, since every generator that is not null corresponds to some cluster center with the same sign. Also, using Nmax ≥ |Ijk| ≥ Nmin, it follows that
1 ρ ·max x∈B |vj(x)− ṽj(x)| ≤ n∑ i=1 [ |εji|‖λi‖ Nmin + ( 1− 1 Nmax ) |cji| ∥∥(aTi , bi)∥∥]+ +
n∑ i=1
[ |εji| ∥∥(aTi , bi)∥∥+ |cji| ‖λi‖ Nmin ] + ∑ i∈Nj |cji| ∥∥(aTi , bi)∥∥
We will compute the total cost that combines all outputs by applying the inequality m∑ j=1 |uj | 2 ≤ m  m∑ j=1 |uj |2 ⇔ m∑ j=1 |uj | ≤ √ m ‖(u1, ..., um)‖
which is a direct application of Cauchy-Schwartz inequality. Together with the relations ‖ε(i)‖ < δmax, ‖λi‖ < δmax, we get
1 ρ · m∑ j=1 max x∈B |vj(x)− ṽj(x)| ≤ m∑ j=1 n∑ i=1 [ |εji|‖λi‖ Nmin + ( 1− 1 Nmax ) |cji| ∥∥(aTi , bi)∥∥]+ +
m∑ j=1 n∑ i=1
[ |εji| ∥∥(aTi , bi)∥∥+ |cji| ‖λi‖ Nmin ] + m∑ j=1 ∑ i∈Nj |cji| ∥∥(aTi , bi)∥∥
≤ n∑
i=1
[√ m ∥∥ε(i)∥∥ ‖λi‖ Nmin + ( 1− 1 Nmax )√ m ‖C:,i‖ ∥∥(aTi , bi)∥∥ ] +
+ n∑ i=1
[√ m ∥∥ε(i)∥∥ ∥∥(aTi , bi)∥∥+√m ‖C:,i‖ ‖λi‖
Nmin
] +
m∑ j=1 ∑ i∈Nj |cji| ∥∥(aTi , bi)∥∥
≤ √ mKδ2max + √ m ( 1− 1
Nmax ) n∑ i=1 ‖C:,i‖ ∥∥(aTi , bi)∥∥+
√ mδmax Nmin n∑ i=1 (∥∥(aTi , bi)∥∥+ ‖C:,i‖)+ m∑ j=1 ∑ i∈Nj |cji| ∥∥(aTi , bi)∥∥
as desired.

heading: D EXPERIMENTAL SPECIFICATIONS
text: Experimental Setup For our code’s execution we used Google’s Colab GPU machines.
Training specifications Small CNNs such as the custom CNNs from Smyrnis et al. (2020); Smyrnis & Maragos (2020) and LeNet5 LeCun et al. (1998) were trained using Adam optimizer with learning rate 10−3 for 20 epochs. Larger CNNs CIFAR-VGG and modified AlexNet were trained with frozen
convolutional layers with SGD at learning rate 10−2, momentum 0.9 and weight decay 5 · 10−4 for 28 epochs. For each experiment we train from start 5 distinct models. The reported accuracy percentages are taken as the average across these 5 models. Standard deviation is provided both for tabular reports and on figure plots as error bars.
Pruning specifications Our algorithms are not deterministic, since K-means has random initialization. To ensure better performance each algorithm was repeated multiple times and the pruned model with the best validation accuracy was provided as output. In particular, we repeat each algorithm’s execution 20 on the experiment of comparison to Smyrnis & Maragos (2020), 1 for the CIFAR experiment, and 5 for the rest of the experiments.

Review summaries:
***This is a educated guess review as the paper is outside my domain expertise.  This paper proposes a compression method using a framework based on geometrical zonotope reduction. The authors further analyze the error bounds of the proposed methods and compare its performance with modern pruning techniques. I think the main contribution of the work would be novelty of the proposed method.

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.

In this paper, a novel method of structured pruning of neural networks using tropical geometry has been proposed. The core idea is to use the tools from tropical geometry to represent a neural network as tropical polynomials and then apply k-means clustering using some distance metrics that work on such representation.   The paper contains background information on tropical geometry and related tools. Experiments have been performed on linear layers of a binary classification network trained on MNIST (3/5 and 4/9) and LeNet5 and VGG trained on MNIST and Fashion-MNIST. The proposed method is compared with $L1$ structured pruning, Smyrnis & Maragos (2020), and ThiNet (Luo et al., 2017).