Tropical Expressivity of Neural Networks

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 12:24:41

Abstract: We propose an algebraic geometric framework to study the expressivity of linear activation neural networks.  A particular quantity that has been actively studied in the field of deep learning is the number of linear regions, which gives an estimate of the information capacity of the architecture.  To study and evaluate information capacity and expressivity, we work in the setting of tropical geometry---a combinatorial and polyhedral variant of algebraic geometry---where there are known connections between tropical rational maps and feedforward neural networks. Our work builds on and expands this relation to capitalize on the rich theory of tropical geometry to characterize and study various architectural aspects of neural networks. Our contributions are threefold: we provide a novel tropical geometric approach to selecting sampling domains among linear regions; an algebraic result allowing for a guided restriction of the sampling domain for network architectures with symmetries; and an open source library to analyze neural networks as tropical Puiseux rational maps. We provide a comprehensive set of proof-of-concept numerical experiments demonstrating the breadth of neural network architectures to which tropical geometric theory can be applied to reveal insights on expressivity characteristics of a network. Our work provides the foundations for the adaptation of both theory and existing software from computational tropical geometry and symbolic computation to deep learning.

Main paper: 
 introduction: 
 Deep learning has become the undisputed state-of-the-art for data analysis and has wide-reaching prominence in many fields of computer science, despite still being based on a limited theoretical foundation. Developing theoretical foundations to better understand the unparalleled success of deep neural networks is one of the most active areas of research in modern statistical learning theory.Expressivity is one of the most important approaches to quantifiably measuring the performance of a deep neural network-such as how they are able to represent highly complex information implicitly in their weights and to generalize from data-and therefore key to understanding the success of deep learning.Tropical geometry is a reinterpretation of algebraic geometry that features piecewise linear and polyhedral constructions, where combinatorics naturally comes into play [e.g., 1, 2, 3]. These characteristics of tropical geometry make it a natural framework for studying the linear regions in a neural network-an important quantity in deep learning representing the network information capacity [4, 5, 6, 7, 8, 9, 10] . The intersection of deep learning theory and tropical geometry is a relatively new area of research with great potential towards the ultimate goal of understanding how and why deep neural networks perform so well. In this paper, we propose a new perspective for measuring and estimating the expressivity and information capacity of a neural networks by developing and expanding known connections between neural networks and tropical rational functions in both theory and practice.Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.Related Work. Tropical geometry has been used to characterize deep neural networks with piecewise linear activation functions, including two of the most popular and widely-used activation functions, namely, rectified linear units (ReLUs) and maxout units. The first explicit connection between tropical geometry and neural networks establishes that the decision boundary of a deep neural network with ReLU activation functions is a tropical rational function [11] . Concurrently, it was established that the maxout activation function fits input data by a tropical polynomial [12] . These works considered neural networks whose input domain is Euclidean, which was recently developed to incorporate tropically-motivated input domains, in particular, the tropical projective torus [13] . Most recently, tropical geometry has been used to construct convolutional neural networks that are robust to adversarial attacks via tropical decision boundaries [14] .Contributions. In this paper, we establish novel algebraic and geometric tools to quantify the expressivity of a neural network. Networks with a piecewise linear activation compute piecewise linear functions where the input space is divided into areas; the network computing a single linear function on each area. These areas are referred to as the linear regions of the network; the number of distinct linear regions is a quantifiable measure of expressivity of the network [e.g., 5]. In our work, we not only study the number of linear regions, we aim to understand their geometry. The main contributions of our work are the following.• We provide a geometric characterization of the linear regions in a neural network via the input space: estimating the linear regions is typically carried out by random sampling from the input space, where randomness may cause some linear regions of a neural network to be missed and result in an inaccurate information capacity measure. We propose an effective sampling domain as a ball of radius R, which is a subset of the entire sampling space that hits all of the linear regions of a given neural network. We compute bounds for the radius R based on a combinatorial invariant known as the Hoffman constant, which effectively gives a geometric characterization and guarantee for the linear regions of a neural network.• We exploit geometric insight into the linear regions of a neural network to gain dramatic computational efficiency: when networks exhibit invariance under symmetry, we can restrict the sampling domain to a fundamental domain of the group action and thus reduce the number of samples required. We experimentally demonstrate that sampling from the fundamental domain provides an accurate estimate of the number of linear regions with a fraction of the compute requirements.• We provide an open source library integrated into the Open Source Computer Algebra Research (OSCAR) system [15] which converts both trained and untrained arbitrary neural networks into algebraic symbolic objects. This contribution then opens the door for the extensive theory and existing software on symbolic computation and computational tropical geometry to be used to study neural networks.The remainder of this paper is organized as follows. We provide an overview of the technical background on tropical geometry and its connection to neural networks in Section 2. We then devote a section to each of the contributions listed above-Sections 3, 4, and 5, respectively-in which we present our theoretical contributions and numerical experiments. We close the paper with a discussion on limitations of our work and directions for future research in Section 6. 
technical background: 
 In this section, we give basic definitions from tropical geometry required to write tropical expressions for neural networks.Algebraic geometry studies geometric properties of solution sets of polynomial systems that can be expressed algebraically, such as their degree, dimension, and irreducible components. Tropical geometry is a variant of algebraic geometry where the polynomials are defined in the tropical semiring, R = (R∪{∞}, ⊕, ⊙) where the addition and multiplication operators are given by a⊕b = max(a, b)and a ⊙ b = a + b, respectively. Define a ⊘ b := a -b.Using these operations, we can write polynomials as m a m T m , where a i are coefficients, T ∈ R, and where the sum is indexed by a finite subset of N n . In our work, we consider the following generalizations of tropical polynomials. where p, q are tropical Puiseux polynomials.Tropical (Puiseux) polynomials and rational maps induce functions from R n → R, which take a pointx ∈ R n to the number obtained by substituting T = x in the algebraic expression and performing the (tropical) operations. It is important to note that tropically, the formal algebraic expression contains strictly more information than the corresponding function, since different tropical expressions can induce the same function.We now overview and recast the framework of [11] , which establishes the first explicit connection between tropical geometry and neural networks, in a slightly different language for our results.As in [11] , the neural networks we will focus on are fully connected multilayer perceptrons with ReLU activation, i.e., functionsR n → R m of the form σ • L d • σ • L i-1 • • • • • L 1 where L i : R ni-1 → R niis an affine map and σ(t) = max{t, 0}. For the remainder of this paper, we use the term "neural network" to refer solely to these. We will always assume that the weights and biases of our neural networks are rational numbers. From a computational perspective, this is not a serious restriction since this is sufficient to describe any neural network with weights and biases given by floating point numbers. We refer to the tuple [n, n 1 , . . . , n d-1 , m] as the architecture of the neural network.One of the key observations intersecting tropical geometry and deep learning is that, up to rescaling of rational weights to obtain integers, neural networks can be written as tropical rational functions [11, Theorem 5.2] . From a more computational perspective, it is usually preferable to avoid such rescaling and simply work with the original weights. The proof of Theorem 5.2 in [11] can directly be adapted to show that any neural network can be written as the function associated to a tropical Puiseux rational map. In their language, this corresponds to saying that any neural network is a tropical rational signomial with nonnegative rational exponents.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We provided a detailed discussion of the limitations or our work, both computational and theoretical in Section 6.• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
sampling domain selection using a hoffman constant: 
 Estimating the number of linear regions of a neural network typically proceeds by sampling points from the input domain and counting the memberships of these points. To guarantee that membership is exhaustive, we seek a sampling domain as a sufficiently large ball so that all linear regions are intersected. At the same time, we would like for the ball to be as small as possible to guarantee efficient sampling. We are thus searching for the smallest ball from which we can sample in such a way that all linear regions are intersected. Given the polyhedral geometry of tropical Puiseux rational maps, it turns out that the radius of this smallest ball that we seek is closely related to the Hoffman constant, which is a combinatorial invariant.Our contribution in this section is a definition of a Hoffman constant of a neural network; we demonstrate its relationship to the smallest sampling ball and propose algorithms to compute its true value and lower and upper bounds.In simpler terms, the Hoffman constant can be expressed for a matrix as follows. Let A be an m × n where x + = max{x, 0} is applied coordinate-wise [16] . The constant H(A) is called the Hoffman constant of A.The Hoffman Constant for Tropical Polynomials and Rational Functions. Let f : R n → R be a tropical Puiseux polynomial and let U = {U 1 , . . . , U m } be the set of linear regions of f . Let f (x) = a i1 x 1 + . . . + a in x n + b i occur on the region U i . Further, let A = [a ij ] m×n be the matrix of coefficients in the expression of f over U. The linear region U i is defined by the following inequalitiesEQUATIONIn matrix form, ( 2) is equivalent toEQUATIONwhere 1 is a column vector of all 1's; a i is the ith row vector of A; and b is a column vector of all b i . Denote A Ui := A -1a i and b Ui := b i 1 -b. Then the linear region U i is captured by the linear system of inequalities A Ui x ≤ b Ui .Definition 3.1. Let f : R n → R be a tropical Puiseux polynomial. The Hoffman constant of f is defined asH(f ) = max Ui∈U H( A Ui ).Care needs to be taken in defining a Hoffman constant for a tropical Puiseux rational map: We want to avoid having all linear regions defined by systems of linear inequalities, since there exist linear regions which are not convex. To do so, we consider convex refinements of linear regions induced by intersections of linear regions of tropical polynomials.Definition 3.2. Let p ⊘ q be a difference of two tropical Puiseux polynomials. Let A p (respectively A q ) be the m p × n (respectively m q × n) matrix of coefficients for p (respectively q). The Hoffman constant of p ⊘ q isEQUATION)Let f be a tropical Puiseux rational map. Then the Hoffman constant of f is defined as the minimal Hoffman constant of H(p ⊘ q) over all possible expressions of f = p ⊘ q.Given the correspondence between neural networks and tropical Puiseux rational maps, the Hoffman constant is well-defined for any neural network and may be computed from the geometry and combinatorics of its linear regions.For a neural network whose tropical Puiseux rational map is f : R n → R, let U = {U 1 , . . . , U m } be the collection of all linear regions. For any x ∈ R n , define the minimal effective radius of f at x asR f (x) := min{r : B(x, r) ∩ U i ̸ = ∅, U i ∈ U}where B(x, r) is the ball of radius r centered at x. That is, R f (x) is the minimal radius such that the ball B(x, r) intersects all linear regions. It is the smallest required radius of sampling around x in order to express the full classifying capacity of the neural network f .We start with the following lemma which relates the minimal effective radius to the Hoffman constant when f is a tropical Puiseux polynomial.Lemma 3.3. Let f be a tropical Puiseux polynomial and x ∈ R n be any point, thenEQUATIONIn particular, we are interested in studying when R m and R n are equipped with the ∞-norm. In this case, the minimal effective radius can be related to the Hoffman constant and function value of f = p ⊘ q. For a tropical Puiseux polynomial p(x) = max 1≤i≤mp {a i x + b i }, let p(x) = min 1≤j≤mq {a j x + b j } be its min-conjugate.Proposition 3.4. Let f = p ⊘ q be a tropical Puiseux rational map. For any x ∈ R n , we haveEQUATIONThe PVZ Algorithm. In [17] , the authors proposed a combinatorial algorithm to compute the precise value of the Hoffman constant for a matrix A ∈ R m×n , which we refer to as the Peña-Vera-Zuluaga (PVZ) algorithm and sketch its main steps here.Definition 3.5. A set-valued map Φ : R n → R m assigns a set Φ(x) ⊆ R m . The map is surjective if Φ(R n ) = ∪ x Φ(x) = R m . Let A ∈ R m×n .For any J ⊆ {1, 2, . . . , m}, let A J be the submatrix of A consisting of rows with indices in J. The set J is called A-surjective if the set-valued mapΦ(x) = A J x + {y ∈ R J : y ≥ 0} is surjective.Notice that A-surjectivity is a generalization of linear independence of row vectors. We illustrate this observation in the following two examples.Example 3.6. If J is such that A J is full-rank, then J is A-surjective, since for any y ∈ R J , there exists x ∈ R n such that y = A J x.Example 3.7. Let A = 1 m×n be the m × n matrix whose entries are 1's. For any subset J of {1, . . . , m} and for any y ∈ R J , let x ∈ R n such that i x i ≤ min{y j , j ∈ J}. Then y -A J x ≥ 0.Thus any J is A-surjective.The PVZ algorithm is based on the following characterization of Hoffman constant. EQUATIONwhereEQUATION)This characterization is particularly useful when R m and R n are equipped with the ∞-norm, since the computation of ( 8) reduces to a linear programming (LP) problem. The key problem is how to maximize over all A-surjective sets. To do this, the PVZ algorithm maintains three collections of sets F, I, and J where during every iteration: (i) F contains J such that J is A-surjective; (ii) I contains J such that J is not A-surjective; and (iii) J contains candidates J whose A-surjectivity will be tested.To detect whether a candidate J ∈ J is surjective, the PVZ algorithm requires solvingEQUATIONIf the optimal value is positive, then J is A-surjective, and J is assigned to F and all subsets of J are removed from J . Otherwise, the optimal value is 0 and there isv ∈ R J + such that A ⊤ J v = 0. Let I(v) = {i ∈ J : v i > 0}and assign I(v) to I. Let Ĵ ∈ J be any set containing I(v). Replace all such Ĵ by sets Ĵ\{i}, i ∈ I(v) which are not contained in any sets in F. The implementation used in our paper directly uses the MATLAB code provided by [17] .Lower and Upper Bounds. A limitation of the PVZ algorithm is that during each loop, every set in J needs to be tested, and each test requires solving a LP problem. Although solving one LP problem in practice is fast, a complete while loop calls the LP solver many times.Here, we propose an algorithm to estimate lower and upper bounds for Hoffman constants. An intuitive way to estimate the lower bound is to sample a number of random subsets from {1, . . . , m} and test for A-surjectivity. This method bypasses optimizing combinatorially over S(A) of Asurjective sets and gives a lower bound of Hoffman constant by Proposition 3.8.To get an upper of Hoffman constant, we use the result from [18] .Theorem 3.9. [18, Theorem 4.2] Let A ∈ R m×n . Let D(A) be a set of subsets of J ⊆ {1, . . . , m} such that A J is full rank. Let D * (A) be the set of maximal elements in D(A). Then the Hoffman constant measured under 2-norm is bounded byEQUATIONwhere ρ(A) is the smallest singular value of A.Using the fact that ∥ • ∥ 1 ≥ ∥ • ∥ 2 , and the characterization from ( 8), we see that the upper bound also holds when R m and R n are equipped with the ∞-norm. However, enumerating all maximal elements in D(A) is not an improvement over enumerating A-surjective sets from a computational perspective.Instead, we will retain the strategy as in lower bound estimation to sample a number of sets from {1, 2, . . . , m} and approximate the upper bound by (10) . We verify this approach via synthetic data.The experiments are relegated to the Appendix.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? 
symmetry and the fundamental domain: 
 In this section, we study a geometric characterization of the sampling domain for networks exhibiting symmetry. This corresponds to invariant neural networks.The notion of invariance for a neural network describes when a manipulation of the input domain does not affect the output of the network. The manipulations we consider here are group actions. Given an invariant neural network, we can then define a sampling domain that takes into account the effect of the group action.Definition 4.2. Let G be a group acting on R n . A subset ∆ ⊆ R n is a fundamental domain if it satisfies two following conditions: (i) R n = g∈G g • ∆; and (ii) g • int(∆) ∩ h • int(∆) = ∅ for all g, h ∈ G, g ̸ = h.The fundamental domain of a group G therefore provides a periodic tiling of R n by acting on ∆.This is very useful in the context of numerical sampling for neural networks which are invariant under some symmetry, since it means we can sample from a smaller subset of the input domain with a guarantee to find all the linear regions in the limit. This allows us, in principle, to be able to use far fewer samples while maintaining the same density of points.Theorem 4.3. Let f : R N → R be a tropical rational map invariant under group G. Let ∆ ⊆ R N be a fundamental domain of G. Suppose L is the set of linear regions. Define the following two setsU c := {A ∈ U : A ⊆ ∆} U n := {A ∈ U : A ∩ ∆ ̸ = ∅}. Then |G||U c | ≤ |U | ≤ |G||U c | + A∈Un\Uc |G| |G A | .where |G A | is the size of the stabilizer of A.This gives us a method for estimating the total number of linear regions from sampling in the fundamental domain using multiplicity, which we discuss next.To demonstrate the potential performance improvements in numerical sampling exploiting symmetry in the network architecture, we consider permutation invariant neural networks inspired by deep sets [19] . Our numerical sampling approach is inspired by very recent work in this area [20] . Lemma 4.4 ([19] ). An m × m matrix W acting as a linear operator of the form W = λI m×m + γ(1 T 1), where λ, γ ∈ R is permutation equivariant, meaning W P x = P W x for any x ∈ R m , so it commutes with any permutation matrix.Using a weight matrix of this form, we can construct permutation invariant neural networks by setting the bias to 0, applying a ReLU activation after multiplication by W , and then summing. In this case, the network is invariant under the group action S n , so the fundamental domain is the set of points with increasing coordinates, i.e., ∆ = {(x 1 , . . . , x n ) :x 1 ≥ x 2 ≥ . . . ≥ x n }. This splits R n into n!tiles, so we have a clear and significant advantage in restricting sampling to the fundamental domain.Note, however, that it is important to address the multiplicities of symmetric linear regions correctly:If a given Jacobian of shape n × 1 has no repeated elements, this means it is contained in the interior of some group action applied to the fundamental domain. This means there are n! total linear regions with this Jacobian. If, on the other hand, there are repeated coefficients in a given Jacobian J, we consider the set C(J) of counts of repeated elements. For example, forJ = [1, 1, 0], C(J) = (2, 1).Then the multiplicity of a given Jacobian is given by mult(J) = n! c∈C(J) c! .Using this multiplicity calculation we can efficiently estimate the number of linear regions while reducing the number of point samples by a factor of n!. This provides a dramatic gain in sampling efficiency.In Figure 1 , we present the results when Algorithm 2 is run with R = 10, N = 10, M = 50. These results show that the fundamental domain estimate performs well for low dimensional inputs but appears to overcount linear regions as n increases. Despite divergence, there is still utility in this metric because we are often more concerned with obtaining an upper bound on the expressivity of a neural network than an exact figure and the fundamental domain estimate does not undercount the number of linear regions. 
symbolic neural networks: 
 Here, we present the details on our practical contribution of a symbolic representation of neural networks as a new library integrated into OSCAR [15] .We present an algorithm that can compute the linear regions of any tropical Puiseux rational function.Intuitively, we do this by computing the linear regions of the numerator and denominator, and then considering intersections of such regions and how they fit together. Thus, a first step is to understand how the computation of linear regions works for tropical Puiseux polynomials. The key to our approach will be to exploit the polyhedral connection of tropical geometry and recast the problem in the language of polyhedral geometry. This, among other things, will allow us to make use the extensive polyhedral geometry library in OSCAR [15] for implementation.One important upshot from this study is that there is a strong connection between the number of linear regions of a tropical Puiseux rational function and the number of monomials that appear in its algebraic expression. Note, however, that the two are independent, in the sense that two Puiseux rational functions could have the same number of linear regions but different numbers of (nonzero) monomials, and conversely, the same number of monomials and a different number of linear regions.For instance, computing the number of linear regions requires some combinatorial data about the intersections of the polyhedra defined by monomials.First, we need to know how to compute the linear regions of tropical polynomials. Let P =as function R k → R, P is given by max n {a n + n 1 x 1 • • • + n k x k } .It follows that the linear regions of P are precisely the sets of the formS n = {x ∈ R n | a m + m 1 x 1 • • • + m k x k ≤ a n + n 1 x 1 • • • + n k x kfor all m ̸ = n} . For any set U on which P is linear, we write L(P, U ) for the corresponding linear map. This gives usEQUATIONWe now rewrite (11) using polyhedral geometry. Recall that a polyhedron in R k is a set of the formP (A, b) = {x ∈ R k | Ax ≤ b}.We claim that each linear region is a polyhedron: For a fixed index n, define the matrix A n to be the (N -1) × k matrix whose rows are the vectors m -n, where m ranges over the support of the coefficients of P (ordered lexicographically) and b n to be the vector with entries a n -a m . Then S n = P (A n , b n ). This gives us a way to encode the computation of the linear regions of tropical Puiseux polynomials using polyhedral geometry. As a direct consequence, intersections of linear regions of tropical Puiseux polynomials are also polyhedra. In particular, there are algorithms from polyhedral geometry for determining whether such polyhedra are realizable. One of the key observations given by our algorithm is that the linear regions of tropical Puiseux rational maps are almost given by k-dimensional intersections of the linear regions of the numerator and the denominator. Indeed, note that if U is a linear region of p and V a linear region of q, then we have L(U ∩ V, p ⊘ q) = L(U, p) -L(V, q). The only issue that arises is that there might be some repetition in the L(U ∩ V, p ⊘ q) as U ranges over the linear regions of p and V over the linear regions of q. In particular, linear regions of p ⊘ q might end up corresponding to unions of such U ∩ V .Determining the linear regions of a neural network may be approached numerically or symbolically.The numerical approach exploits the fact that linear regions of a neural network correspond to regions where the gradient is constant. Thus, to estimate the number of linear regions, we can evaluate the gradient on a sample of points (e.g., a mesh) in some large box [-R, R] n . For sufficiently large R and a sufficiently dense sample of points, we get an accurate estimate. The symbolic approach, on the other hand, exploits the connection between neural networks and tropical Puiseux rational maps.Indeed, we can symbolically compute a Puiseux rational map that represents the neural network and then compute the number of linear regions using the approach outlined in section 5.1.To compare each method, we ran the computations on smaller networks with varying sizes to compare run times and precision. For the symbolic approach, we generate 20 neural networks with random weights for each architecture and then compute the tropical Puiseux rational function associated to each neural network and compute the linear regions using Algorithm 3.For the numerical approach, we also work with synthetic data and generate 1000 neural networks with random weights for each architecture. We then estimate the number of linear regions in a box of size [-10, 10] n and sample 1000 points from this domain.In both cases, we use He initialization for the weights, i.e., we generate weights with distributionN (0, 2 √ d )where d is the input dimension. The data we obtain in this manner is summarized in Tables 10 and 11 . For the symbolic approach, we also track the number of nonzero monomials to compare this quantity with the number of linear regions. For networks with 3 layers, we find the numerical estimate to be quite close, but for 4 it seems to diverge. This could be because in the numerical approach, we are only counting the number of unique Jacobians that can be found in the domain. A situation could arise where the same linear function is disconnected and hence counted twice by the symbolic approach but only once for the numerical approach.The main observations from our experimental study are as follows. The numerical approach is faster, but offers no guarantee of precision: When running the computation for a given R and mesh grid, there seems to be no easy way of determining whether we have indeed hit all the linear regions or whether we have obtained an accurate estimate of the arrangements of these regions. It is possible to either overestimate or underestimate the number of linear regions. In particular, there is a priori no obvious way to select the parameters. We found the symbolic approach to be more precise, but slower. In general, the number of monomials seems to be far larger than the number of linear regions, which contradicts the intuition of Figure 2 .Both algorithms suffer from the curse of dimensionality: in the case of the numerical approach, the number of samples in a meshgrid grows exponenially with respect to the dimension. In the case of the symbolic approach, calculations with polytopes seem to scale poorly with dimension and with the complexity of the neural network.6 Discussion: Limitations & Directions for Future ResearchIn this paper, we set up a framework to interpret and analyzed the expressivity of neural networks using techniques from polyhedral and tropical geometry. We demonstrated several ways in which a symbolic interpretation can often enable computational optimizations for otherwise intractable tasks and provided new insights into the inner workings of these networks. To the best of our knowledge, ours is the first work to provide practical tropical geometric theory and algorithms to numerically compute and analyze the expressivity of a neural network both in terms of inherent neural network quantities as well as tropical geometric quantities.Despite the theoretical and practical advancement of tropical deep learning that our work offers, it is nevertheless subject to limitations, which we now discuss and which inspire directions for future research.Experimental Limitations. The curse of dimensionality is a common theme in deep learning, and our work is unfortunately no exception. The methods introduced in this paper are quite fast for small enough networks, but scale poorly with dimension and more complex architectures.We note that the main computational bottlenecks of the Puiseux rational function associated with a neural network are the implementation of fast multivariate Puiseux series operations. Our current computations rely on a custom implementation of this type of operation, and one potential avenue for improvement would be using such methods once they have been implemented in OSCAR [15] .For the computation of linear regions, both the numerical and symbolic approaches suffer from the curse of dimensionality. For instance, the numerical approach requires sampling on a mesh grid in a box of the form [-R, R] n where n is the input dimension. In particular, the number of points needed is proportional to the volume, which scales exponenially in n. Similarly, the symbolic approach relies on the computation of the Puiseux rational function associated with a neural network and polytope computations, both of which are challenging computational problems in higher dimensions.Most of our computations rely on carrying out some elementary computations many times. Thus, another avenue of improvement for this would be to parallelize.Much of what we are studying are basically framed as a combinatorial optimization problem, which are known to be difficult. In particular, computing the Hoffman constant is equivalent to the Stewart-Todd condition measure of a matrix and both quantities are NP-hard to compute in general cases [17, 21] .Further studying and understanding where and how symbolic computation algorithms can be made more efficient, e.g., by parallelization, would make our proposed approaches more applicable to larger neural networks. Our work effectively proposes a new intersection of symbolic computation and deep learning, so there remains infrastructure to set up to make methods from these two fields compatible.We ran the final computations on NVIDIA GeForce RTX 3090 GPUs. Sample a random integer K.Sample a random subset J from {1, . . . , m} of size K.Solve (9). Let t be the optimal value; 6:if t > ϵ then 7:J is surjective. Update H L = max{H L , 1 t }; 8:Compute the minimal singular value of ρ(A J ); Create a permutation invariant model σ with input dimension n.Sample N n points in the cube with side length R centered at the origin. Note that the number of points in the sample grows exponentially with the input dimension n.Compute the Jacobian matrices of the network at each point, round to 10 decimal place to avoid numerical errors, remove duplicates, and count the number of unique Jacobians.Sample N n n! points from the fundamental domain of R n intersected with the sampling cube.Compute the unique Jacobians similarly as for the regular sampling.Sum the multiplicities of each Jacobian to get an estimate of the total number of linear regions.Record the ratio of the fundamental domain estimate to the regular estimate. return The average ratio across M models.Proof. The polyhedra defined byA p A q -1 a ip a jq x ≤ b ip 1 -b p b jq 1 -b qform a convex refinement of linear regions of f . Letres ip,jq (x) := A p A q -1 a ip a jq x - b ip 1 -b p b jq 1 -b qdenote the residual of x to the polyhedron. We haveR f (x) ≤ H(p ⊘ q) max{∥res ip,jq (x) + ∥ ∞ : 1 ≤ i p ≤ m p ; 1 ≤ j q ≤ m q }.Algorithm 3 Linear regions of tropical Puiseux rational functions Require: Tropical Puiseux polynomials p, q in n variables. 1: Compute the linear regions U 1 , . . . , U l of p, and set L i = L(p, U i ).2: Compute the linear regions V 1 , . . . , V m of q, and set S j = L(q, V j ).3: Compute the pairs (i, j) such that U i ∩ V j has dimension n 4: for (i, j) such that U i ∩ V j has dimension n do 5:Compute the linear map T ij = L i -S j 6: Set S to be the set of all T ij 7: for T ∈ S do 8:Compute the set I(T ) indices (i, j) such that T = T ij .Compute the set C(T ) of connected components of (i,j)∈I(T ) Create a model with architecture σ and initialise weights and biases using He inialisation.U i ∩ V j return T ∈S C(T ).Sample N points in the cube with side length R centered at the origin.Compute the Jacobian matrices of the network at each point.Round the Jacobians matrices to 5 decimal places to avoid floating point errors.Remove duplicates and count the number of unique Jacobians. return The average number of linear regions.∥res ip,jq (x) + ∥ ∞ = A p x + b p -1(a ip x + b ip ) A q x + b q -1(a jq x + b jq ) + ∞ = max k,ℓ (A p x + b p ) k -(a ip x + b ip ), (A q x + b q ) ℓ -(a jq x + b jq ), 0 = max p(x) -(a ip x + b ip ), q(x) -(a jq x + b jq ), 0 Therefore, max ip,jq ∥res ip,jq (x)∥ ∞ = max ip,jq p(x) -(a ip x + b ip ), q(x) -(a jq x + b jq ), 0 = max p(x) -min ip {a ip x + b ip }, q(x) -min jq {a jq x + b jq }, 0 = max p(x) -p(x), q(x) -q(x)which proves (6) .Proof. From the definition of minimal effective radius we haveR f (x) = min{r : B(x, r) ∩ U i ̸ = ∅, U i ∈ U} = min{r : d(x, U i ) ≤ r, U i ∈ U} = max{d(x, U i ) : U i ∈ U}.For each linear region U i characterized byA Ui x ≤ b Ui , by (1), d(x, U i ) ≤ H( A Ui )∥( A Ui x-b Ui ) + ∥.Passing to maximum we have R f (x) = max Ui∈U d(x, U i ) ≤ max Ui∈U H( A Ui ) max Ui∈U ∥( A Ui x -b Ui ) + ∥ = H(f ) max Ui∈U ∥( A Ui x -b Ui ) + ∥.We illustrate the computation of Hoffman constant of tropical Puiseux rational map on synthetic data.We generate tropical Puiseux rational maps by randomly generating two tropical Puiseux polynomials p and q. Specifically, suppose p has m p monomials and q has m q monomials. We construct an m p × n matrix A p and an m q × n matrix A q by uniformly sampling entries from [0, 1]. We then form the matrix defined by (4). We then compute the exact Hoffman constant using the PVZ algorithm and estimate its lower bound and approximate its upper bound by our proposed algorithm. We record the computation time and the number of calls to solve the LP problem in the whole loop.In the experiment we take different values of m p , m q , n and B. For each of the parameters we repeat all computation for 8 times. The true Hoffman constants, lower bounds, upper bounds, and the computation time per linear region can be found in Table 1 ,2,3, and the number of iterations of the PVZ algorithm and average time to solve LP during each iteration can be found in Table 4 ,5.6.From the tables we can see that computing the true Hoffman constants requires testing surjectivity and solving over thousands LP problems, which costs a lot of time. Although the lower bounds and approximate upper bounds can be loose, the computational time is much faster for lower bounds and upper bounds, which implies its potential to apply for real data applications.Tables 8 and 9 summarise the outcomes of the experiments on the computation of linear regions for tropical Puiseux rational functions. For a fixed number of variables n var and number of monomials n monomials , we generate n samples random Puiseux rational functions by picking random coefficients and exponents using Julia's inbuilt random number generation functions, where both the numerator and the denominator have n monomials monomials. We then compute the number of linear regions for each of these rational functions and take the average over our all the samples that were generated. Justification: Each of the three contributions mentioned in the abstract has a whole section devoted to it, including theoretical results and experiments. We also provided an in-depth discussion of the limitations of our work in Section 6.• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We provided all the code that is necessary to reproduce the experimental results, together with instructions on how to run this.• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: The paper gives some details about how the synthetic data used for experiments was generated. Moreover, we also provide the code that is necessary to run the experiments.• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). 
experiment statistical significance: 
 • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: The appendix provides some detail on the type of compute that was used (type of GPU, memory), as well was runtimes for each experiment.• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: We are carefully read through the code of ethics and to the best of our knowledge the contributions in this paper do not violate it in any way.• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: The work does not have any obvious harmful applications or any potential negative societal impact.• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The work does not pose any such risks.• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: Where we have used or been inspired by previous work we have made sure that we have legal permission to use it and have clearly cited it in each case.• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. • The paper should discuss whether and how consent was obtained from people whose asset is used.• At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: This work did not involve crowdsourcing nor research with human subjects.• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.• For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.n a n ⊙ x n where by x n we meanx n1 1 ⊙ • • • ⊙ x n kk and powers are taken in the tropical sense. Then 
 
 Appendix:  


Decision: The submission presents a tropical geometry perspective of neural networks aimed at identifying theoretical and practical frameworks to count linear regions and better understand their geometry. 

Reviewers praised the clarity and novel consideration of certain concepts from tropical geometry in context of neural nets, found the technical content accessible and not unnecessarily convoluted, and the proofs and concepts clearly presented. However, concerns were raised in regard to the provided experiments, particularly the correctness of the estimated bounds; the computational complexity of the proposed methodology and thus limited applicability (also acknowledged in the submission); and that, although well motivated and interesting, the paper lacked technical depth. This latter concern extended to aspects related to rigour in tropical geometry and positioning of the work in the context of existing literature.

The authors contended that the primary aim of the article was to present a proof of concept and that they did not make any significant efforts to optimise certain parts, that experiments focused on smaller networks to facilitate clear analysis. They offered to include larger experiments in a revision as well as other improvements including additional references. They acknowledged that a table in their original submission had mistakes and that some computations had used thresholds producing incorrect results. Authors also contended that the conciseness of their proofs should not be mistaken for lack of technical depth, although their argumentation focused on other aspects, particularly implications and applications, and integration with OSCAR. After the rebuttal and discussions, the reviewers were not sufficiently persuaded to change their reject recommendations and offered suggestions how the article could be improved.

After carefully considering the reviews, responses, discussion, and also reading the article, I found that the article is written in a clear way and presents an interesting exposition of concepts like the Hoffman constant which appears promising. However, in my assessment, the scope of technical innovations and implications is limited and currently not sufficiently well developed to warrant publication at NeurIPS. This is in agreement with some of the opinions expressed by the reviewers. Therefore, I recommend to reject the submission. The discussion identified several points of possible improvement, particularly greater care with numerical experiments.

Reviews: review: paper_summary: paper_summary: This work provides a geometric characterization of the linear regions in a neural network via the input space. Although linear regions are usually estimated by randomly sampling from the input space, stochasticity may cause some linear regions of a neural network to be missed. This paper proposes an effective sampling domain as a ball of radius R and computes bounds for the radius R based on a combinatorial invariant known as the Hoffman constant, which gives a geometric characterization for the linear regions of a neural network. Further, the paper exploits geometric insight into the linear regions of a neural network to gain dramatic computational efficiency when networks exhibit invariance under symmetry. Lastly, the paper provides code for converting trained and untrained neural networks into algebraic symbolic objects, useful for precisely the kinds of analysis this paper performs.
strength_weakness: strength_weakness: 1. My greatest concern in this paper stems from the experiments for upper and lower bound estimation for Hoffman constants given in Tables 1, 2, and 3 in the appendix. It seems the experimental upper and lower bounds computed there do not actually bound the true Hoffman constant. I understand that the upper bound may be loose due to the way it is estimated, but the lower bound should always be below the true Hoffman constant, as per my understanding. Yet for, say, the first of eight computations in table 1, the lower bound $H_L$ is $0.5460$, which is clearly above the true value of $H$, given to be $0.3298$. For that example, the upper bound $H^U$ is given to be $0.2081$, which is clearly not above the true value. This pattern continues, and the lower and upper bounds for the Hoffman constants seem to fluctuate somewhat arbitrarily around the true Hoffman constants, which is concerning. I am currently assuming that there is some kind of mistake with these experimental values and would like a clarification from the authors regarding this.

2. Due to the curse of dimensionality, this method for estimating the expressiveness of neural networks can only be applied to simple neural networks in practice. This is very apparent due to the way the numerical approach requires sampling on a mesh grid in an $n$-dimensional box (but is also true for the symbolic approach, that relies on the computation of the Puiseux rational function associated with a neural network, which becomes increasingly quite hard in higher dimensions). To the credit of the authors, they are up-front about this limitation, but this does significantly hinder the applicability of the presented results.
questions: questions: My questions to the authors are listed below:

1. Why do the computed upper and lower bounds for the Hoffman constants in Tables 1, 2, and 3, seem wrong? Is there a mistake with this computation, and if so, can you provide the correct tables so that I may judge how tight/loose the bounds are? I elaborated on this in the first weakness of the "Weaknesses" section above. 

### Additional Comments and Minor Corrections

The writing in this paper is quite good and the material is very clearly introduced. Nonetheless, I would like to give a non-exhaustive list of minor corrections below:

L103, 105: Please use \citet for in-text citations. This happens several times, but I will only mention it once.

L349: "to interpret and analyzed" -> "to interpret and analyze"
limitations: limitations: The authors adequately discuss the limitations of their work in Section 6.
paper_summary: paper_summary: The paper studies the expressivity of neural networks as captured by the number of linear regions using tools from tropical geometry. There are three main contributions, two of which are theoretical and the other is about open source library that allows the analysis of neural networks as Puiseux rational maps. 

The first theoretical contribution is that they propose a new approach for selecting sampling domains among the linear regions and the second is a way to prune the search space for network architectures with symmetries.

Prior work on tropical geometry and deep neural nets have analyzed ReLU and maxout units. Contrary to prior works, this work makes an effort to understand the geometry of the linear regions not just their number. To do so the authors propose a way of sampling the domain that leads to more accurate estimates compared to random sampling from the input space, which is a previously used alternative that can result in some missed linear regions and hence in inaccurate estimates about the information capacity of the neural network. This insight about sampling, allows then the authors to reduce the time to estimate the linear regions of special types of neural networks that exhibit some symmetry. This essentially reduces the number of samples needed and they experimentally verify their results.

Finally, the authors release OSCAR an open source library.
strength_weakness: strength_weakness: -the main weakness I see in the paper is that, though well-motivated and interesting, it lacks technical depth. For example, there is essentially one main result stated as Theorem 4.3, and some intermediate results stated as Lemma 3.3 and Proposition 3.4. On the one hand, the latter two are simple observations about Puiseux polynomials, and on the other hand the proof of the Theorem 4.3 is not more than 3 lines (as shown in Appendix C). As such, I believe it is a nice transfer of ideas from tropical geometry to neural networks, but given that the connection was already there and used in prior works more than 10 years back, I don't think the better sampling algorithm is solid enough.
questions: questions: -Would it be possible perhaps to strengthen the paper by proving depth-width separation results analogous to Telgarsky "Benefits of Depth in Neural Networks" using your techniques?

-Is there some notion of optimality associated with your sampling algorithm? Could it be further improved?
limitations: limitations: See weaknesses.
paper_summary: paper_summary: This study investigates the expressive power of deep fully-connected ReLU networks (or a piecewise linear function) from the perspective of tropical geometry. The number of linear regions gives an estimate of the information capacity of the network, and the authors provide a novel tropical geometric approach to selecting sampling domains among linear regions.
strength_weakness: strength_weakness: - The proposed algorithms suffer from the curse of dimensionality
questions: questions: - The authors mention in the abstract that the number of linear regions is an estimate of information capacity of the network. I need more clarifications, because this fact bridges tropical geometry and machine learning study.

- (minor) l.133: I was a bit confused here. Is the matrix-vector product $Ax$ in the sense of tropical algebra or in the ordinal sense? What does a “vector-inequality” $Ax \le b$ mean?
limitations: limitations: it is discussed in Section 6
paper_summary: paper_summary: This paper proposes new methods to count the number of linear regions in neural networks by viewing them as tropical Puiseux rational maps. By computing their Hoffman constant, the authors are able to identify a sampling radius which ensures that all the network’s linear regions will be intersected. They use this insight to propose algorithms for counting the number of linear regions for both invariant and traditional networks.
strength_weakness: strength_weakness: The main weakness of the work, in my opinion, can be summarized in the following points:

- the connections to tropical geometry and group theory are not rigorous beyond the point of simple notational fixes
- the motivation for the work and how it fills gaps in the existing literature is unclear, and
- the effective utility of the approach is not convincingly demonstrated by the theory or experiments.

**Rigor of tropical and group theories**

I believe this point is the biggest weakness of the paper. From the perspective of tropical algebra, vectors and polynomials live in $\bar{\mathbb{R}}$. The authors mention $\bar{\mathbb{R}}$ in line 87, but then this is never used in most of their work. This might seem as a notational fix, but it is not, as it introduces problems in virtually every single result in the paper. This first becomes a real issue in (4), where maximums are taken over, potentially, $\infty$. How is it guaranteed that (4) exists in the context of tropical algebra? This is a recurring problem that appears in (5), (6), and (7). Another important issue at the intersection of group theory and tropical algebra is how groups are defined. Semirings, by construction, are objects that do not admit additive inverses. This means that, if one wants to define groups on such structures, great care needs to be taken as to how groups are defined, how they act on vector spaces, and what groups are actually permissible in this context.

From the perspective of group theory how is the group action defined? How do the group elements act on vectors in tropical spaces? Group representations $\rho: G \to \operatorname{GL}$ require the concept of an invertible matrix, however that concept is ill-defined in tropical vector spaces.

(Moreover, the authors define incorrectly $\bar{\mathbb{R}}$. The infinity element needs to be the identity element of tropical addition: if one opts to use the max-plus semiring, $-\infty$ should be used. If we use the min-plus semiring, $\infty$ should be used. However, this is a notational fix.) 

**Motivation**

In terms of motivation it is unclear how the work is related to the existing works. There have been countless results on the number of linear regions of neural networks, and quite a few results using tropical geometry at that. What void in the literature does this paper fill? The related work paragraph lists some of the works in tropical geometry, but doesn’t highlight where these works come short and how the proposed manuscript fills that void. Moreover, there is no discussion of why the existing works on linear counting that do not utilize tropical geometry are also not able to handle the presented context.

**Effective utility**

At the end of the day, I’m not sure I understand what the utility of the method is. Ignoring here the questions on motivation, the goal is to make deep learning more interpretable. However, the authors’ experiments diverge when input sizes are larger than $6$ and the networks are deeper than $4$ layers. Modern deep learning uses input sizes significantly larger than $100$ and decade old networks are deeper than $10$ layers. So what effectively are we learning about deep networks?

Unfortunately, there are some larger issues with the method and experiments. Beyond the concerns from the perspective of tropical geometry, we have zero guarantees about the upper and lower bounds of the Hoffman constant. There is no asymptotic analysis on the sample complexities of the bounds, no analyses about tightness or optimality, or even, at the very least, an analysis that the bounds are not vacuous or trivial. On line 272 the authors claim that even though their estimate diverges, that’s acceptable because frequently we’re interested is an upper bound on expressivity. However, how can we guarantee that there the number of regions is not undercounted (I couldn’t find a proof)? For that statement to be true the bound needs to be tight, but from their own experiments (Tables 1 and 2), the true $H$ ends up being larger than the upper bound, which is used to calculate the radius and eventually the radius. Obviously, then, the computed bounds are not representative: then, since the estimate Hoffman constant is not accurate and the algorithm diverges, what essentially do we gain?
questions: questions: I have some more fine-grained comments and questions.

**Major**

There is a recurring discussion about massively improving efficiency. However, that efficiency is when compared against what? There is not a single comparison against existing works, so the improvement is over what? Regardless, as the authors discuss in Algorithm 2 and in the section about limitations, there is an *exponential* scaling with the number of inputs. Even if the authors introduce a factorial reduction for invariant networks, they require exponential sampling, which leads to no real improvement, as is evident by their really small parameter values and large running times. How where these sample numbers chosen in the first place? I couldn’t find any asymptotic analysis that guarantees with high probability that the whole space will be sampled with such a number of samples. Overall, the computational complexity of the approach is prohibitive, as it required $N^n$ Jacobian computations, which is nigh impossible for parameter values found in real networks.

There is a significant lack of attribution to prior work. In the introduction, textbooks on tropical geometry are cited as well as papers on the counting of linear regions. However, when the intersection of tropical geometry and machine/deep learning is discussed, zero references are provided, whereas the field has been fairly active in the last 5 years with dozens of highly cited papers. Similarly, in the related works section the final citation has no connection to the presented paper beyond being at the intersection of tropical geometry and machine learning. However, there are much older and much more well-cited papers to include as general references on the field, both as general reviews and as specific applications (tropical compression of neural networks comes to mind). As a final comment on this train of thought, would the authors like to elaborate on line 352? Specifically, both [11] and [12] analyze the expressivity of neural networks using tropical geometric quantities (through zonotopes and Newton polytopes). How do the authors view their work as the first in doing that?

As a last major comment, there is another lack of preciseness, however to a lesser extend as to what I mentioned above. There is a recurring discussion about one method being more precise than the other: however, what does that mean? Preciseness is never defined, and it’s not straightforward how the authors compute the ground truth of the number of linear regions. For example, how can we say that Table 10 is more precise than Table 11? In a similar vain, there are underlying assumptions that are not discussed or communicated. For example, what are the assumptions of 4.3 from the perspective of group theory? Does the theorem work for any, possibly infinite group? Similarly, there are constraints in Definition 3.5 that are not communicated. The way A-surjectivity is introduced, it is required that $m < n$. However, that makes explicit assumptions about the networks that can be analyzed, which is never communicated or considered.

**Minor**

There are some minor things that are unclear in the text. For example, it is unclear what Section 5.2 refers to. Is it a table or a plot, and which one? In Theorem 4.3 $\mathcal{L}$ is mentioned which is never used or defined, and it is unclear what the term bias is referring to in 256 (I’m assuming $\lambda$?). Table 1 (and others) are lacking headers and it’s impossible to understand what the different columns represent. Finally, the term maximal elements is used with respect to sets of sets. However, sets lack canonical order, so it’s unclear what “maximal element” means in this context.

Overall the notation is good, but at a few points it is confusing. Matrix indices usually refer to columns, not rows, which can lead to confusion and the choice of $\rho$ for the singular values (over the universally accepted $\sigma$) can hurt readability. In 329 the input dimension is denoted by $d$, in contrast to the rest of the manuscript and the notation $\min\{y_j, j\in J\}$ is not consistent with set theory nor optimization (and also in conflict with the authors own notation, for example, in (10) or 295. Finally, $S_n$ is used as the permutation group but also as a set in 295.
limitations: limitations: I think the authors accurately identify the main limitations of their approach, which relates to the large computational complexity.

Comments: title: post-rebuttal reviewer comment
Rebuttal Response
comment: Thank you for taking the time to carefully review our work and for providing your thoughtful feedback. We appreciate your acknowledgment of the improvements we’ve made in addressing the concerns regarding the Hoffman constants. While we respect your decision to maintain your initial rating, we believe it is important to note that despite satisfactorily addressing the concerns raised, this has not influenced the final evaluation. This process and outcome diminishes the impact that constructive dialogue is intended to have on the review process.
This being said, we have found this process to be an invaluable opportunity to further refine our research, and we remain committed to making any necessary improvements. We sincerely thank you again for your constructive comments and the time invested in reviewing our work and engaging in discussion.
### Lack of attribution
Thank you for your detailed feedback. We were happy to see that we have found common ground concerning which additional references to include in our revision. We appreciate the opportunity to clarify our position regarding the inclusion and placement of references related to the intersection of tropical geometry and machine/deep learning.

We agree with your observation that the section titled Tropical Geometry does not contain specific references to works applying tropical geometry to study machine learning, except in the context of expressivity. This is because the focus of that section is to *introduce* tropical geometry and its relevance to deep learning.

The references to works that explore the intersection of tropical geometry and machine learning more broadly are indeed included in the Related Work section, which follows immediately after. We intended the Related Work section to provide a comprehensive view of the current literature, including those intersections. While we understand that this might be interpreted differently, we hope this clarifies our intent.

We recognize that both the Tropical Geometry and Related Work sections touch on the intersection of tropical geometry and machine learning. However, we believe our initial structure effectively distinguishes between the introduction of the concept and the detailed review of the relevant literature. Thus, the statement that "when the intersection of tropical geometry and machine/deep learning is discussed, zero references are provided" is imprecise, as this could easily be interpreted as applying to both paragraphs taken together. Both sections indeed discuss this intersection, with more references provided in the latter. 

Finally, we feel it is important to address the characterization of this issue as a "major concern'' (it is mentioned in the strongly-worded statement as a "significant lack of attribution to prior work''). While we acknowledge the importance of proper citation placement, **we believe this is a minor structural issue rather than a substantive flaw in our work**, since the citations *did* appear in our work, placed subsequently in the text, though, we concede, in different sections. We are fully committed to improving the clarity and structure of our paper and we are happy to include the agreed-upon additional references, but we also want to emphasize that this issue does not, in our view, diminish the overall contribution or rigor of our work.  This is the reason why, to us, it is "such a point of contention.''
We would once again like to thank the reviewer for taking the time to reply promptly to our previous responses. 

### Group actions
In light of the reviewer's response, we believe there has been a misunderstanding in our convention, and we would like to clarify the following points:
1. In section 4.1, we work with *arbitrary* group actions, in  the sense that we are assuming we have been given a group $G$ together with an action map $G \times \mathbb{R}^n \to \mathbb{R}^n$ that satisfies the properties we mentioned in our previous response.
2. In section 4.2, we work with *permutation invariant neural networks*, i.e., networks that are invariant under permutations of their inputs. In other words, we are working with a specific (and standard!) group action of the symmetric group $S_n$ on $\mathbb{R}^n$ called the *natural permutation representation*, given by $\sigma \cdot (x_1, \dotsc, x_n) = (x_{\sigma(1)}, \dotsc, x_{\sigma(n)})$ (i.e., the $i$-th coordinate of $x$ becomes the $\sigma(i)$-th coordinate of $\sigma \cdot x$). This is a linear representation and can thus also be defined in terms of a representation of $S_n$.

We would also like to point out that the formulas the reviewer provided in their response appear to be definitions of *examples* of actions rather than definitions of the *notion* of an action, which is what we are working with. For example, the first formula given by the reviewer appears to be taken from equation (1) in Dehmamy et al. (2021); this defines an *specific* action on the space of functions $f : \mathcal{S} \to \mathbb{R}^n$ where $\mathcal{S}$ is some topological space. Notice that the formula given is also already assuming we are given a group action on the space $\mathcal{S}$.

### Tropical geometry
We acknowledge that the second main contribution by Zhang et al. (2018) is the use of theory from tropical geometry to derive an analytic upper bound on the number of linear regions.  The first is a representation of neural networks in terms of tropical rational functions, which, strictly speaking, is defined by tropical algebra (in the sense that tropical algebra is used to define these functions).  We are following suit: while our interpretation of neural networks are tropical Puiseux rational maps is tropical algebraic, we maintain that our framework is *tropical*.  We would like to add that tropical algebra was first introduced and studied in the context of tropical geometry, rather than as an independent theory (even though since the introduction of tropical geometry, work on tropical linear algebra, for instance, has been well-studied).  See Maclagan and Sturmfels, *An Introduction to Tropical Geometry* (2015) and Joswig, *Essentials of tropical combinatorics*' (2021).

### Effective utility
We appreciate the reviewer's observations regarding the lengths of the sections in our paper. While it is true that the symbolic section is shorter than the part on the numerical estimate, it nonetheless constitutes a significant portion of the main technical content and is highlighted as one of the key contributions of our paper in the introduction as well as the conclusion. Therefore, we feel it would be more balanced to give it due consideration in the review. For context, we would also like to note that the reviewer provided detailed feedback on Section 4, which is shorter than Section 5, indicating that length alone should not diminish the importance of the content.
Hello again,

### Group theory
I'm familiar with abstract group theory, group theory on topological spaces, representation and character theory. I appreciate the clarification. As $\mathbb{R}^n$ is a topological space (where standard definitions define a group acting on such a space as $g \cdot f(x) = f(g^{-1}x)$, see Dehmamy et al., 2021 or Cohen et al., 2019), a vector space (where standard definitions include group representations and generally $g \cdot f(x) = \rho(g) f(g^{-1}x)$, see Cohen and Welling, 2017 or Weiler and Cesa, 2019), and a set (where abstract group definitions could potentially suffice), stating that you define group actions in the classical sense is not descriptive, hence why I asked for the clarification. It's still not clear to me how you practically define the group action, but at this point I think at least the theoretical concepts are covered.

### Tropical geometry
I understand the authors perspective, but I disagree. Zhang et al., 2018 was explicitly using concepts from tropical geometry, which is not present in this work. 

### Effective utility
1. These considerations were for the numerical method as they explicitly mentioned the Hoffman constant and the point still stands.
2. The technical content of the paper spans pages 3 to 8. Three of those 5 pages are devoted to the numerical method, one page to Section 4, and one page to Section 5. The majority of the technical content is on the Hoffman constant.

### Lack of attribution
The statement is not false. Please read the full statement, printed here for your convenience: "In the introduction, textbooks on tropical geometry are cited as well as papers on the counting of linear regions. However, when the intersection of tropical geometry and machine/deep learning is discussed, zero references are provided, whereas the field has been fairly active in the last 5 years with dozens of highly cited papers". The comment explicitly mentions the introduction and where the intersection of tropical geometry and machine learning is first introduced. To further avoid confusion, I explicitly stated that general textbooks and cited papers are given for each of the fields separately, as a way to explicitly specify what I was referring to. As a final guard to misinterpretation, the following sentence reads "Similarly, in the related works section the final citation has..." which further reinforces that the previous part was not talking about the related works section. I further explained this in my previous response, and the statement is correct, I do not understand why this is such a point of contention. I think the listed works in your response act as adequate general references.

Dehmamy et al., 2021: Automatic Symmetry Discovery with Lie Algebra Convolutional Network

Cohen et al., 2019: A General Theory of Equivariant CNNs on Homogeneous Spaces

Cohen and Welling, 2017: Steerable CNNs

Weiler and Cesa, 2019: General E(2) - Equivariant Steerable CNNs
### Effective utility
1. We don't claim the new experiments are large scale, simply that they are larger scale than the original ones. 
2. Concerning the scale, we would also like to point out that that other papers in the area work with small, shallow networks, and have large compute times; see e.g., https://arxiv.org/pdf/1810.03370 and https://arxiv.org/pdf/1711.02114.
3. We are confused about the reviewer's comment concerning our symbolic method: ''As I mentioned in my original review, there is no asymptotic analysis nor a statement about the tightness of the bounds. In essence, running the proposed method on a network may or may not reveal something about the network, and we have no way of knowing how accurate the method might be.''
We acknowledge that such considerations are sensible for our numerical method, but these concerns are not relevant to the symbolic method, where, by the very nature of symbolic computation, **our method *does* reveal something about the network, and is *fully accurate*.**
4. While Section 3 does present one of the important contributions of our work, it is certainly not the only contribution we make and while we do appreciate feedback on this portion of the work that occupies 3 out of the 9 allowed content pages, we would like to point out that the entirety of Section 5 is also an important contribution because it presents our symbolic method and how it compares to the numerical one.  As mentioned above, there are fundamental differences to the two approaches and while there exist other numerical approaches in the literature, **ours is the first to propose symbolic approaches which essentially mitigate all of the concerns raised by the reviewer** on interpretability and accuracy (which are indeed important questions in numerical computation).

### Lack of attribution
Thank you for your feedback. We would like to respectfully address the comment regarding the absence of references when discussing the intersection of tropical geometry and machine/deep learning. **The statement that ''zero references were provided'' is entirely false**, particularly considering the subsequent clarification that ''no general references on the field are provided.'' We have indeed cited relevant works within this intersection, including on topics beyond expressivity and linear region counting. 

There are other references (listed below) around the intersection of tropical geometry and machine learning, but most of these do not directly overlap with the focus of our work, so we are not convinced that including them would be any more helpful than some of the existing references (which the reviewer already raised concerns on in terms of relevance to our work). Two notable ones that we do agree to include are Maragos, Charisopoulos, and Theodosis (2021), which provides a detailed survey of the general field, and Montufar, Ren, and Zhang (2022), which uses tropical geometry to study the linear regions of neural networks with neural networks with maxout units. We would like to point out that among the list below, the paper that we agree to include by Brandenburg et al. (2024) falls under the category of ''contemporaneous work'' by NeurIPS (as it appeared online within 2 months of our submission). If there are other particular papers that the reviewer believes we have overlooked that are directly relevant to our work, we would be grateful for the opportunity to review and incorporate them.

**Additional references:**

Maragos, Charisopoulos, and Theodosis. *Tropical Geometry and Machine Learning*, 2021.

Brandenburg, Loho, and Montúfar. *The Real Tropical Geometry of Neural Networks*, 2024.

Smyrnis and Maragos. *Tropical Polynomial Division and Neural Networks*, 2019.

Montufar, Ren, and Zhang. *Sharp bounds for the number of regions of maxout networks and vertices of minkowski sums*, 2022.
We appreciate the time and effort the reviewer has invested in evaluating our work. However, we were concerned by the tone of the recent exchange, which we believe deviated from the professional and respectful dialogue we value. Our intent in pointing out mathematical inaccuracies was not to discredit the review but to ensure that our work is assessed with the utmost accuracy. We hope to steer the conversation back to a constructive and respectful engagement and remain grateful for the opportunity to further clarify and discuss important aspects of our research.

We also want to clarify that our response was not limited to a single sentence/paragraph in **Questions** section. We noted that there were additional incorrect statements and misunderstandings other than the ones we highlighted in our previous response. Our intention is to address these comprehensively, ensuring that our work is accurately represented and understood. We appreciate your attention to detail and the opportunity to clarify these points.

### Group actions
Our original reading of the section in the review about group actions was that there was some confusion about how group actions are defined in the tropical setting, to which we answered that our group actions are not tropical. Group actions are quite a basic concept, but for clarification, we think it is worth being explicit about what we mean. By a left group action of $G$ on a set $X$, we mean a map $(g, x) \mapsto g \cdot x$ that satisfies the following properties: 
1. For any $x$ in $X$ and $g, h$ in $G$, we have $(g h) \cdot x = g \cdot (h \cdot x)$
2. For all $x$ in $X$, we have $1_G \cdot x = x$.

A right group action can be defined in a similar way (see, e.g., the Wikipedia page on group actions). In accordance with standard mathematical terminology, we use the term \emph{group action} to refer to a map $G \times X \to X$ that is either a left or a right action. In particular, we are making \emph{no} assumptions on the group $G$ beyond finiteness. The group $G$ acting on $\mathbb{R}^n$ further induces an action on the finite set of linear regions $\mathcal{U}$. In this case, for a linear region $x\in \mathcal{U}$ and a group element $g\in G$, the action of $g$ sends $x$ to another linear region $g\cdot x$. Thus we are in the case of finite groups acting on finite sets, without more complicated group representation theory involved. In particular, we do not mention group representations since they are not relevant here: in this level of generality, there is no natural way attaching a representation $\rho : G \to \mathrm{GL}(\mathbb{R}^n)$ to the group action $G \circlearrowright \mathbb{R}^n$ as the reviewer seems to be suggesting. It is of course possible to define certain group actions using representations, which gives rise to the class of *linear* group actions, but in our work there is no need to impose this additional restriction since it is not necessary for our results to hold. Given that this is seemingly a source of confusion, we will clarify this in the revision. 

### Tables
We apologise for the lack of clarity in Tables 1-6. As explained in Appendix D, we compute the Hoffman constant together with upper and lower bounds for 8 different Puiseux rational functions, and each column of Tables 1-3 corresponds to the outputs given for of these 8 samples (which are randomly generated with different structural parameters for each table). Tables 4-6 provide more detail about compute times, and again each column corresponds to a different sample. We will clarify this in the revision. 

### Tropical geometry

The reviewer is philosophically correct in observing that the entire paper could theoretically be rewritten without reference to tropical geometry, however, in the same line of reasoning, *any* mathematical theory could be rephrased starting from set theory. Doing so would diminish the significance of the specific mathematical contributions that tropical geometry brings to our work. Our choice to use the language of tropical geometry was twofold: (i) it provides a unifying and systematic framework for the general study of expressivity of neural networks; and (ii) it builds upon and extends the work of Zhang et al. (2018), where the main contribution of that paper was to provide an alternative perspective to studying neural networks through the lens of tropical geometry.  Furthermore, we would like to claim that the use of tropical geometry is in agreement with other well established works in the linear regions literature, and does not obscure the mathematics of our paper. 

Finally, concerning the OSCAR implementation, we agree that in principle our code could be reimplemented without using tropical notions. However, one of the four cornerstones of the OSCAR library is precisely the tropical geometry library (building from polymake) and our work opens the door for researchers to apply these very powerful comptuational tools to study neural networks.
Thank you for the discussion. Regarding the incorrect statements in the review, you seem to be referring to a single sentence (of a large paragraph, of an even larger section, of the **Questions** subfield). The whole purpose of the **Questions** subfield is to ask clarifying questions, which I did. I was operating under the assumption that for any choice of $J$ the set should be non-trivial, which you clarified in your rebuttal. There is little value in attempting to discredit a thorough review for asking a clarifying question.

At the same time, there are many points raised in my review that are still not addressed, from theoretical ones (how are group actions and group representations defined in this work), to practical ones (what are the different columns in the tables). You mention you work with group actions in the classical sense (which, itself, is not descriptive), but there is no mention of group representations and how these actions act on the objects of vector spaces.


### Tropical geometry
It is still unclear why tropical geometry is *necessary* for the paper. OSCAR is a computational algebra tool that does not require tropical geometry. Puiseux polynomials can exist outside of tropical geometry. All the computational tools do not require any concepts from tropical geometry, but rather, as the authors suggest, polyhedral geometry. This extends beyond using the extended reals: in (Zhang, 2018) and (Charisopoulos, 2018) the Newton polytopes are studied, which are central objects in tropical geometry. It appears that this work could avoid using tropical notation, and the paper would remain almost identical.

### Effective utility
No one is expecting production level code, but asking for a method that can work on networks of reasonable (in the order of 20) depths and reasonable (in the order of 1000) input sizes does not impose such requirements. Even in the new experiments you provided, the network sizes are tiny and there is a large variance in the running time (you mention 1 minute, however some instances run for over 10 minutes for a 3 layer network with a total of 4 hidden and one output neuron). We are in agreement that understanding small networks can lead to more profound understanding of deep learning, but I strongly disagree a 5 neuron network is a large-scale experiment: in fact, I would argue such a network doesn't even satisfy the bar of a small network. As I mentioned in my original review, there is no asymptotic analysis nor a statement about the tightness of the bounds. In essence, running the proposed method on a network may or may not reveal something about the network, and we have no way of knowing how accurate the method might be. The majority of the paper is devoted to the numerical method (Section 3), it is expected that comments will be made on what most of the work is about.

### Lack of attribution
The comment in the review was precise: "when the intersection of tropical geometry and machine/deep learning is discussed, zero references were provided". The intersection is introduced in 33 and no general references on the field are provided. 39-48 are works related to this one, and I already mentioned relevant papers which are more related to the work than, for example, [13] and [14].
### Lack of attribution to prior work

We are confused by the reviewer's claim that ''when the intersection of tropical geometry and machine/deep learning is discussed, zero references were provided'' when these appear in a subsection on related work (lines 39-48 of our submission).

To clarify our intentions on line 352, we are certainly not claiming that this work is the first to analyze expressivity of neural networks using tropical geometric quantities; we explicitly reference previous work in this direction in our manuscript in lines 39-41 (''Tropical geometry has been used to characterize deep neural networks with piece wise linear activation functions, including two of the most popular and widely-used activation functions, namely, rectified linear units (ReLUs) and maxout units.''). However, we are not aware of previous work that provides and implements exact algorithms that compute the total number of linear regions of a network-this is what the sentence on line 352 is stating.

### Lack of precision

We now address the reviewer's comments about the lack of precision in our comparison between our two methods: it is useful to state explicitly that the symbolic method for computing linear regions does already compute the ground truth. As a reminder, this is based on Algorithm 3, which computes the *exact* number of linear regions of a tropical Puiseux rational function. More specifically, the symbolic method converts the neural networks to a tropical Puiseux rational function, and then applies Algorithm 3. 
With that in mind, our claim that Table 10 in our original submission is more precise than Table 11 is communicating the fact that **the numerical method (used for Table 11) does not always give the exact answer (because, for instance, some regions might be missed), while the symbolic method does.**

As for missing assumptions, we acknowledge that Theorem 4.3 is missing the assumption that the group is finite. 
 We left this assumption out because it is implicit in the context (for instance, the statement is clearly implausible in the context of machine learning if it is to be interpreted in terms of cardinal arithmetic). Moreover, we disagree that our definition of $A$-surjective sets introduces any new assumptions on $m$ and $n$.  **The definition makes sense for any matrix $A$ (with no assumption that $m < n$) and the claim that the existence of $A$-surjective sets implies that $m < n$ is incorrect: For any non-zero matrix $A$, there exists an $A$-surjective set of row indices. In particular, our use of this notion does not introduce any additional assumptions on the networks we consider.**
### Effective Utility 

Firstly, we want to clarify that the main goal of our paper was to present a proof of concept, not to develop highly optimized code for large-scale stress tests on modern deep neural networks. Our focus was on laying the theoretical groundwork and demonstrating the feasibility of our approach. Therefore, we did not prioritize optimizing certain parts of the code for performance. This was a deliberate choice to highlight the direct applicability of symbolic computation techniques to neural networks. For example, in the tropical Puiseux polynomial library, we implemented simple algorithms, rather than using more sophisticated computer algebra methods. We believe there is considerable room for improvement in this area, and more efficient algorithms could significantly boost our approach's performance, which we noted in the Discussion section as a future research direction.

Secondly, our experiments mainly focused on smaller networks to allow for clear and understandable analysis. We believe that understanding small networks is helpful for making deep learning more interpretable. However, our code is capable of handling more complex architectures than those used in our experiments. For instance, our symbolic method can process neural networks with inputs of dimension of 28 × 28 (the dimension of inputs in the MNIST dataset) in about 1 minute. This shows that our approach is scalable, contrary to what our smaller experiments might suggest. We have added new tables in the attachment to demonstrate this on various architectures with higher-dimensional inputs (see Table 1). In our revision, we will include these larger-scale results alongside the smaller-scale experiments, as we believe the smaller-scale ones provide a clearer and more accessible proof of concept, allowing us to illustrate the key insights and mechanisms of our approach more easily.

Finally, the reviewer raised an important issue regarding the two methods we outlined for computing linear regions, which yield different results for networks deeper than 4 layers. We appreciate the reviewer for pointing this out and giving us the chance to clarify. The discrepancy is because the numerical algorithm version implemented in our submission allows for disconnected linear regions, while the symbolic method accounts for connectivity. In other words, the numerical algorithm may undercount the number of linear regions for certain networks. We will address this discrepancy in the revision.

We thank the reviewer for their careful reading and for identifying errors in Table 1--3 regarding the computed Hoffman constants. The lower bounds should indeed be below the true Hoffman constants. After reviewing the public code by Peña et al. (2018), we found that it returned incorrect values, leading to the errors. We have since re-computed the values using a brute force method, and the updated tables show that the lower bounds are always below the true values, consistent with the theory.

Regarding upper bounds, Theorem 3.9 (line 214 of our original submission) states that the Hoffman constant is bounded by the inverse of the smallest nonzero singular value of submatrices of $A$. We used a threshold of $10^{-10}$ to determine nonzero values, but found that many small singular values ranged between $10^{-30} \sim 10^{-14}$. This confirms that the singular values provide upper bounds, aligning with the theory. We agree with the reviewer that these bounds can be tightened, and we will mention this as a direction for future research in our revision. This study could also be promising for new results concerning the Stewart--Todd condition measure of a matrix.

We now turn to addressing the questions asked by the reviewer.  We summarize the major concerns in subtopics.

### Improving efficiency

We would like to clarify that our claim of improving efficiency refers to the factorial reduction for invariant networks, when compared to naively sampling without taking the symmetry into account. In particular, we do not claim to introduce computational improvements on already existing works, although we believe that the ideas we introduce in this manuscript may also lead to similar improvements for other methods.

How our methods scale and the question of their utility in the context of modern deep learning have been addressed earlier in this response.

(continued in the next official comment)
As we approach the end of the discussion period, we would like to take this opportunity to address some additional concerns raised in the reviewer’s original report. Due to the character limit for rebuttals, our initial response had to be concise, and we regret not being able to provide the level of detail that the depth of the original report warrants.

It is important to clarify that some statements made in the review above are incorrect. Additionally, as with reviewer vnGc, we are concerned that our significant contributions of adapting symbolic computation to the study of neural networks were not fully recognized, given the lack of acknowledgment and comments.

### Rigor of Tropical Geometry and Group Theory

We apologize for the confusion raised in our work, since, indeed, while we focus on the tropical geometric interpretation of neural networks, we are actually not working fully and exclusively in the tropical setting throughout our work, precisely because some of the concepts would not make sense, as pointed out by the reviewer.  We now elaborate on the specific concerns raised by the reviewer.

Our results do not require us to work over $\overline{\mathbb{R}}$. In particular, the absence of $\overline{\mathbb{R}}$ is intentional: we never work with tropical vectors or vector spaces, but only with tropical (Puiseux) polynomials, which can be understood with no reference to $\overline{\mathbb{R}}$.  Referring specifically to the expressions mentioned by the reviewer: in (4), we are taking a maximum over a finite set of Hoffman constants, each of which lies in $\mathbb{R}$ rather than $\overline{\mathbb{R}}$ (one concern here might be that we are in principle allowing coefficients of the tropical Puiseux rational function to be $-\infty$, but we can simply ignore such coefficients). Similar observations can be made about (5), (6), and (7), which should now clarify that these expressions are well-defined.

We respond similarly to the concern about group actions in the tropical setting: we never claim to be working with group actions in a tropical sense. In our submission, we are not working with tropical vector spaces and group actions, but simply with $\mathbb{R}^n$ and group actions in the classical sense.

In our revision, we will explicitly state that these specific concepts should not be evaluated tropically so as to diffuse any misunderstandings. 

### Motivation

We thank the reviewer for this question and would like to take this opportunity to respond to concerns raised by the reviewer.

With regard to motivation and contribution, we respond by stating that to the best of our knowledge, all computational methods (that have been implemented!) for computing the number of linear regions of a neural network resort to some form of sampling that doesn't guarantee an exact solution, or impose some restrictions such as boundedness on the input variables (for instance, as our Jacobian sampling method does) rather than computing the *total* number of linear regions. Our work fills this void in two different ways: 
1. We provide new tools for computing the size of the domain that needs to be restricted to in order to count the correct number of linear regions, and we give a new method (the so-called symbolic method) for computing the exact number of linear regions of a neural network on an unbounded domain; 
2. We also provide a new avenue for understanding the expressivity of neural networks (or more generally, studying interpretability) - specifically, we provide a direct way of computing another representation of neural networks, namely, the tropical Puiseux rational form. This representation is important because it opens the door to using other theory from tropical geometry, e.g., computing other measures of complexity, such as the number of (non-redundant) monomials that appear in the tropical expression of a neural network.



(continued in the next official comment)
Thank you for your continued engagement with our work and for the thoughtful feedback.

To the best of our knowledge, the number of linear regions in a neural network is not equivalent to any of the information measures listed by the reviewer. We understand the potential for miscommunication and will be more careful with our terminology in the future to ensure clarity and precision.

Thank you once again for your valuable input.
Thank you very much for your thoughtful response and for taking the time to revisit our paper in light of our comments. 
In our revision, we will ensure that the novelty of our proofs, their distinction from prior works, and the connections to depth-width tradeoffs are further emphasized.

One of the key contributions of our paper is demonstrating the computational feasibility of using the tropical form of a neural network to gain deeper insights into the geometry of linear regions and the complexity of the resulting tropical expression. **We noticed that the review has not yet mentioned this aspect**, and we would greatly appreciate any feedback you could provide on our symbolic computations for linear regions and tropical forms, as **we consider this to be a central component of our work**.
Thank you once again for your time and constructive feedback.
Thank you for detailed responses. I will keep my score as is.

> Linear Regions as an Estimate of Information Capacity
> ... by counting these linear regions, we get an estimate of how many classes a neural network could classify in theory if the weights were ‘hand-tuned,’ ...

Thank you for clarifying it. I skimmed Zhang et al. (2018), Montúfar et al. (2014), and Raghu et al. (2017), but none of the authors called it information. Is the number of linear regions equivalent to either Shannon's mutual information (aka channel capacity), the information bottleneck in the rate-distortion theory, or any other information measure? If not, I recommend the authors not to call it 'information' to avoid miscommunication.
The reviewer appreciates the author's response. The reviewer has read their comments and reread parts of the paper but still maintains the score unchanged. The reviewer would rewrite parts of the paper to highlight the novelty of the proofs, the proofs themselves and how they were significantly different from prior works, and finally the author's suggested connections to depth-width tradeoffs.
I would like to thank the authors for providing a rebuttal. My concerns regarding the Hoffman constants have been somewhat assuaged, but I am surprised that the code the authors were using from prior work was wrong and that this was caught only during the review process. Out of an abundance of caution, I would like to maintain my reject rating. I believe this work has some merit, but greater care needs to be taken when computing bounds. I hope that the authors will improve their work and produce a higher quality resubmission.
We thank the reviewer for reading our rebuttal and giving us this important opportunity to clarify our approach further.

### The role of infinity

The tropical semiring is a fundamental algebraic object in tropical geometry where all other constructions are based. For the sake of completeness and correctness, we must introduce $-\infty$ to the extended real line since it is the neutral element for tropical addition. In our application to machine learning, the main way the tropical framework appears is that it gives a very convenient (and, as our work demonstrates, computable) way of representing neural networks. In other words, we are interested in *tropical* representations these functions. While tropical Puiseux polynomials naturally yield functions defined over the whole extended real line, this is generally not the case for neural networks, and thus we usually restrict to $\mathbb{R}$. We would also like to emphasize that while the mathematics are mostly developed over the real numbers, a large portion of our code uses OSCAR's implementation of the tropical algebra.

### Connection to tropical geometry

Tropical geometry is a broad field and intersects with many other mathematical fields including polyhedral geometry, algebraic geometry, combinatorics, etc. For example, tropical Puiseux polynomials, tropical monomials are naturally related to linear regions and polyhedra in ways which are fully elaborated in our paper. The connection between neural networks and tropical geometry is *crucial* since it allows us to use OSCAR to develop symbolic computations.
While we acknowledge that we don’t use any advanced tropical geometry for our results (and instead use techniques from other fields e.g., polyhedral geometry), we maintain that our work is nevertheless tropical geometric in nature: Firstly, our results are built on the tropical geometric interpretation of neural networks. Secondly, we principally interpret tropical Puiseux polynomials as functions over $\mathbb{R}$, which is the natural approach for studying their function-theoretic properties as we do in our work. Despite this interpretation, they still are rigorously tropical objects.

We understand that the mix of tropical and classical approaches and perspectives in our work may have inadvertently introduced confusion, which we will carefully clarify in the revision.

### Responding to other concerns
We are very grateful for this opportunity to engage with the reviewer who gave us a very detailed, thoughtful, and constructive review, which we appreciated very much. We would like to ask if the reviewer has any other questions pertaining to our rebuttal of the concerns in the original report? We are aware that our rebuttal was brief, given that we were constrained to the quite strict character limit, but we would very much like to engage further and respond in greater detail to the reviewer’s observations in the original report above.
Thank you for the rebuttal and for engaging with the reviewing process.

Regarding the tropical geometry, I have to say I'm confused by the response. If the Puiseux polynomials are interpreted using $\mathbb{R}$, and all the other concepts in the paper are independent of tropical geometry, then what is the connection to tropical geometry?