Tropical Expressivity of Neural Networks

## Abstract

We propose an algebraic geometric framework to study the expressivity of linear activation neural networks. A particular quantity of neural networks that has been actively studied is the number of linear regions, which gives a quantification 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 connection 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 a new open source OSCAR library to analyze neural networks symbolically using their tropical representations, where we present a new algorithm that computes the exact number of their linear regions. 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 neural networks and deep learning.

## 1 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 such a foundation 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 (see Appendix 2.3), where combinatorics naturally comes into play (e.g., Mikhalkin and Rau, ; Speyer and Sturmfels, ; Maclagan and Sturmfels, ). 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 (e.g., Pascanu et al., ; Montúfar et al., ; Arora et al., ; Raghu et al., ; Hanin and Rolnick, ; Xiong et al., ; Goujon et al., ; Montúfar et al., ). 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.

##### Related Work.

Tropical geometry has emerged as a powerful tool for analyzing deep neural networks with piecewise linear activation functions, such as rectified linear units (ReLUs) and maxout units. Zhang et al. () first established that neural networks can be represented by tropical rational functions, enabling the use of tropical techniques to study network expressivity. They also showed that the decision boundary of a deep ReLU network is contained in a tropical hypersurface. (For more details, see Appendix 2.3.) Concurrently, Charisopoulos and Maragos () demonstrated that the maxout activation function fits input data using a tropical polynomial. These initial works focused on neural networks with Euclidean input domains. Yoshida et al. () later extended this approach to incorporate the tropical projective torus as an input domain, broadening the applicability of tropical methods. Recently, Pasque et al. () leveraged tropical geometry to construct convolutional neural networks with improved robustness against adversarial attacks, demonstrating the practical value of this theoretical framework. This growing body of research highlights the potential of tropical geometry to enhance our understanding and design of neural networks.

Measures of quantifying neural network expressivity are important for facilitating the theoretical and empirical investigation of neural network properties. Neural networks with piecewise linear activations compute piecewise linear functions on areas of the input space referred to as the network’s *linear regions*. The number of distinct linear regions of the network provides an appropriate and quantifiable measure of its expressivity (e.g., Montúfar et al., ). Subsequent research has also worked towards enumerating the number of linear regions a given neural network has. Using mixed-integer programming, Serra et al. () provide an exact enumeration of the number of linear regions in a bounded subset of the input domain. For unbounded domains, Serra and Ramalingam () give an analytic upper bound on the maximum number of linear regions of a neural network along with a probabilistic lower bound, and Charisopoulos and Maragos () provide a probabilistic methods for estimating the linear regions of a one-layer network, together with some analytic bounds for various architectures.

##### Contributions.

In this paper, we establish novel algebraic and geometric tools to quantify the expressivity of a neural network by exactly enumerating all of its linear regions. We study more than simply the number of linear regions, we provide further insight on 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 number of 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 () which converts both trained and untrained arbitrary neural networks into algebraic symbolic objects, as well as a new algorithm that computes the *exact* number of linear regions of such objects. Our library opens the door for the extensive theory and existing software on symbolic computation and computational tropical geometry to be used to study neural networks. We also propose a new alternative measure of expressivity, the *monomial count*, which is based on the algebraic complexity of tropical expressions of neural networks.

The remainder of this paper is organized as follows. We devote a section to each of the contributions listed above—Sections 3, 4, and 6, 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 7. The Appendix provides the necessary technical background on tropical geometry and its connection to neural networks as well as all proofs.

Figure: (a) The linear regions of a randomly initialised ReLU neural network
Refer to caption: extracted/5911715/two-d.png

## 2 Technical Background

In this section, we the necessary technical background on the mathematics of neural networks and tropical geometry for our contributions.

### 2.1 Neural Networks

###### Definition 1 .

Given a function $\sigma:{\mathbb{R}}\to{\mathbb{R}}$, a *neural network with activation $\sigma$* is a function $f:{\mathbb{R}}^{n}\to{\mathbb{R}}^{m}$ of the form

$$ $\sigma\circ L_{d}\circ\dotsb\circ\sigma\circ L_{1}$ $$

where $L_{i}:{\mathbb{R}}^{n_{i-1}}\to{\mathbb{R}}^{n_{i}}$ is an affine map and the function $\sigma$ is applied to vectors element-wise. The tuple of integers $[n_{0},\dotsc,n_{d}]$ is called the *architecture* of the neural network $f$.

Given such a neural network, we can always write the $L_{i}$ as $L_{i}(x)=A_{i}x+b_{i}$. $A_{i}$ as a *weight matrix* and $b_{i}$ is a *bias vector* for the $i$th layer of the neural network; $\mathbb{R}^{n}$ is the *input domain* of the neural network and the output of $L_{i}$ is the *preactivation output* of the $i$th layer, $\sigma\circ L_{i}$ is the *output* of the $i$th layer. For conciseness, we will write $\nu^{(\ell)}$ to denote the function giving the output of the $\ell$th; i.e.,

$$ $\nu^{(\ell)}=\sigma\circ L_{l}\circ\dots\circ\sigma\circ L_{1}.$ $$

There are many choices for the *activation function* $\sigma$, a popular choice is the Rectified Linear Unit (ReLU) function, $\sigma(t)=\max(0,t)$. Neural networks with ReLU activation will be the main focus of this work, and will usually be referred to simply as *neural networks*.

###### Definition 2 .

A set $U\subset\mathbb{R}^{n}$ of a neural network $f:\mathbb{R}^{n}\to\mathbb{R}^{m}$ is a *linear region* if it is a maximal connected region (closure of an open set) on which $f$ is linear.

###### Definition 1 .

###### Definition 2 .

### 2.2 Polyhedral Geometry

Polyhedra are geometric objects that finitely many inequalities can describe.

###### Definition 3 .

A *polyhedron* is a subset of $\mathbb{R}^{n}$ of the form $P=\{x\in\mathbb{R}^{n}:Ax\leq b\},$
where $A\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^{m}$, and the inequality is taken element-wise. Such a polyhedron is denoted by $P(A,b)$.

###### Lemma 4 .

Let $P(A,b)$ and $P(A^{\prime},b^{\prime})$ be polyhedra. Then

$$ $P(A,b)\cap P\left(A^{\prime},b^{\prime}\right)=P\left(\begin{bmatrix}A\\ A^{\prime}\end{bmatrix},\begin{bmatrix}b\\ b^{\prime}\end{bmatrix}\right).$ $$

###### Proof.

Note that for $x\in\mathbb{R}^{n}$ we have

$$ $\begin{bmatrix}A\\ A^{\prime}\end{bmatrix}x=\begin{bmatrix}Ax\\ A^{\prime}x\end{bmatrix}\leq\begin{bmatrix}b\\ b^{\prime}\end{bmatrix}$ $$

if and only if $Ax\leq b$ and $A^{\prime}x\leq b^{\prime}$. Therefore, we conclude that

$$ $P(A,b)\cap P(A^{\prime},b^{\prime})=P\left(\begin{bmatrix}A\\ A^{\prime}\end{bmatrix},\begin{bmatrix}b\\ b^{\prime}\end{bmatrix}\right).$ $$

∎

###### Example 5 .

-
- 1.
$A=\begin{pmatrix}1&1&0\\
1&0&1\end{pmatrix}^{\top}$ and $b=\begin{pmatrix}0&1&1\end{pmatrix}^{\top}$ give the the polyhedron in Figure 2(a).
- 2.
$A=\begin{pmatrix}1&0&-1&0\\
0&1&0&-1\end{pmatrix}^{\top}$ and $b=\begin{pmatrix}1&1&1&1\end{pmatrix}$ give the polyhedron in Figure 2(b).
- 3.
$A=\begin{pmatrix}1&1&0&1&0&-1&0\\
1&0&1&0&1&0&-1\end{pmatrix}^{\top}$ and $b=\begin{pmatrix}0&1&1&1&1&1&1\end{pmatrix}^{\top}$ give the polyhedron in Figure 2(c).

Figure: (a)
Refer to caption: extracted/5911715/polyhedron_1.png

###### Definition 3 .

###### Lemma 4 .

###### Proof.

###### Example 5 .

##### Dimension Theory for Polyhedra.

###### Definition 6 .

The *affine hull* of a polyhedron $P\subset{\mathbb{R}}^{n}$ is the smallest affine subspace of ${\mathbb{R}}^{n}$ that contains $P$, and is denoted by $\mathrm{AffHull}(P)$

###### Definition 7 .

The *dimension* of a polyhedron $P$ is the dimension of $\mathrm{AffHull}(P)$.

The description of a polytope as the set of points that satisfy a system comprising finitely many linear inequalities may be needlessly complicated: some inequalities may be redundant and some may be replaced by equalities without changing the set. We now make these notions more precise.

###### Definition 8 .

An inequality $\langle\alpha,x\rangle\leq\beta$ in the system $Ax\leq b$ is an *implicit equality* if for any $x$ that satisfies $Ax\leq b$, we have $\langle\alpha,x\rangle=\beta$.

###### Notation .

We can partition the system $Ax\leq b$ into two systems: the system of implicit equalities, denoted by $A^{=}x\leq b^{=}$, and the system of remaining inequalities, denoted by $A^{+}x\leq b^{+}$.

The affine hull gives us a convenient way of dealing with the system of implicit equalities.

###### Lemma 9 .

The affine hull of a polyhedron $P=P(A,b)$ admits the following description:

$$ $\mathrm{AffHull}(P)=\left\{x:A^{=}x=b^{=}\right\}$ $$

In particular, the dimension of $P$ is given by

$$ $n-\mathrm{rank}(A^{=}).$ $$

###### Proof.

See (Schrijver, , §8.2).
∎

Once we know which defining inequalities of a polyhedron $P(A,b)$ are implicit equalities, we can always find a point in the polyhedron that make the remaining inequalities strict.

###### Lemma 10 .

Let $P=P(A,b)$ be a polyhedron. Then there exists a point $\bar{x}\in P$ such that $A^{+}x<b^{+}$.

###### Proof.

See (Schrijver, , §8.1).
∎

###### Definition 6 .

###### Definition 7 .

###### Definition 8 .

###### Notation .

###### Lemma 9 .

###### Proof.

###### Lemma 10 .

###### Proof.

### 2.3 Tropical Geometry

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*, $\overline{\mathbb{R}}=(\mathbb{R}\cup\{-\infty\},\oplus,\odot)$ where the addition and multiplication operators are given by $a\oplus b=\max(a,b)$ and $a\odot b=a+b$, respectively. We additionally let $a\oslash b:=a-b$.

##### Tropical Polynomials.

Using these operations, we can write polynomials as $\bigoplus_{m}a_{m}T^{m}$, where $a_{i}$ are coefficients, $T\in\overline{{\mathbb{R}}}$, and where the sum is indexed by a finite subset of $\mathbb{N}$. In our work, we consider the following generalizations of tropical polynomials.

###### Definition 11 .

A *tropical Puiseux polynomial* in the indeterminates $T_{1},\dotsc,T_{n}$ is a formal expression of the form $\bigoplus_{m}a_{m}T^{m}$ where the index $m$ runs through a finite subset of $\mathbb{Q}_{\geq 0}^{n}$ and $T^{m}=T_{1}^{m_{1}}\odot\dotsb\odot T_{n}^{m_{n}}$ with powers taken in the tropical sense.

###### Definition 12 .

A *tropical Puiseux rational map* in $T_{1},\dotsc,T_{n}$ is a tropical quotient of the form $p\oslash q$ where $p,q$ are tropical Puiseux polynomials.

###### Definition 11 .

###### Definition 12 .

##### Linear Regions of Tropical Polynomials.

Let $f$ be a tropical polynomial in $n$ variables. We write $f=\bigoplus_{j=1}^{m}a_{\alpha_{j}}T^{\alpha_{j}}$ where $\alpha_{j}=\left\{\alpha_{j1},\dots,\alpha_{jn}\right\}\in\mathbb{N}^{n}$ for each $j=1,\dots,m$. As a function ${\mathbb{R}}^{n}\to{\mathbb{R}}$, the map $f$ is given by

$$ $x\mapsto\max_{j\in\{1,\dots,m\}}\left\{a_{\alpha_{j}}+\langle\alpha_{j},x \rangle\right\}.$ (1) $$

Let $i\in\{1,\dots,m\}$, and consider

$$ $M_{\alpha_{i}}=\left\{x\in\mathbb{R}^{n}:f(x)=a_{\alpha_{i}}+\langle\alpha_{i} ,x\rangle\right\},$ $$

that is $M_{\alpha_{i}}$ is the subset of points at which the $i$th term is the maximum term in the expression of $f$. Equivalently, we have that

$$ $\displaystyle M_{\alpha_{i}}$ $\displaystyle=\left\{x\in\mathbb{R}^{n}:a_{\alpha_{i}}+\langle\alpha_{i},x \rangle\geq a_{\alpha_{j}}+\langle\alpha_{j},x\rangle\text{ for all }j\in\{1, \dots,m\}\right\}$ $\displaystyle=\left\{x\in\mathbb{R}^{n}:\left\langle\alpha_{j}-\alpha_{i},x \right\rangle\leq a_{\alpha_{i}}-a_{\alpha_{j}}\text{ for all }j\in\{1,\dots,m \}\right\}$ $\displaystyle=\left\{x\in\mathbb{R}^{n}:Ax\leq b\right\},$ $$

where $A\in\mathbb{R}^{m\times n}$ with $A_{jk}=\alpha_{jk}-\alpha_{ik}$ and $b\in\mathbb{R}^{m}$ with $b_{j}=a_{\alpha_{i}}-a_{\alpha_{j}}$. That is, the subset $M_{\alpha}$ is the polyhedron $P(A,b)$.

We then consider the collection of polyhedral $(M_{\alpha_{i}})_{i\in\{1,\dots,m\}}$ to determine the linear regions of $f$. That is, we determine the maximally connected sets, which will be some union of the $M_{\alpha_{i}}$s, such that on these sets $f$ is a linear function.

###### Example 13 .

-
- 1.
Consider the tropical polynomial $f=0\oplus T\oplus T^{2}$. Then the map $f$ is given by
$x\mapsto\max\left\{0,1+x,1+2x\right\},$
thus
$\begin{cases}M_{0}=P(1,-1)=\{x\leq-1\},\\
M_{1}=P\left([1,-1],\begin{bmatrix}0\\
1\end{bmatrix}\right)=\{-1\leq x\leq 0\},\\
M_{2}=P(-1,0)=\{x\geq 0\}.\end{cases}$
The linear regions of $f$ are then $\{M_{0},M_{1},M_{2}\}$.
- 2.
Consider the tropical polynomial $f=T\oplus 0T^{2}$. Then the map $f$ is given by
$x\mapsto\max\{1+x,2x\},$
thus
$\begin{cases}M_{1}=P(1,1)=\{x\leq 1\}\\
M_{2}=P(1,-1)=\{x\geq 1\}.\end{cases}$
The linear regions of $f$ are then $\{M_{1},M_{2}\}$.
- 3.
Consider the tropical polynomial $f=1T^{0}\oplus T\oplus T^{2}$. Then the map $f$ is given by
$x\mapsto\max\{1,1+x,1+2x\},$
thus
$\begin{cases}M_{0}=P(1,0)=\{x\leq 0\},\\
M_{1}=P\left(\begin{bmatrix}1\\
-1\end{bmatrix},\begin{bmatrix}0,\\
0\end{bmatrix}\right)=\{x=0\},\\
M_{2}=P(-1,0)=\{x\geq 0\}.\end{cases}$
The linear regions in this case are $\{M_{0},M_{2}\}$. Note how $M_{1}$ does not contribute to the map $f$, so the monomial $T$ is redundant. Algorithm 6 would detect this by noting that the dimension of $M_{1}$ is less than the number of variables of $f$.
- 4.
Consider the tropical polynomial $f=T^{2}\oplus T^{3}\oplus 2T^{4}$. Then the map $f$ is given by
$x\mapsto\max\{1+2x,\,1+3x,\,2+4x\},$
thus
$\begin{cases}M_{2}=P\left(1,-\frac{1}{2}\right)=\left\{x\leq-\frac{1}{2}\right
\},\\
M_{3}=\varnothing\\
M_{4}=P\left(-1,\frac{1}{2}\right)=\left\{x\geq-\frac{1}{2}\right\}.\end{cases}$
Hence, the linear regions in this case are $\{M_{2},M_{4}\}$. Note how $M_{3}$ does not contribute to the map $f$. Hence, the monomial $T^{3}$ is redundant. One of the results of Section 6.4, Lemma 32, shows that this is related to the fact that the dimension of $M_{3}$ is less than the number of variables of $f$.

Figure: (a)
Refer to caption: extracted/5911715/two-d_trop_poly_1.png

For a tropical polynomial $f$, a point that lies in two linear regions is a point at which the maximum identified in (1) is attained at two different terms in the expression of $f$. In standard tropical geometry terminology, these points are precisely those found on the tropical hypersurface cut of by $f$.

###### Example 13 .

##### Tropical Expressions for Neural Networks.

The first explicit connection between tropical geometry and neural networks was established in Zhang et al. (); we adopt a similar notation.

One of the key observations for 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 (Zhang et al., , 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 Zhang et al. () can be directly 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.

###### Proof.

Let $f:\mathbb{R}^{n}\to\mathbb{R}^{m}$ be a neural network with architecture $[n_{0},\dots,n_{d}]$. Let $A_{1}=\left[a_{ij}\right]\in\mathbb{Z}^{n_{0}\times n_{1}}$ and $b\in\mathbb{R}^{n_{1}}$ be the weight and bias vectors respectively for the first layer of the network. Let $(A_{1})_{+}=\left[a^{+}_{ij}\right]$ where $a_{ij}^{+}:=\max\left\{a_{ij},0\right\}$, and let $(A_{1})_{-}=\left[a^{-}_{ij}\right]$ where $a_{ij}^{-}:=\max\left\{-a_{ij},0\right\}$. So that $(A_{1})_{+},(A_{1})_{-}\in\mathbb{N}^{m\times n}$ with $A_{1}=(A_{1})_{+}-(A_{1})_{-}$. Observe,

$$ $\sigma(A_{1}x+b)=\max\left(0,A_{1}x+b\right)=\sigma\left((A_{1})_{+}x+b,(A_{1} )_{-}x\right)-A_{-}x.$ $$

That is, every coordinate of the output of the first layer of the network can be written as the difference of tropical polynomials. Assume this is also true for the $\ell$th layer, where $\ell<d$, so we can write

$$ $\nu^{(\ell)}(x)=F^{(\ell)}(x)\oslash G^{(\ell)}(x),$ $$

where $F^{(\ell)}$ and $G^{(\ell)}(x)$ are tropical polynomials. Then

$$ $\displaystyle L_{\ell+1}\circ\nu^{(\ell)}(x)$ $\displaystyle=\left(\left(A_{\ell+1}\right)_{+}-\left(A_{\ell+1}\right)_{-} \right)\left(F^{(\ell)}(x)-G^{(\ell)}(x)\right)+b_{\ell}$ $\displaystyle=\left(\left(A_{\ell+1}\right)_{+}F^{(\ell)}(x)+\left(A_{\ell+1} \right)_{-}G^{(\ell)}(x)+b_{\ell+1}\right)$ $\displaystyle\quad-\left(\left(A_{\ell+1}\right)_{-}G^{(\ell)}(x)+\left(A_{ \ell+1}\right)_{-}F^{(\ell)}(x)\right)$ $\displaystyle=H^{(\ell+1)}(x)-G^{(\ell+1)}(x),$ $$

where $H^{(\ell+1)}(x)$ is a tropical polynomial. Therefore, the output of the $(\ell+1)$st can be written as

$$ $\displaystyle\nu^{(\ell+1)}(x)$ $\displaystyle=\max\left\{0,\,L_{\ell+1}\circ\nu^{(l)}\right\}$ $\displaystyle=\max\left\{0,\,H^{(\ell+1)}(x)-G^{(\ell+1)}(x)\right\}$ $\displaystyle=\max\left\{H^{(\ell+1)}(x),\,G^{(\ell+1)}(x)\right\}-G^{(\ell+1) }(x)$ $\displaystyle=F^{(\ell+1)}(x)-G^{(\ell+1)}(x),$ $$

where, as before, $F^{(\ell+1)}$ and $G^{(\ell+1)}$. Hence, through inductive arguments, we deduce that the neural network $f$ can be written as a difference of tropical polynomials, that is $f$ can be written as a tropical rational map.
∎

The proof that neural networks can be written as tropical rational maps provides a recursive construction that we utilize to computationally obtain a tropical representation of a neural network.

###### Proof.

### 2.4 Permutation Invariant Neural Networks

Informally, a permutation invariant neural network is a neural network whose output is unchanged upon re-ordering its inputs.

###### Definition 14 .

A *permutation matrix* $P\in\mathbb{R}^{n\times n}$ is a matrix of zeros with exactly one entry equal to 1 in each row and column.

###### Example 15 .

$P_{1}=\begin{pmatrix}0&1&0\\
1&0&0\\
0&0&1\end{pmatrix}$ is a permutation matrix, whereas $P_{2}=\begin{pmatrix}1&1&0\\
0&0&1\\
1&0&0\end{pmatrix}$ is not since the first row contain two 1s. Note that

$$ $P_{1}\begin{pmatrix}x_{1}\\ x_{2}\\ x_{3}\end{pmatrix}=\begin{pmatrix}x_{2}\\ x_{1}\\ x_{3}\end{pmatrix}.$ $$

That is, left multiplication by $P_{1}$ has the effect of permuting the entries of the vector.

###### Definition 16 .

-
- 1.
A function $f:\mathbb{R}^{n}\to\mathbb{R}^{m}$ is *permutation invariant* if $f(Px)$ for every $n\times n$ permutation matrix $P$.
- 2.
A function $f:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is *permutation equivariant* if $f(Px)=Pf(x)$ for every $n\times n$ permutation matrix $P$.

###### Lemma 17 ( Zaheer et al. ( 2017 ) ) .

An $m\times m$ matrix $W$ acting as a linear operator of the form $W=\lambda I_{m\times m}+\gamma(\mathbf{1}^{\top}\mathbf{1})$, where $\lambda,\gamma\in{\mathbb{R}}$ and $I_{m\times m}$ is the $m\times m$ identity matrix, is permutation equivariant.

Now consider the neural network $f:\mathbb{R}^{n}\to\mathbb{R}$ given by

$$ $f(x)=\sum_{i=1}^{n}\sigma\left(Wx\right),$ (2) $$

where $\sigma$ is the ReLU activation function and $W$ is as in Lemma 17. Then $f$ is permutation invariant since

$$ $f(Px)=\sum_{i=1}^{n}\sigma(WPx)\overset{\text{Lem}\ref{lem:deepsets}}{=}\sum_{ i=1}^{n}P\sigma(Wx)=\sum_{i=1}^{n}\sigma(Wx)=f(x),$ $$

where we have used the fact that the ReLU activation is applied element-wise, and summation is a permutation invariant operation.

###### Lemma 18 .

The set

$$ $\Delta=\{(x_{1},\dots,x_{n}):x_{1}\geq x_{2}\geq\dots\geq x_{n}\}$ $$

is a fundamental domain of the action of $S_{n}$ on ${\mathbb{R}}^{n}$ that permutes coordinates.

###### Proof.

It suffices to show that conditions (i) and (ii) of Definition 28 are satisfied.
(i): Let $x=(x_{1},\dots,x_{n})\in\mathbb{R}^{n}$. Let $g:\{1,\dots,n\}\to\{1,\dots,n\}$ be a bijective function such that

$$ $x_{g(1)}\geq x_{g(2)}\geq\dots\geq x_{g(n)}.$ $$

Then $g\in S_{n}$, and $g\cdot x=\left(x_{g(1)},\dots,x_{g(n)}\right)=:\hat{x}\in\Delta.$
Therefore,

$$ $x=g^{-1}\cdot\hat{x}\in\bigcup_{h\in S_{n}}h\cdot\Delta.$ $$

Thus since clearly $\bigcup_{g\in S_{n}}g\cdot\Delta\subset\mathbb{R}^{n}$, we deduce that $\mathbb{R}^{n}=\bigcup_{g\in G}g\cdot\Delta$.
(ii): Let $g,\in S_{n}$ be distinct. Suppose for contradiction that $x\in\left(g\cdot\mathrm{int}(\Delta)\cap h\cdot\mathrm{int}(\Delta)\right)$. Then $x=g\cdot y$ and $x=h\cdot z$, for some $y,z\in\mathrm{int}(\Delta)$. In particular, $y$ and $z$ are such that

$$ $y_{1}>y_{2}>\dots>y_{n}\mbox{ and }z_{1}>z_{2}>\dots>z_{n}.$ $$

We know that for each $j\in\{1,\dots,m\}$ we have $y_{j}=z_{k}$ for some $k\in\{1,\dots,m\}$. Suppose $y_{j}=z_{k}$ then

$$ $y_{1}>\dots y_{j-1}>y_{j}=z_{k}>z_{k+1}>\dots>z_{n}.$ $$

This means the $y_{1},\dots,y_{j-1}$ can only pair with the $z_{1},\dots,z_{k-1}$, and thus $j=k$. Therefore, $y=z$ which implies that $g=h$ which is a contradiction. We conclude then that
$g\cdot\mathrm{int}(\Delta)\cap h\cdot\mathrm{int}(\Delta)=\varnothing.$
∎

###### Definition 14 .

###### Example 15 .

###### Definition 16 .

###### Lemma 17 ( Zaheer et al. ( 2017 ) ) .

###### Lemma 18 .

###### Proof.

## 3 Bounded Domain Selection Using a Hoffman Constant

Understanding the number of linear regions of a neural network is inherently challenging due to its combinatorial nature. From an applications perspective, since it is reasonable to assume that the data are bounded, it is common to restrict to some bounded input domain $X\subseteq\mathbb{R}^{n}$ such as $[-R,R]^{n}$ or $[0,R]^{n}$. Then the number of linear regions in $X$ can be either estimated by computing the Jacobians of the network at sample points (see Appendix 6.2) or computed exactly (e.g., Serra et al., ). However, these approaches are limited from a theoretical perspective, since, by assumption, they only provide information about the linear regions of a network in a bounded region $X$. In this section, we address the discrepancy between bounded and unbounded linear region enumeration by inferencing the unbounded case from the bounded case. More specifically, we provide a method to determine the radius $R$ of a ball centered at the origin, which intersects every linear region. Given such an $R$, we can apply existing algorithms on $X=[-R,R]^{n}$ to obtain the *exact* number of linear regions.

Our approach proceeds as follows. Recall that neural networks can be formulated as tropical Puiseux rational maps (see Appendix 2). Thus, characterizing $R$ for neural networks is equivalent to characterizing $R$ for tropical Puiseux rational maps. The linear regions of tropical Puiseux polynomials are made up of polyhedra, allowing us to connect the value $R$ to a combinatorial invariant: the *Hoffman constant*. We extend the definition of the Hoffman constant to tropical rational maps to provide more insight on their linear regions and construct algorithms to compute its the true value, as well as upper and lower bounds.

### 3.1 Neural Hoffman Constants

Intuitively, the Hoffman constant of a matrix measures the distance from points in a space to polyhedra constructed from this matrix (see Appendix 2 for background on polyhedral geometry). Let $A$ be an $m\times n$ matrix with real entries. Then for any $b\in\mathbb{R}^{m}$ such that $P(A,b)$ is non-empty, let

$$ $d(u,P(A,b))=\min\{\|u-x\|:x\in P(A,b)\}$ $$

denote the distance of a point $u\in\mathbb{R}^{n}$ to the polyhedron, measured under an arbitrary norm $\|\cdot\|$ on $\mathbb{R}^{n}$. Then there exists a constant $H(A)$ only depending on $A$ such that

$$ $d\left(u,P(A,b)\right)\leq H(A)\left\|(Au-b)_{+}\right\|,$ (3) $$

where $x_{+}=\max(x,0)$ is applied coordinate-wise (Hoffman, ). $H(A)$ is the *Hoffman constant* of $A$.

##### The Hoffman Constant for Tropical Polynomials and Rational Functions.

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be a tropical Puiseux polynomial and let $\mathcal{U}=\{U_{1},\ldots,U_{m}\}$ be the set of linear regions of $f$. Say $f(x)=a_{i1}x_{1}+\ldots+a_{in}x_{n}+b_{i}$ occurs on the region $U_{i}$, so that $A=\left[a_{ij}\right]_{m\times n}$ is the matrix of exponents in the algebraic expression of $f$. The linear region $U_{i}$ is defined by the inequalities

$$ $a_{i1}x_{1}+\cdots+a_{in}x_{n}+b_{i}\geq a_{j1}x_{1}+\cdots+a_{jn}x_{n}+b_{j}, \quad\forall\ j=1,2,\cdots,m$ (4) $$

which can be written in matrix form as

$$ $(A-\mathbf{1}a_{i})x\leq b_{i}\mathbf{1}-b,$ (5) $$

where $\mathbf{1}$ is an all-1 column vector; $a_{i}$ is the $i$th row vector of $A$; and $b$ is a column vector of all $b_{i}$. Denote $\widetilde{A}_{U_{i}}:=A-\mathbf{1}a_{i}$ and $\widetilde{b}_{U_{i}}:=b_{i}\mathbf{1}-b$. Then the linear region $U_{i}$ is captured by the linear system of inequalities $\widetilde{A}_{U_{i}}x\leq\widetilde{b}_{U_{i}}$.

###### Definition 19 .

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be a tropical Puiseux polynomial. The *Hoffman constant of $f$* is

$$ $H(f)=\max_{U_{i}\in\mathcal{U}}H\big{(}\widetilde{A}_{U_{i}}\big{)}.$ $$

Care needs to be taken in defining the Hoffman constant of a tropical Puiseux rational map: we can no longer assume that all linear regions are defined by systems of linear inequalities, since such maps can admit non-convex linear regions. To bypass this difficulty, we consider convex refinements of linear regions induced by intersections of linear regions of tropical polynomials.

###### Definition 20 .

Let $p\oslash q$ be a difference of two tropical Puiseux polynomials. Let $A$ (respectively $A^{\prime}$) be the $m_{p}\times n$ (respectively $m_{q}\times n$) matrix of exponents for $p$ (respectively $q$), and $a$ (respectively $a^{\prime}$) the $i$th row vector of $A$ (respectively $A^{\prime}$). The Hoffman constant of $p\oslash q$ is

$$ $H(p\oslash q):=\max\bigg{\{}H\bigg{(}\begin{bmatrix}A\\ A^{\prime}\end{bmatrix}-\mathbf{1}\begin{bmatrix}a_{i}\\ a^{\prime}_{j}\end{bmatrix}\bigg{)}:i=1,\cdots,m_{p};\ j=1,\cdots,m_{q}\bigg{ \}}.$ (6) $$

Let $f$ be a tropical Puiseux rational map. Then the *Hoffman constant of $f$* is defined as the minimal Hoffman constant of $H(p\oslash q)$ over all possible expressions of $f=p\oslash q$.

As every neural network can be represented by a tropical Puiseux rational map, Definition 20 gives a notion of Hoffman constants for neural networks.

###### Definition 19 .

###### Definition 20 .

### 3.2 The Minimal Effective Radius

For a neural network whose tropical Puiseux rational map is $f:\mathbb{R}^{n}\to\mathbb{R}$, let $\mathcal{U}=\{U_{1},\ldots,U_{m}\}$ be the collection of its linear regions. For any $x\in\mathbb{R}^{n}$, define the *minimal effective radius* of $f$ at $x$ as

$$ $R_{f}(x):=\min\left\{r:B(x,r)\cap U\neq\varnothing,\,U\in\mathcal{U}\right\}$ $$

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$.

The following lemma relates the minimal effective radius to the Hoffman constant when $f$ is a tropical Puiseux polynomial.

###### Lemma 21 .

Let $f$ be a tropical Puiseux polynomial and $x\in\mathbb{R}^{n}$ be any point. Then

$$ $R_{f}(x)\leq H(f)\max_{U\in\mathcal{U}}\big{(}\big{\|}(\widetilde{A}_{U}x- \widetilde{b}_{U})_{+}\big{\|}\big{)}.$ (7) $$

###### Proof.

From the definition of minimal effective radius, we have

$$ $\displaystyle R_{f}(x)$ $\displaystyle=\min\left\{r:B(x,r)\cap U_{i}\neq\varnothing,U_{i}\in\mathcal{U}\right\}$ $\displaystyle=\min\{r:d(x,U_{i})\leq r,U_{i}\in\mathcal{U}\}$ $\displaystyle=\max\{d(x,U_{i}):U_{i}\in\mathcal{U}\}.$ $$

For each linear region $U_{i}$ characterized by $\widetilde{A}_{U_{i}}x\leq\widetilde{b}_{U_{i}}$, by (3) we have

$$ $d(x,U_{i})\leq H(\widetilde{A}_{U_{i}})\|(\widetilde{A}_{U_{i}}x-\widetilde{b} _{U_{i}})_{+}\|.$ $$

Passing to the maximum we have

$$ $\displaystyle R_{f}(x)$ $\displaystyle=\max_{U_{i}\in\mathcal{U}}d(x,U_{i})$ $\displaystyle\leq\max_{U_{i}\in\mathcal{U}}H(\widetilde{A}_{U_{i}})\max_{U_{i} \in\mathcal{U}}\left\|(\widetilde{A}_{U_{i}}x-\widetilde{b}_{U_{i}})_{+}\right\|$ $\displaystyle=H(f)\max_{U_{i}\in\mathcal{U}}\left\|(\widetilde{A}_{U_{i}}x- \widetilde{b}_{U_{i}})_{+}\right\|.$ $$

∎

In particular, we are interested in the case when $\mathbb{R}^{m}$ and $\mathbb{R}^{n}$ are equipped with the $\infty$-norm, where the minimal effective radius can be related to the Hoffman constant and function value of $f=p\oslash q$. For a tropical Puiseux polynomial $p(x)=\max_{1\leq i\leq m_{p}}\{a_{i}x+b_{i}\}$, we set $\check{p}(x)=\min_{1\leq j\leq m_{q}}\{a_{j}x+b_{j}\}$ to be its min-conjugate. We can then relate the minimal effective radius and the Hoffman constant of tropical Puiseux rational map as follows.

###### Proposition 22 .

Let $f=p\oslash q$ be a tropical Puiseux rational map. For any $x\in\mathbb{R}^{n}$, we have

$$ $R_{f}(x)\leq H(p\oslash q)\max\{p(x)-\check{p}(x),\,q(x)-\check{q}(x)\}.$ (8) $$

###### Proof.

The polyhedra defined by

$$ $\left(\begin{bmatrix}A\\ A^{\prime}\end{bmatrix}-\mathbf{1}\begin{pmatrix}a_{i}\\ a^{\prime}_{j}\end{pmatrix}\right)x\leq\begin{bmatrix}b_{i}\mathbf{1}-b\\ b^{\prime}_{j}\mathbf{1}-b^{\prime}\end{bmatrix}$ $$

form a convex refinement of linear regions of $f$. Let

$$ $\mathrm{res}_{i,j}(x):=\left(\begin{bmatrix}A\\ A^{\prime}\end{bmatrix}-\mathbf{1}\begin{bmatrix}a_{i}\\ a^{\prime}_{j}\end{bmatrix}\right)x-\begin{bmatrix}b_{i}\mathbf{1}-b\\ b_{j}\mathbf{1}-b^{\prime}\end{bmatrix}$ $$

denote the residual of $x$ to the polyhedron. We have

$$ $R_{f}(x)\leq H(p\oslash q)\max\left\{\|\mathrm{res}_{i,j}(x)_{+}\|_{\infty}:1 \leq i\leq m_{p}\,;1\leq j\leq m_{q}\right\}.$ $$

Note that

$$ $\displaystyle\|\mathrm{res}_{i,j}(x)_{+}\|_{\infty}$ $\displaystyle=\left\|\left(\begin{bmatrix}Ax+b-\mathbf{1}(a_{i}x+b_{i})\\ A^{\prime}x+b^{\prime}-\mathbf{1}(a^{\prime}_{j}x+b^{\prime}_{j})\end{bmatrix} \right)_{+}\right\|_{\infty}$ $\displaystyle=\max_{k,\ell}\left\{(Ax+b)_{k}-(a_{i}x+b_{i}),\,(A^{\prime}x+b^{ \prime})_{\ell}-(a^{\prime}_{j}x+b^{\prime}_{j}),\,0\right\}$ $\displaystyle=\max_{i,j}\left\{p(x)-(a_{i}x+b_{i}),\,q(x)-(a^{\prime}_{j}x+b^{ \prime}_{j}),\,0\right\}$ $$

Therefore,

$$ $\displaystyle\max_{i,j}\|\mathrm{res}_{i,j}(x)\|_{\infty}$ $\displaystyle=\max_{i,j}\left\{p(x)-(a_{i}x+b_{i}),\,q(x)-(a^{\prime}_{j}x+b^{ \prime}_{j}),\,0\right\}$ $\displaystyle=\max\left\{p(x)-\min_{i}\{a_{i}x+b_{i}\},\,q(x)-\min_{j}\{a^{ \prime}_{j}x+b^{\prime}_{j}\},\,0\right\}$ $\displaystyle=\max\left\{p(x)-\check{p}(x),\,q(x)-\check{q}(x)\right\}$ $$

which proves (8).
∎

Understanding the value $R_{f}(x)$ for various $x$ the input domain can be useful from the perspective of interpretability since the concentration of linear regions can be indicative of the learned structures of the network. Figure 4 shows the linear regions of a trained network concentrating along the boundary between the data sets. A full exploration of the application of these tools to interpretability is left for future work.

Figure: (a) The linear regions of a ReLU neural network at initialization.
Refer to caption: extracted/5911715/two-d_init.png

###### Lemma 21 .

###### Proof.

###### Proposition 22 .

###### Proof.

### 3.3 Computing and Estimating Hoffman Constants

##### The PVZ Algorithm.

In Peña et al. (), the authors proposed a combinatorial algorithm to compute the precise value of the Hoffman constant for a matrix $A\in\mathbb{R}^{m\times n}$, which we refer to as the *Peña–Vera–Zuluaga (PVZ) algorithm* and sketch its main steps here.

###### Definition 23 .

A set-valued map $\Phi:\mathbb{R}^{n}\to\mathbb{R}^{m}$ assigns a set $\Phi(x)\subseteq\mathbb{R}^{m}$. The map is surjective if $\Phi(\mathbb{R}^{n})=\cup_{x}\Phi(x)=\mathbb{R}^{m}$.
Let $A\in\mathbb{R}^{m\times n}$. For any $J\subseteq\{1,2,\ldots,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 $\Phi(x)=A_{J}x+\{y\in\mathbb{R}^{J}:y\geq 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 24 .

-
- 1.
If $J$ is such that $A_{J}$ is full-rank, then $J$ is $A$-surjective, since for any $y\in\mathbb{R}^{J}$, there exists $x\in\mathbb{R}^{n}$ such that $y=A_{J}x$.
- 2.
Let $A=\mathbf{1}_{m\times n}$ be the $m\times n$ matrix whose entries are 1’s. For any subset $J$ of $\{1,\ldots,m\}$ and for any $y\in\mathbb{R}^{J}$, let $x\in\mathbb{R}^{n}$ such that $\sum_{i}x_{i}\leq\min\{y_{j},j\in J\}$. Then $y-A_{J}x\geq 0$. Thus any $J$ is $A$-surjective.

The PVZ algorithm is based on the following characterization of the Hoffman constant.

###### Proposition 25 .

(Peña et al., , Proposition 2)
Let $A\in\mathbb{R}^{m\times n}$. Equip $\mathbb{R}^{m}$ and $\mathbb{R}^{n}$ with norm $\|\cdot\|$ and denote its dual norm by $\|\cdot\|^{*}$. Let $\mathcal{S}(A)$ be the set of all $A$-surjective sets. Then

$$ $H(A)=\max_{J\in\mathcal{S}(A)}H_{J}(A)$ (9) $$

where

$$ $H_{J}(A)=\max_{\begin{subarray}{c}y\in\mathbb{R}^{m}\end{subarray}\\ \|y\|\leq 1}\min_{\begin{subarray}{c}x\in\mathbb{R}^{n}\\ A_{J}x\leq y_{J}\end{subarray}}\|x\|=\frac{1}{\displaystyle\min_{\begin{ subarray}{c}v\in\mathbb{R}^{J}_{+},\|v\|^{*}=1\end{subarray}}\left\|A_{J}^{ \top}v\right\|^{*}}.$ (10) $$

This characterization is particularly useful when $\mathbb{R}^{m}$ and $\mathbb{R}^{n}$ are equipped with the $\infty$-norm, since the computation of (10) 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 $\mathcal{F}$, $\mathcal{I}$, and $\mathcal{J}$ where during every iteration: (i) $\mathcal{F}$ contains $J$ such that $J$ is $A$-surjective; (ii) $\mathcal{I}$ contains $J$ such that $J$ is not $A$-surjective; and (iii) $\mathcal{J}$ contains candidates $J$ whose $A$-surjectivity will be tested.

To detect whether a candidate $J\in\mathcal{J}$ is surjective, the PVZ algorithm requires solving

$$ $\min\left\|A^{\top}_{J}v\right\|_{1},\,\,s.t.\,\,v\in\mathbb{R}^{J}_{+},\|v\|_ {1}=1.$ (11) $$

If the optimal value is positive, then $J$ is $A$-surjective, and $J$ is assigned to $\mathcal{F}$ and all subsets of $J$ are removed from $\mathcal{J}$. Otherwise, the optimal value is 0 and there is $v\in\mathbb{R}^{J}_{+}$ such that $A^{\top}_{J}v=0$. Let $I(v)=\{i\in J:v_{i}>0\}$ and assign $I(v)$ to $\mathcal{I}$. Let $\hat{J}\in\mathcal{J}$ be any set containing $I(v)$. Replace all such $\hat{J}$ by sets $\hat{J}\backslash\{i\},i\in I(v)$ which are not contained in any sets in $\mathcal{F}$.

###### Definition 23 .

###### Example 24 .

###### Proposition 25 .

##### Lower and Upper Bounds.

A limitation of the PVZ algorithm is that during each loop, every set in $\mathcal{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,\ldots,m\}$ and test for $A$-surjectivity. This method bypasses optimizing combinatorially over $\mathcal{S}(A)$ of $A$-surjective sets and gives a lower bound of Hoffman constant by Proposition 25.

To get an upper of Hoffman constant, we use the following result from Güler et al. ().

###### Theorem 26 .

(Güler et al., , Theorem 4.2)
Let $A\in\mathbb{R}^{m\times n}$. Let $\mathcal{D}(A)$ be a set of subsets of $J\subseteq\{1,\ldots,m\}$ such that $A_{J}$ is full rank. Let $\mathcal{D}^{*}(A)$ be the set of maximal elements in $\mathcal{D}(A)$. Then the Hoffman constant measured under 2-norm is bounded by

$$ $H(A)\leq\max_{J\in\mathcal{D}^{*}(A)}\frac{1}{\hat{\rho}(A_{J})}$ (12) $$

where $\hat{\rho}(A)$ is the smallest singular value of $A$.

Using the fact that $\|\cdot\|_{1}\geq\|\cdot\|_{2}$, and the characterization from (10), we see that the upper bound also holds when $\mathbb{R}^{m}$ and $\mathbb{R}^{n}$ are equipped with the $\infty$-norm. However, enumerating all maximal elements in $\mathcal{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,\ldots,m\}$ and approximate the upper bound by (12).

Figure: Algorithm 1 Exact computation of the Hoffman constant

Figure: Algorithm 2 Lower bound for Hoffman constant

Figure: Algorithm 3 Upper bound for Hoffman constant

###### Theorem 26 .

##### Numerical Verification.

We verify our approaches on synthetic data. More specifically, we generate Puiseux rational maps by randomly generating two tropical Puiseux polynomials $p$ and $q$, with $m_{p}$ and $m_{q}$ monomials respectively. We do so by constructing an $m_{p}\times n$ matrix $A_{p}$ and an $m_{q}\times n$ matrix $A_{q}$ by uniformly sampling entries from $[0,1]$. We then form the matrix of (6) and compute the exact Hoffman constant along with approximations of its lower and upper bound by our proposed Algorithms 2 and 3. However, upon careful investigations of the public code provided by Peña et al. (), we find the output numerical values are unstable. To complete our experiments, we then tested examples without using the public code, and instead implemented a brute force computation by computing (11) over all submatrices. The brute force approach is given by Algorithm 1.

For the combination of different values $m_{p}$, $m_{q}$, $n$ and $B$, we repeat all computations 8 times. The true Hoffman constants, lower bounds, upper bounds, and the computation time can be found in Tables 2(d). Although we did not use PVZ algorithm to compute the exact values, for the sake of completeness, we also record the computation time and the number of calls to solve the LP problem within the loop of the PVZ algorithm. The number of iterations of the PVZ algorithm with the average time to solve the LP problems during each stage can be found in Tables 1(c),1(c),1(c). From the tables, we see that computing the true Hoffman constants requires solving over 1000 LP problems, which is computationally expensive. Although the lower and upper bounds can be loose, the computational times are much faster, which illustrates their practicality in real data applications.

**Table 1: Number of iterations in the PVZ algorithm and average time to solve LP during each iteration.**
| # iterations | 94 | 86 | 67 | 83 | 99 | 86 | 75 | 83 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Time per LP | 0.0042 | 0.0026 | 0.0025 | 0.0026 | 0.0025 | 0.0025 | 0.0026 | 0.0026 |

**Table 2: Lower bounds and true values of Hoffman constants**
| Sample | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Lower bounds $H_{L}$ | 0.239 | 0.153 | 0.209 | 0.316 | 0.366 | 0.361 | 0.374 | 0.399 |
| Time $H_{L}$ | 0.206 | 0.205 | 0.204 | 0.206 | 0.206 | 0.207 | 0.211 | 0.216 |
| True values $H$ | 0.555 | 0.621 | 0.594 | 1.105 | 1.142 | 0.649 | 0.778 | 1.876 |
| Time $H$ | 0.644 | 0.686 | 0.651 | 0.638 | 0.674 | 0.638 | 0.657 | 0.676 |
| Upper bounds $H^{U}$ | 1.033 | 0.906 | 0.899 | 1.966 | 1.784 | 1.183 | 1.448 | 2.728 |
| Time $H^{U}$ | 0.001 | 0.001 | 0.002 | 0.001 | 0.001 | 0.002 | 0.001 | 0.001 |

## 4 Symmetry and the Fundamental Domain

We now exploit our geometric characterization of linear regions of a neural network as polyhedra to optimize the estimation of the number of linear regions.

### 4.1 The Linear Structure of Invariant Networks

The notions of *invariance* and *equivariance* under symmetries are central to *geometric deep learning* (Bronstein et al., ), which leverages the inherent symmetries of data so that models generalize more effectively (Sannai and Imaizumi, ). In our setting, symmetries in a neural network induce symmetries in the linear structure of the network (see Figure 5), which we can exploit for computational gains.

Figure: (a)
Refer to caption: extracted/5911715/two-d_deepset.png

###### Definition 27 .

Let $f:{\mathbb{R}}^{n}\to{\mathbb{R}}$ be a function and let $G$ be a group acting on the domain ${\mathbb{R}}^{n}$. $f$ is said to be *invariant* under the group action of $G$ (or $G$-invariant) if for any $g\in G$, $f\circ g=f$.

We can define sampling domains for invariant neural networks which incorporate the effect of the group action.

###### Definition 28 .

Let $G$ be a group acting on ${\mathbb{R}}^{n}$. A subset $\Delta\subseteq{\mathbb{R}}^{n}$ is a *fundamental domain* if it satisfies the two following conditions: (i) ${\mathbb{R}}^{n}=\bigcup_{g\in G}g\cdot\Delta$; and (ii) $g\cdot\text{int}(\Delta)\cap h\cdot\text{int}(\Delta)=\varnothing$ for all $g,h\in G$ with $g\neq h$.

The fundamental domain of a group $G$ induces a periodic tiling of ${\mathbb{R}}^{n}$ by acting on $\Delta$. This is very useful in the context of numerical sampling for neural networks that 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. The upshot is that we can use far fewer samples while maintaining the same density of points.

###### Theorem 29 .

Let $f:{\mathbb{R}}^{n}\to{\mathbb{R}}$ be a tropical rational map invariant under the group action $G$. Let $\Delta\subseteq{\mathbb{R}}^{n}$ be a fundamental domain of $G$. Suppose $\mathcal{U}$ is the set of linear regions of $f$. Define the sets

$$ $\mathcal{U}_{c}:=\{A\in\mathcal{U}:A\subseteq\Delta\}\quad\text{ and }\quad \mathcal{U}_{e}:=\{A\in\mathcal{U}:A\cap\Delta\neq\varnothing\}.$ $$

Then

$$ $|G||\mathcal{U}_{c}|\leq|\mathcal{U}|\leq|G||\mathcal{U}_{c}|+\sum_{A\in \mathcal{U}_{e}\backslash\mathcal{U}_{c}}\frac{|G|}{|G_{A}|}.$ $$

where $|G_{A}|$ is the size of the stabilizer of $A$.

###### Definition 27 .

###### Definition 28 .

###### Theorem 29 .

### 4.2 Proof of Theorem 29

###### Proof.

For any linear region $A$, we denote the orbit of $A$ by $[A]$. The action of $G$ partitions $\mathcal{U}$ into a set of orbits $[\mathcal{U}]$, and thus

$$ $|\mathcal{U}|=\sum_{[A]\in[\mathcal{U}]}|[A]|.$ $$

From property (i) in the definition of a fundamental domain, we have

$$ $\bigcup_{A\in\mathcal{U}}A=\bigcup_{\sigma\in G}\sigma\cdot\Delta,$ $$

which implies the following estimate:

$$ $|\mathcal{U}|\geq\sum_{A\in\mathcal{U}_{c}}|[A]|=|G||\mathcal{U}_{c}|.$ $$

For any $A\in\mathcal{U}$, the orbit stabilizer theorem states that $|[A]||G_{A}|=|G|$. Thus we have

$$ $|\mathcal{U}|\leq\sum_{A\in\mathcal{U}_{e}}|[A]|\leq|G||\mathcal{U}_{c}|+\sum_ {A\in\mathcal{U}_{e}\backslash\mathcal{U}_{c}}\frac{|G|}{|G_{A}|}.$ $$

∎

Theorem 29 gives us a method for estimating the total number of linear regions from sampling in the fundamental domain using *multiplicity*, which we discuss next.

###### Proof.

### 4.3 Estimating Linear Regions Using the Fundamental Domain

We now demonstrate the performance improvements in counting linear regions gained by exploiting symmetry in the network architecture with a study of permutation invariant neural networks inspired by DeepSets (Zaheer et al., ). Our numerical sampling approach is detailed in Appendix 6.2 and inspired by recent work in this area (Goujon et al., ). Here, we focus on a specific sampling method for estimating the number of linear regions for illustrative purposes, but we emphasize that our approach based on Theorem 29 is readily adaptable to any method for determining the number of linear regions on a bounded domain.

A permutation invariant network is one that is invariant under the action of $S_{n}$ on coordinates (see Appendix 2.4). As a consequence of Lemma 18, this action has fundamental domain

$$ $\Delta=\{(x_{1},\ldots,x_{n}):x_{1}\geq x_{2}\geq\ldots\geq x_{n}\},$ $$

which is a tile in ${\mathbb{R}}^{n}$ that admits $n!$ translates by the $S_{n}$-action. Thus, despite restricting sampling to $\Delta$, we can still effectively gain information about linear regions outside $\Delta$.

To enumerate the linear regions of this neural network, we use a numerical technique (see Appendix 6.2). In particular, this method characterizes linear regions by associating them to the Jacobians of the neural network with respect to the inputs, meaning linear regions are identified by $n$-dimension real vectors. Thus, to estimate the number of linear regions of this neural network, we need to address the multiplicities of these vectors.

###### Lemma 30 .

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be a permutation invariant neural network as given by (2). Let $J$ be the Jacobian of the neural network at the point $x\in\mathbb{R}^{n}$. Then $f$ has at most

$$ $\mathrm{mult}(J)=\frac{n!}{\prod_{c\in C(J)}c!}$ $$

distinct linear regions with the corresponding linear map having Jacobian $J$, where $C(J)$ gives the counts of each of the elements of $J$.

###### Proof.

Note that since $f$ is permutation invariant, the Jacobian at $Px$, for a permutation matrix $P$, is equal to $J$. If $J$ has distinct elements, then the region is contained within the interior of the fundamental region, and thus by property (ii) of Definition 28 we obtain $n!$ factorial distinct regions with Jacobian $J$. On the other hand, if $J$ has an entry repeated $m$ times, then the region is symmetric under $m!$ permutations of $S_{n}$. Thus, there exists at most $\frac{n!}{m!}$ regions with Jacobian $J$, since some transformed regions may be connected and thus not be distinguished as separate linear regions. Generalizing this argument, it follows that a given Jacobian $J$ corresponds to at most

$$ $\mathrm{mult}(J)=\frac{n!}{\prod_{c\in C(J)}c!}$ $$

linear regions.
∎

By Lemma 30, the number of linear regions of the neural network can be estimated by $\sum_{J\in\mathcal{J}}\frac{n!}{\prod_{c\in C(J)}c!}$, where $\mathcal{J}$ are the Jacobians of the linear regions in $\Delta$ computed by Algorithm 5.
Consequently, we can estimate the number of linear regions of the neural network while reducing the number of point samples by a factor of $n!$. This provides a dramatic gain in computational efficiency via an upper bound rather than an exact number.

###### Lemma 30 .

###### Proof.

## 5 Linear Regions of Invariant Networks

Figure: Figure 6: Ratio estimates for different input sizes with standard deviation error bars.
Refer to caption: extracted/5911715/ratio_radius20_with_exc_time.png

In Figure 6, we present a comparison between the estimate of the number of linear regions of a permutation invariant when we utilize the fundamental domain and when we do not. We first initialize a permutation invariant network with $n$ input dimensions. Then we apply Algorithm 5 with $X=[-20,20]^{n}$ and $N=10^{n}$ to obtain an estimate that does not account for the symmetries of the network. To account for the symmetries, we instead apply Algorithm 5 with $X=[-20,20]^{n}\cap\Delta$ and $N=\frac{10^{n}}{n!}$ and account for the multiplicities using Lemma 30. We record the ratio of these estimates as well as the ratios of their execution times. Figure 6 shows the average of these values across 10 iterations of this procedure.

We observe that the fundamental domain estimate performs well for low dimensional inputs and provides significant improvements in execution time. Despite the divergence as the input dimension increases, this estimate is still useful because we are often more concerned with obtaining an upper bound on the expressivity of a neural network rather than an exact figure and the fundamental domain estimate does not undercount the number of linear regions.

## 6 Symbolic Neural Networks

In this section, we present our threefold contribution of symbolic tools for neural networks, comprising a new Julia library integrated into the system along with theoretical results: (i) an algorithm to determine algebraic representations of the linear regions of arbitrary tropical Puiseux rational functions; (ii) methods for computing the tropical representations of neural networks and simplifying them; and (iii) A new algebraic measure of expressivity for neural networks, *monomial complexity*.

The combinations of these tools allow us to compute algebraic representations of the linear regions of *arbitrary* neural networks, and determine their *exact* number of linear regions.

The Julia library forming a part of our symbolic contribution can be found in the following repository:
[https://github.com/Paul-Lez/tropicalnn](https://github.com/Paul-Lez/tropicalnn),

### 6.1 Linear Regions of Tropical Puiseux Rational Functions

##### Overview of the Algorithm.

We start by sketching our algorithm for determining the linear regions of tropical Puiseux rational functions. A more precise formulation is given as Algorithm 4, together with a proof of correctness (Theorem 31), and a Julia implementation.

When viewed as a function on the real numbers, a tropical Puiseux rational function $f=p\oslash q$ is simply the difference of two max terms: the numerator and the denominator. In particular, $f$ is linear on a region $R\subset{\mathbb{R}}^{n}$ whenever $p$ and $q$ are linear on $R$. This indicates that we should be able to determine the linear regions of $f$ once we know those of $p$ and $q$. More precisely, notice that if $U_{1},\dotsc,U_{s}$ are the linear regions of $p$ and $V_{1},\dotsc,V_{t}$ are the linear regions of $q$, then $f$ is linear on each of the intersections $U_{i}\cap V_{j}$, and these intersections cover the input space ${\mathbb{R}}^{n}$. However, we cannot conclude that the linear regions of $f$ are given by this collection of intersections, as the following issues may arise: some intersections may be empty or have dimension less than $n$; and some intersections may “glue” together to form a larger linear region of $f$ (see Appendix A for examples of these phenomena). Whether or not these arise usually depends on the $U_{i}$’s and $V_{j}$’s and has to do with the combinatorics of the arrangement of these objects in ${\mathbb{R}}^{n}$. After filtering out empty and lower-dimensional regions, and determining which intersections glue together, we obtain a list of regions in ${\mathbb{R}}^{n}$ (polyhedra or unions of polyhedra), which correspond to the linear regions of $f$.

##### Combinatorics of Polyhedral Arrangements.

In order for our tropical linear region algorithm to be implementable, we need a way of computationally determining the combinatorics of the arrangement of the $U_{i}$’s and $V_{j}$’s. The key here is the standard fact from tropical geometry that the linear regions of a tropical (Puiseux) polynomial are polyhedra whose defining inequalities can be determined from the coefficients and exponents of the polynomial (see Appendix 2.3 for more detail). Hence, we are left to deal with the combinatorics of polyhedral arrangements.

From Lemma 4, we have that the intersections of the linear regions of $p$ and $q$ are also polyhedra, and thus determining the non-emptiness or dimension of such objects are well-understood problems that can be solved using linear programming.
This means that we can (computably!) detect when some intersections may be empty or have dimension less than $n$ using polyhedral geometric tools.

Next, to deal with gluing intersections, we can once again reduce to a problem of intersections of polyhedra. Let us denote by $L_{i}$ the linear map representing $p$ on $P_{i}$ and similarly, we write $M_{j}$ for the linear map representing $q$ on $Q_{j}$. Then gluing intersections may arise when there exist tuples of indices $(i,j,k,\ell)$ that satisfy the following set of conditions, $(\star)$:

- (i)
The intersection $(U_{i}\cap V_{j})\cap(U_{k}\cap V_{\ell})$ is non-empty;
- (ii)
$f$ is represented by the same linear map on $U_{i}\cap V_{j}$ and on $U_{k}\cap V_{\ell}$; and
- (iii)
$\dim(U_{i}\cap V_{j})=\dim(U_{k}\cap V_{\ell})=n$.

Notice that $f$ is represented by the same linear map on $U_{i}\cap V_{j}$ and on $U_{k}\cap V_{\ell}$ if and only if the equality of linear maps $L_{i}-M_{j}=L_{k}-M_{\ell}$ holds. Thus we can computably determine when such indices arise. For some fixed indices $i,j$ such that $\dim U_{i}\cap V_{j}=n$, two cases can arise:

- (a)
Either there are no pairs of indices $(k,\ell)\neq(i,j)$ such that $(i,j,k,\ell)$ satisfies $(\star)$; or
- (b)
There exist pairs of indices $(k,\ell)\neq(i,j)$ such that $(i,j,k,\ell)$ satisfies $(\star)$.

When (a) occurs, $U_{i}\cap V_{j}$ is a linear region of $f$. We now focus on (b): Set $\mathcal{I}$ to be the set of all pairs of indices $(k,\ell)$ such that $(i,j,k,\ell)$ satisfies $(\star)$ and $F=L_{i}-M_{j}$. Then, $f$ is represented by $F$ on the (possibly disconnected) region

$$ $\bigcup_{(k,\ell)\in\mathcal{I}}U_{k}\cap V_{\ell},$ $$

and the linear regions where $f$ is represented by $F$ correspond to the connected components of this region. We can determine these computationally as unions of polyhedra by considering which pairwise intersections $(U_{k}\cap V_{\ell})\cap(U_{k^{\prime}}\cap V_{\ell^{\prime}})$ are empty for $(k,\ell),(k^{\prime},\ell^{\prime})\in\mathcal{I}$.

###### Notation .

If $f:{\mathbb{R}}^{n}\to{\mathbb{R}}$ is a piecewise linear function and $U\subset{\mathbb{R}}^{n}$ a subset on which $f$ is linear, we write $L(f,U)$ for the linear map representing $f$ on $U$.

Figure: Algorithm 4 Linear regions of tropical Puiseux rational functions

###### Theorem 31 (Correctness of Algorithm 4 ) .

Algorithm 4 computes the exact number of linear regions of a Puiseux rational function $f=p\oslash q$.

###### Proof.

Let $U_{1},\dotsc,U_{\ell}$ be the linear regions of $p$ and $L_{i}=L(p,U_{i})$. Similarly let $V_{1},\dotsc,V_{m}$ be the linear regions of $q$, and set $S_{j}=L(q,V_{j})$.
We take $T_{ij}=L_{i}-S_{j}$ and set

$$ $S=\left\{T_{ij}\mid U_{i}\cap V_{j}\text{ has dimension }n\right\}.$ $$

For $T\in S$, let $I(T)$ be the set of pairs $(i,j)$ such that $T=T_{ij}$, and $C(T)$ the connected components of

$$ $\bigcup_{(i,j)\in I(T)}U_{i}\cap V_{j}.$ $$

We need to check that the set of linear regions of $f$ is precisely the union

$$ $\mathcal{U}=\bigcup_{T\in S}C(T).$ $$

It suffices to check that:

- (i)
The elements of this set cover ${\mathbb{R}}^{n}$;
- (ii)
$f$ is linear on each region in $\mathcal{U}$; and
- (iii)
Each element $D$ in $\mathcal{U}$ is maximal in the sense that there is no (connected) region $E$ containing $D$ as a strict subset such that $f$ is linear on $E$.

(i) follows from the fact that the sets $\{U_{i}\cap V_{j}|\dim U_{i}\cap V_{j}=n\}$ cover $\mathbb{R}^{n}$; (ii) holds because by definition, any element of $\mathcal{U}$ is a subset of

$$ $\bigcup_{(i,j)\in I(T)}U_{i}\cap V_{j}$ $$

for some $T$ and the set of indices $I(T)$ was constructed precisely so that $f$ can be represented by the linear map $T$ on this union.
For (iii) it suffices to notice that

$$ $\bigcup_{(i,j)\in I(T)}U_{i}\cap V_{j}=\{x\in{\mathbb{R}}^{n}|\text{ There exists an open }N\text{ such that }x\in\overline{N},\text{ and }f|_{N}=T|_{N}\}$ $$

so connected components of this union are maximal connected regions of $\mathbb{R}^{n}$ on which $f$ is linear.

∎

###### Notation .

###### Theorem 31 (Correctness of Algorithm 4 ) .

###### Proof.

### 6.2 Numerical Estimation of Linear Regions

In this section, we briefly discuss another standard method for computing the linear regions of a neural network, and compare it to our *symbolic method*, i.e. Algorithm 4.

#### 6.2.1 A Numerical Algorithm

The method of numerical estimation we use is inspired by the recent work of Goujon et al. (). Specifically, to numerically estimate the number of linear regions of a neural network, we exploit the fact that the linear regions of a neural network correspond to regions where the gradient is constant. We evaluate the gradient on a sample of points in some bounded regions $X$ and identify the number of unique gradients we obtain. However, care needs to be taken at this step, since it may be the case that the same linear function operates on disconnected regions. In our symbolic approach, this would correspond to distinct linear regions. To try and account for this in our numerical approach, for points with the same Jacobian, we sample the model at their midpoint and compare this to the midpoint provided by the linear map. If these values differ, then the regions are disconnected. However, if the values do not differ, we still cannot be certain whether the region is connected or disconnected. Therefore, our numerical approach is likely to *underestimate* the number of linear regions in this instance, giving an overall conservative measure of expressivity. We summarize this technique with Algorithm 5.

Figure: Algorithm 5 Numerical estimation of neural network linear regions

There are a few sources of errors that arise in our method of numerical approximation that are important to note:

- 1.
We cannot be sure if our search radius captures all of the linear regions.
- 2.
It may be the case that disconnected regions are acted on by the same linear map. The symbolic approach would count these regions as distinct. In our numerical approach, we try to resolve this by additionally sampling at the midpoint of points with the same Jacobian, however, this does guarantee that we identify disconnected regions.
- 3.
From exploratory experiments, we observe that some linear regions are very small. Therefore, a highly refined grid would be required to identify them. As the dimension of the input increases, we require exponentially more points to maintain a certain density level, which quickly becomes infeasible.

#### 6.2.2 Comparison with the Symbolic Approach

Our contributions provide a symbolic approach for computing the linear regions of a given neural network. Specifically, we compute the tropical expression for a neural network and then use Algorithm 4 to compute its linear regions. The advantage of this approach is that we obtain an exact characterization of the linear regions of a neural network. However, as expected and as we will show, this approach is more computationally expensive and thus takes more time than numerical approaches such as Algorithm 5. Therefore, in practical situations, numerical approaches may still be preferred. However, our symbolic method can be used to assess the precision of these numerical approaches by comparing them to the ground truth.

Here we use both Algorithm 4 and Algorithm 5 to obtain the number of linear regions of neural networks of different architectures. We implement Algorithm 5 with $X$ as a cube of radius $R$ for multiple values of $R$ and using various sample sizes, due to the lack of an efficient method to set these parameters optimally. For each algorithm and configuration, we sample 25 neural networks. The results are presented in Table 3. For the tables containing the results of the numerical approach, $N$ denotes the number of points and $R$ denotes the search radius.

**(e) Symbolic calculation**
| Architecture | Linear regions | Runtime (s) |
| --- | --- | --- |
| $[2,6,1]$ | $11.84$ | $2.57$ |
| $[3,5,1]$ | $20.88$ | $4.76$ |
| $[4,4,1]$ | $14.2$ | $1.05$ |
| $[5,3,1]$ | $7.4$ | $0.35$ |
| $[6,2,1]$ | $4.0$ | $0.167$ |
| $[3,2,2,1]$ | $5.56$ | $25.18$ |
| $[3,3,2,1]$ | $14.72$ | $38.51$ |

We find here that the numerical approximations are on par with the symbolic computations but have the advantage of running faster. However, this precision is not guaranteed and we see it deteriorates for neural networks with larger architectures, probably as a consequence of some of the issues outlined above. One particular issue is too small a search radius, which cannot capture all of the linear regions. Indeed, for 4-layered networks, increasing the search radius improves the approximation.

### 6.3 Tropical Representations of Neural Networks

##### Our Contribution.

Any neural network with integer weights can be viewed as the function ${\mathbb{R}}^{n}\to{\mathbb{R}}$ associated to a tropical rational function (Zhang et al., ). This fact is used by Brandenburg et al. () as a theoretical tool, but to the best of our knowledge, this has not yet been implemented in practice for analyzing concrete neural networks. Our work fills this gap by developing Julia tools and investigating their theoretical foundations and practical applications.

##### Pruning Tropical Expressions.

Non-zero tropical Puiseux polynomials and rational maps induce functions $\mathbb{R}^{n}\to\mathbb{R}$. It is important to note that the algebraic expression contains strictly more information than the corresponding function since different tropical expressions can induce the same function. Since for neural networks, we are only concerned with the induced functions, it is natural to consider which tropical representations are optimal. Here, we use these in a qualitative sense: an optimal tropical representation has relatively few redundant monomials.

This observation extends to interpretability, where a goal is to find minimal expressions of neural networks. Tropical geometry has been used for finding such representations (Smyrnis et al., ; Smyrnis and Maragos, ), where the corresponding minimal representations have been studied in algebraic statistics (Tran and Wang, ). Our contribution brings a new perspective to expressivity as well as interpretability using polyhedral geometry.

If $g=\bigoplus_{j=1}^{m}a_{\alpha_{j}}T^{\alpha_{j}}$ is a tropical Puiseux polynomial in $n$ variables, then we can associate to each monomial $a_{\alpha_{i}}T^{\alpha_{i}}$ a polytope $P_{i}\subset{\mathbb{R}}^{n}$ such that the maximum in the expression

$$ $g(x)=\max_{j\in\{1,\dots,m\}}\left\{a_{\alpha_{j}}+\left\langle\alpha_{j},x \right\rangle\right\}$ (13) $$

is attained at the $i$th term precisely when $x\in P_{i}$ (see Appendix 2.3 for further details). The following lemma gives a natural criterion for detecting which monomials are redundant, based on the geometry of their associated polyhedra.

###### Lemma 32 .

The $i$th monomial can be removed from the expression of $g$ without changing the corresponding function ${\mathbb{R}}^{n}\to{\mathbb{R}}$ if and only if $\dim P_{i}<n$.

###### Proof.

Let $g=\bigoplus_{i}a_{i}T^{\alpha_{i}}$ be a tropical Puiseux polynomial, and let $P_{k}$ be the polytope associated to the $k$th monomial of the expression of $g$. Recall that $P_{k}$ is defined by the system of linear inequalities $(*)$

$$ $\langle\alpha_{j},x\rangle+a_{j}\leq\langle\alpha_{k},x\rangle+a_{k}\text{ for all }j\neq k.$ $$

Assume $\dim P_{k}<n$. Then, the system $(*)$ must contain at least one implicit equality

$$ $\langle\alpha_{j},x\rangle+a_{j}\leq\langle\alpha_{k},x\rangle+a_{k}$ $$

such that $\alpha_{j}\neq\alpha_{k}$. In particular, the maximum in
$g(x)=\max_{i}\langle\alpha_{i},x\rangle+a_{i}$
is attained at the $j$th term whenever it is attained at the $k$th term, and we can remove the $k$th term from the expression without modifying the corresponding function.

Conversely, let us assume that we can remove the $k$th monomial from the expression of $g$ without changing the corresponding function. Suppose for a contradiction that $P_{k}$ has dimension $n$. This implies that the system has no implicit equalities, and thus by Lemma 10 we can find a point $\bar{x}\in P_{k}$ such that all the inequalities in $(*)$ are strict. This contradicts our assumption on the redundancy of the $k$th monomial.
∎

In particular, this gives us a computable way of simplifying tropical expressions of neural networks and measuring their monomial complexity, which we present in Algorithm 6.

Figure: Algorithm 6 Pruning tropical expressions.

###### Lemma 32 .

###### Proof.

### 6.4 Monomials as a Measure of Expressivity

Various measures neural network expressivity have been proposed and studied, such as counting the linear regions of ReLU neural networks (Montúfar et al., ); measuring the effect of forward propagation on the length of 1D curves (Raghu et al., ); and evaluating the sum of the Betti numbers of decision regions (Bianchini et al., ). Our work focuses on the number of linear regions of the input domain partitioned by the neural network. We provide tools to evaluate this measure of expressivity exactly by capitalizing on the representation of neural networks as tropical Puiseux rational functions. As a consequence and byproduct of this approach, we obtain to another measure of neural network expressivity, namely the number of monomials in the tropical expression of the neural network which quantifies its *algebraic* complexity.

###### Definition 33 .

Let $f$ be a neural network, and $g\oslash h$ a tropical representation of $f$, i.e., a tropical Puiseux rational function whose underlying real-valued function equals $f$. If $g$ has $m$ irredundant monomials and $h$ has $n$ irredundant monomials then we define the *monomial complexity* of the representation $g\oslash h$ to be the pair $(m,n)$.

Intuitively, this captures how many linear terms needed to express the neural network. Notice that this measure is closely related to, but not identical to, the number of linear regions of a neural network.

###### Example 34 .

-
- 1.
If $g$ is a tropical polynomial then the number of irredundant monomials of $g$ is equal to the number of linear regions of $g$.
- 2.
If $f$ is a neural network with a tropical representation of monomial complexity $(m,n)$ then $f$ has at most $mn$ linear regions.

We emphasize that the number of linear regions and the number of monomials of a tropical expression are linked, but distinct. To provide intuition for how these two quantities are connected, Figure 7 shows the evolution of the number of linear regions as we vary the number of monomials of randomly generated Puiseux rational functions in 3 and 4 variables.

Figure: Figure 7: Left: Linear regions of a Puiseux rational function in 3 variables. Right: Linear regions of a Puiseux rational function in 4 variables.

###### Definition 33 .

###### Example 34 .

### 6.5 Symbolic Experiments

We now demonstrate the breadth of our symbolic contribution via proof-of-concept experiments. Our aim is to demonstrate the new possibilities that our approach opens up, rather than merely providing performance metrics. Focusing on small networks highlights the intuitive insights these tools can offer, which are essential for thorough understanding and effective application in the broader context of deep learning.

When explicitly computing linear regions of neural networks, it is common to restrict to low-dimensional input spaces and small architectures. For instance, various methods proposed by Serra et al. () have been used to analyze the linear regions of neural networks; Hu et al. () consider neural networks with at most 22 hidden neurons on bounded input domains. Our tools consider the full input domain of these neural networks, and provide an exact geometric characterization of the linear regions. This now makes previously inaccessible avenues available for analyzing the geometry of linear regions of networks (see Appendix A).

##### Characterizing the Width–Depth Separation.

Expressivity has been studied from various perspectives; Telgarsky () theoretically proves that depth outperforms width in neural networks. We have introduced the monomial count as a measure of expressivity (see Appendix 6.4 for the full development) and use it to experimentally validate and provide an alternative experimental study of Telgarsky ().

More specifically, we take neural networks with $d$-dimensional input domains with architectures $[d,k,1]$ and $[d,2,k,1]$ where $k\in\{2,\dots,7\}$. After randomly initializing these architectures we compute the number of monomials in their corresponding tropical representation. We sample 10 neural networks for each architecture to obtain an average number of monomials.

Figure: (a) Regular scale
Refer to caption: extracted/5911715/depth_analysis.png

From Figure 8, we observe that increasing the width of a layer in a deeper network leads to exponentially more monomials in the subsequent tropical expression.

##### Redundant Monomials.

Our tools construct the tropical representation of a neural network through a standard procedure involving the weights of the network, which leads to a *native* tropical representation of the neural network. A detailed investigation into the redundant monomials using Algorithm 6 that are present in this native tropical representation is beyond the scope of this work, although Appendix 6.4 outlines a basis for this exploration and for monomial complexity as a measure of expressivity that would be a potential source of future explorations. Here we simply illustrate some of the questions we can start asking using our tools.

A particularly interesting study is the pruning rate from the native tropical representation using our tools. We investigate how this rate depends on the network architecture and whether its weights are random or have undergone training. We generate constant-width neural networks and then compare the proportion of monomials in the corresponding representation that can be pruned. We consider this both when the network is randomly initialized and when the network is trained. From Figure 9 we see that trained neural networks exhibit a greater pruning rate.

Figure: Figure 9: The rate of monomial pruning for architectures with two input dimensions and a hidden layer with width as given by the $x$-axis.
Refer to caption: extracted/5911715/layer_1.png

##### At the MNIST Scale.

We now move beyond our proof-of-concept experiments to demonstrate the implementability of our tools on larger, practical neural networks. We train a neural network with a $[784,4,10]$ architecture on the MNIST dataset and achieve 85% accuracy on the train and test dataset. Using our tools we can obtain the neural network’s tropical representation, which has $144$ monomials. Moreover, we enumerate exactly its $9$ linear regions, along with their polyhedral representations. In particular, we can deduce that $8$ of the linear regions are on a single unbounded polyhedron; one linear region is a collection of several very small bounded polyhedra and one unbounded polyhedron.

## 7 Discussion: Limitations & Directions for Future Research

Our contributions offer theoretical and practical advancements in *tropical deep learning*, but are subject to some important limitations which in turn inspire directions for future research, which we now discuss.

##### Experimental Considerations.

Our methods have shown promising results for networks of moderate size, including those with input dimensions comparable to MNIST. However, as we scale to more complex architectures and higher dimensions, computational challenges persist. To further improve scalability, parallelization of our elementary computations could yield significant performance gains, as many of our algorithms involve repeating similar operations multiple times.

##### Structural Considerations.

Some of the problems we study are framed as combinatorial optimization problems, which are inherently challenging. For instance, computing the Hoffman constant, which is equivalent to the Stewart–Todd condition measure of a matrix, is known to be NP-hard in general cases (Peña et al., , ). This challenge could be addressed by employing approximate algorithms or algorithms that provide upper bounds on the Hoffman constant, since these would be sufficient for our purposes and computationally more tractable.

Our introduction of a new algebraic measure of expressivity provides fresh insights but also opens up new questions about its computational complexity and relationship to other expressivity measures.
The neural network pruning methods we have developed show promise in reducing model complexity while maintaining expressivity. However, further research is needed to fully understand the trade-offs between model size, expressivity, and performance across a wider range of architectures and tasks.

##### Future Directions.

These limitations inspire future work on both the practical and theoretical fronts. In practice, to achieve improved scalability, further studying and understanding where and how symbolic computation algorithms can be made more efficient, e.g., by parallelization or novel algorithmic approaches, would make our proposed methods more applicable to larger neural networks. Expanding our pruning methods to a broader range of architectures to investigate their impact on model performance in diverse tasks is a pathway to developing improved pruning techniques. Building on our initial empirical tests of theoretical expressivity results, a comprehensive empirical validation could help bridge the gap between theory and practice in neural network expressivity.

Theoretically, our tropical contributions have the potential to capture both expressivity and interpretability. Towards this end, a deeper exploration of our new algebraic expressivity measure, including its theoretical properties and practical implications, could yield valuable insights into neural network behavior. Perhaps most importantly, ours is the first work to forge a new intersection of symbolic computation and deep learning. Fostering collaboration between these fields will lead to novel algorithms and insights that leverage the strengths of both areas.

## Acknowledgments

Y.C. is funded by a President’s Scholarship at Imperial College London. P.L. is funded by a London School of Geometry and Number Theory–Imperial College London PhD studentship, which is supported by the Engineering and Physical Sciences Research Council [EP/S021590/1]. A.M. is supported by the Engineering and Physical Sciences Research Council under grant reference [EP/Y028872/1] and by a London Mathematical Society Emmy Noether Fellowship [EN-2223-01].

## Appendix A Computational Demonstration

We randomly initialize a ReLU neural network of architecture $[2,6,1]$, and deduce various properties using our tools. The native tropical representation of the network is

$$ $\displaystyle\bigg{(}\frac{8303211062024807}{18014398509481984}x_{1}^{\frac{53 15625921210391264531289425775}{2028240960365167042394725128601}}x_{2}^{\frac{4 2807318170191291834305564285899}{8112963841460668169578900514406}}$ $\displaystyle\oplus\frac{113798118771065816597402430375}{158456325028528675187 087900672}x_{1}^{\frac{6889937869568708339499981931275}{2028240960365167042394 725128601}}x_{2}^{\frac{75444231325898099640798371358899}{81129638414606681695 78900514406}}$ $\displaystyle\oplus\frac{-19844302439616671184375517979487}{811296384146066816 95789005144064}x_{1}^{\frac{1064890959119053184381174910843}{81129638414606681 69578900514406}}x_{2}^{\frac{60410920445114443123341361610413}{811296384146066 8169578900514406}}$ $\displaystyle\oplus\frac{38420334371169026913494526372513}{8112963841460668169 5789005144064}x_{1}^{\frac{17362138752552321484255944932843}{81129638414606681 69578900514406}}x_{2}^{\frac{93047833600821250929834168683413}{811296384146066 8169578900514406}}$ $\displaystyle\oplus\frac{-17603947378294062525056571070551}{811296384146066816 95789005144064}x_{1}^{\frac{6564683680998574221620489953367}{20282409603651670 42394725128601}}x_{2}^{\frac{27428459948081432536048514362851}{811296384146066 8169578900514406}}$ $\displaystyle\oplus\frac{40660689432491635572813473281449}{8112963841460668169 5789005144064}x_{1}^{\frac{8138995629356891296589182458867}{202824096036516704 2394725128601}}x_{2}^{\frac{60065373103788240342541321435851}{8112963841460668 169578900514406}}$ $\displaystyle\oplus\frac{-18724124908955366854716044525019}{405648192073033408 47894502572032}x_{1}^{\frac{96061121998271785012737977021211}{8112963841460668 169578900514406}}x_{2}^{\frac{45032062223004583825084311687365}{81129638414606 68169578900514406}}$ $\displaystyle\oplus\frac{10408193496437482194218977650981}{4056481920730334084 7894502572032}x_{1}^{\frac{42358369791705053312612747043211}{81129638414606681 69578900514406}}x_{2}^{\frac{77668975378711391631577118760365}{811296384146066 8169578900514406}}$ $\displaystyle\oplus\frac{3378044267536599337074993047453}{12676506002282294014 96703205376}x_{1}^{\frac{}{}}x_{2}^{\frac{58186019326277163785836989899259}{81 12963841460668169578900514406}}$ $\displaystyle\oplus\frac{44618467267239594276882973631597}{2028240960365167042 3947251286016}x_{1}^{\frac{9983496943818553840512815393871}{811296384146066816 9578900514406}}x_{2}^{\frac{0808532170376077030747169692439}{25353012004564588 0299340641075}}$ $\displaystyle\oplus\frac{8303211062024807}{18014398509481984}x_{1}^{\frac{5315 625921210391264531289425775}{2028240960365167042394725128601}}x_{2}^{\frac{428 07318170191291834305564285899}{8112963841460668169578900514406}}$ $\displaystyle\oplus\frac{-81656452117619827421182154083}{202824096036516704239 47251286016}x_{1}^{\frac{11246000628660118898637973096971}{8112963841460668169 578900514406}}x_{2}^{\frac{6905895518496787064523625284043}{507060240091291760 598681282150}}$ $\displaystyle\oplus\frac{64382118954969073630997358422927}{2028240960365167042 3947251286016}x_{1}^{\frac{6778740845753648164496920339037}{811296384146066816 9578900514406}}x_{2}^{\frac{43070706318462417398441659587307}{8112963841460668 169578900514406}}$ $\displaystyle\oplus\frac{13737969485405769628670110823819}{5070602400912917605 986812821504}x_{1}^{\frac{6690559447393050501252433933227}{2028240960365167042 394725128601}}x_{2}^{\frac{4422357277763732412282131240381}{507060240091291760 598681282150}}$ $\displaystyle\oplus\frac{19681995235611859526693202637247}{2028240960365167042 3947251286016}x_{1}^{\frac{8041244530595213222622078042137}{811296384146066816 9578900514406}}x_{2}^{\frac{27692005162376545446910233973947}{8112963841460668 169578900514406}}$ $\displaystyle\oplus\frac{2562938555566466102594071877399}{50706024009129176059 86812821504}x_{1}^{\frac{6003092684301720882891861679501}{10141204801825835211 97362564300}}x_{2}^{\frac{855594227754182707655708569773}{25353012004564588029 9340641075}}\bigg{)}$ $\displaystyle\oslash\bigg{(}0x_{1}^{\frac{5315625921210391264531289425775}{202 8240960365167042394725128601}}x_{2}^{\frac{42807318170191291834305564285899}{8 112963841460668169578900514406}}$ $\displaystyle\oplus\frac{113798118771065816597402430375}{158456325028528675187 087900672}x_{1}^{\frac{6889937869568708339499981931275}{2028240960365167042394 725128601}}x_{2}^{\frac{75444231325898099640798371358899}{81129638414606681695 78900514406}}$ $\displaystyle\oplus\frac{-19844302439616671184375517979487}{811296384146066816 95789005144064}x_{1}^{\frac{1064890959119053184381174910843}{81129638414606681 69578900514406}}x_{2}^{\frac{60410920445114443123341361610413}{811296384146066 8169578900514406}}$ $\displaystyle\oplus\frac{38420334371169026913494526372513}{8112963841460668169 5789005144064}x_{1}^{\frac{17362138752552321484255944932843}{81129638414606681 69578900514406}}x_{2}^{\frac{93047833600821250929834168683413}{811296384146066 8169578900514406}}$ $\displaystyle\oplus\frac{-17603947378294062525056571070551}{811296384146066816 95789005144064}x_{1}^{\frac{6564683680998574221620489953367}{20282409603651670 42394725128601}}x_{2}^{\frac{27428459948081432536048514362851}{811296384146066 8169578900514406}}$ $\displaystyle\oplus\frac{40660689432491635572813473281449}{8112963841460668169 5789005144064}x_{1}^{\frac{8138995629356891296589182458867}{202824096036516704 2394725128601}}x_{2}^{\frac{60065373103788240342541321435851}{8112963841460668 169578900514406}}$ $\displaystyle\oplus\frac{-18724124908955366854716044525019}{405648192073033408 47894502572032}x_{1}^{\frac{96061121998271785012737977021211}{8112963841460668 169578900514406}}x_{2}^{\frac{45032062223004583825084311687365}{81129638414606 68169578900514406}}$ $\displaystyle\oplus\frac{10408193496437482194218977650981}{4056481920730334084 7894502572032}x_{1}^{\frac{42358369791705053312612747043211}{81129638414606681 69578900514406}}x_{2}^{\frac{77668975378711391631577118760365}{811296384146066 8169578900514406}}\bigg{)}.$ $$

As we noted previously, redundant monomials may exist within this representation. Removing these gives the following reduced representation,

$$ $\displaystyle\bigg{(}\frac{8303211062024807}{18014398509481984}x_{1}^{\frac{53 15625921210391264531289425775}{2028240960365167042394725128601}}x_{2}^{\frac{4 2807318170191291834305564285899}{8112963841460668169578900514406}}$ $\displaystyle\oplus\frac{113798118771065816597402430375}{158456325028528675187 087900672}x_{1}^{\frac{6889937869568708339499981931275}{2028240960365167042394 725128601}}x_{2}^{\frac{75444231325898099640798371358899}{81129638414606681695 78900514406}}$ $\displaystyle\oplus\frac{-19844302439616671184375517979487}{811296384146066816 95789005144064}x_{1}^{\frac{1064890959119053184381174910843}{81129638414606681 69578900514406}}x_{2}^{\frac{60410920445114443123341361610413}{811296384146066 8169578900514406}}$ $\displaystyle\oplus\frac{38420334371169026913494526372513}{8112963841460668169 5789005144064}x_{1}^{\frac{17362138752552321484255944932843}{81129638414606681 69578900514406}}x_{2}^{\frac{93047833600821250929834168683413}{811296384146066 8169578900514406}}$ $\displaystyle\oplus\frac{40660689432491635572813473281449}{8112963841460668169 5789005144064}x_{1}^{\frac{8138995629356891296589182458867}{202824096036516704 2394725128601}}x_{2}^{\frac{60065373103788240342541321435851}{8112963841460668 169578900514406}}$ $\displaystyle\oplus\frac{10408193496437482194218977650981}{4056481920730334084 7894502572032}x_{1}^{\frac{42358369791705053312612747043211}{81129638414606681 69578900514406}}x_{2}^{\frac{77668975378711391631577118760365}{811296384146066 8169578900514406}}$ $\displaystyle\oplus\frac{3378044267536599337074993047453}{12676506002282294014 96703205376}x_{1}^{\frac{}{}}x_{2}^{\frac{58186019326277163785836989899259}{81 12963841460668169578900514406}}$ $\displaystyle\oplus\frac{8303211062024807}{18014398509481984}x_{1}^{\frac{5315 625921210391264531289425775}{2028240960365167042394725128601}}x_{2}^{\frac{428 07318170191291834305564285899}{8112963841460668169578900514406}}$ $\displaystyle\oplus\frac{64382118954969073630997358422927}{2028240960365167042 3947251286016}x_{1}^{\frac{6778740845753648164496920339037}{811296384146066816 9578900514406}}x_{2}^{\frac{43070706318462417398441659587307}{8112963841460668 169578900514406}}$ $\displaystyle\oplus\frac{13737969485405769628670110823819}{5070602400912917605 986812821504}x_{1}^{\frac{6690559447393050501252433933227}{2028240960365167042 394725128601}}x_{2}^{\frac{4422357277763732412282131240381}{507060240091291760 598681282150}}\bigg{)}$ $\displaystyle\oslash\bigg{(}0x_{1}^{\frac{5315625921210391264531289425775}{202 8240960365167042394725128601}}x_{2}^{\frac{42807318170191291834305564285899}{8 112963841460668169578900514406}}$ $\displaystyle\oplus\frac{113798118771065816597402430375}{158456325028528675187 087900672}x_{1}^{\frac{6889937869568708339499981931275}{2028240960365167042394 725128601}}x_{2}^{\frac{75444231325898099640798371358899}{81129638414606681695 78900514406}}$ $\displaystyle\oplus\frac{-19844302439616671184375517979487}{811296384146066816 95789005144064}x_{1}^{\frac{1064890959119053184381174910843}{81129638414606681 69578900514406}}x_{2}^{\frac{60410920445114443123341361610413}{811296384146066 8169578900514406}}$ $\displaystyle\oplus\frac{38420334371169026913494526372513}{8112963841460668169 5789005144064}x_{1}^{\frac{17362138752552321484255944932843}{81129638414606681 69578900514406}}x_{2}^{\frac{93047833600821250929834168683413}{811296384146066 8169578900514406}}$ $\displaystyle\oplus\frac{-17603947378294062525056571070551}{811296384146066816 95789005144064}x_{1}^{\frac{6564683680998574221620489953367}{20282409603651670 42394725128601}}x_{2}^{\frac{27428459948081432536048514362851}{811296384146066 8169578900514406}}$ $\displaystyle\oplus\frac{40660689432491635572813473281449}{8112963841460668169 5789005144064}x_{1}^{\frac{8138995629356891296589182458867}{202824096036516704 2394725128601}}x_{2}^{\frac{60065373103788240342541321435851}{8112963841460668 169578900514406}}$ $\displaystyle\oplus\frac{10408193496437482194218977650981}{4056481920730334084 7894502572032}x_{1}^{\frac{42358369791705053312612747043211}{81129638414606681 69578900514406}}x_{2}^{\frac{77668975378711391631577118760365}{811296384146066 8169578900514406}}\bigg{)}.$ $$

Since we have a 2-dimensional input domain, we can visualize the linear regions in which the neural network partitions the input domain, Figure 10(a). By leveraging the capabilities of the OSCAR library, we can further compute geometric quantities of the linear regions, such as their volumes, Table 5. The extent to which these measurements are useful for applications such as interpretability is left for future work.

Note how linear regions may be constructed as unions of convex polyhedra to form non-convex regions, for instance in Figure 10(a), we see that linear region 6 is constructed as the union of various convex polyhedra. Moreover, despite the same linear map acting on different polyhedra, these polyhedra may be disconnected and thus form separate linear regions, for instance in Figure 10(a) linear region 5 is acted on by the same linear map as linear region 6 but it is disconnected from linear region 6. Our Algorithm 4 accounts for both of these scenarios to ensure that an accurate enumeration of the linear regions is provided.

Figure: (a)
Refer to caption: extracted/5911715/two-d_demonstration.png

In Table 4, we explicitly identify the linear maps acting on the identified linear regions.

**Table 4: The linear maps referenced in the annotations of Figure 10(a).**
|  | Linear Map |
| --- | --- |
| 1 | $\frac{177774498751173330659305028664479}{81129638414606681695789005144064}+<br>\begin{pmatrix}x_{1}&x_{2}\end{pmatrix}\begin{pmatrix}-\frac{11736213875255232<br>1484255944932843}{81129638414606681695789005144064}\\<br>-\frac{67430907137272043571998589392077}{40564819207303340847894502572032}\end<br>{pmatrix}$ |
| 2 | $\frac{236039135561959028757175073016479}{81129638414606681695789005144064}+<br>\begin{pmatrix}x_{1}&x_{2}\end{pmatrix}\begin{pmatrix}-\frac{71064890959119053<br>184381174910843}{81129638414606681695789005144064}\\<br>-\frac{51112450559418639668752185855577}{40564819207303340847894502572032}\end<br>{pmatrix}$ |
| 3 | $\frac{175534143689850721999986081755543}{81129638414606681695789005144064}+<br>\begin{pmatrix}x_{1}&x_{2}\end{pmatrix}\begin{pmatrix}-\frac{58138995629356891<br>296589182458867}{20282409603651670423947251286016}\\<br>-\frac{117459611094442284794020721037}{5070602400912917605986812821504}\end{pmatrix}$ |
| 4 | $\frac{2467659317368072804295773604453}{1267650600228229401496703205376}+\begin<br>{pmatrix}x_{1}&x_{2}\end{pmatrix}\begin{pmatrix}-\frac{26889937869568708339499<br>981931275}{20282409603651670423947251286016}\\<br>-\frac{14657276499952616981870172682455}{10141204801825835211973625643008}\end<br>{pmatrix}$ |
| 5 | $0+\begin{pmatrix}x_{1}&x_{2}\end{pmatrix}\begin{pmatrix}0\\<br>0\end{pmatrix}$ |
| 6 | $\frac{64382118954969073630997358422927}{20282409603651670423947251286016}+<br>\begin{pmatrix}x_{1}&x_{2}\end{pmatrix}\begin{pmatrix}-\frac{44483762839087916<br>893628237364063}{81129638414606681695789005144064}\\<br>-\frac{6241769120366527326120747021831}{2535301200456458802993406410752}\end{pmatrix}$ |
| 7 | $\frac{275132423198170357049046004762259}{81129638414606681695789005144064}+<br>\begin{pmatrix}x_{1}&x_{2}\end{pmatrix}\begin{pmatrix}-\frac{16947999387824064<br>8721985039474431}{81129638414606681695789005144064}\\<br>-\frac{10544719203702376892200856846943}{10141204801825835211973625643008}\end<br>{pmatrix}$ |
| 8 | $\frac{57238640684530172339958449873759}{81129638414606681695789005144064}+<br>\begin{pmatrix}x_{1}&x_{2}\end{pmatrix}\begin{pmatrix}-\frac{98023872742774881<br>26256017207743}{81129638414606681695789005144064}\\<br>-\frac{8801801137461575644517898662257}{40564819207303340847894502572032}\end{pmatrix}$ |
| 9 | $-\frac{1025996126255525757911594478241}{81129638414606681695789005144064}+<br>\begin{pmatrix}x_{1}&x_{2}\end{pmatrix}\begin{pmatrix}-\frac{56099635067710756<br>426130787229743}{81129638414606681695789005144064}\\<br>-\frac{25120257715314979547764302198757}{40564819207303340847894502572032}\end<br>{pmatrix}$ |
| 10 | $\frac{216867786387384658951175960410259}{81129638414606681695789005144064}+<br>\begin{pmatrix}x_{1}&x_{2}\end{pmatrix}\begin{pmatrix}-\frac{21577724167167391<br>7021859809496431}{81129638414606681695789005144064}\\<br>-\frac{3656083337041431967003114432767}{2535301200456458802993406410752}\end{pmatrix}$ |
| 11 | $\frac{49815959752272649106529847334927}{20282409603651670423947251286016}+<br>\begin{pmatrix}x_{1}&x_{2}\end{pmatrix}\begin{pmatrix}-\frac{90781010632521185<br>193503007386063}{81129638414606681695789005144064}\\<br>-\frac{29046690625929460280294588971449}{10141204801825835211973625643008}\end<br>{pmatrix}$ |
| 12 | $\frac{3378044267536599337074993047453}{1267650600228229401496703205376}+\begin<br>{pmatrix}x_{1}&x_{2}\end{pmatrix}\begin{pmatrix}-\frac{15315625921210391264531<br>289425775}{20282409603651670423947251286016}\\<br>-\frac{5288831177744633003029285899165}{5070602400912917605986812821504}\end{pmatrix}$ |
| 13 | $\frac{179146822334000678485908299899655}{81129638414606681695789005144064}+<br>\begin{pmatrix}x_{1}&x_{2}\end{pmatrix}\begin{pmatrix}-\frac{51810545227454800<br>99417093565705}{2535301200456458802993406410752}\\<br>-\frac{129307656659568521746027221589755}{81129638414606681695789005144064}<br>\end{pmatrix}$ |

**Table 5: Volumes of the linear regions identified in Figure 10(a).**
| Linear Region | Volume |
| --- | --- |
| 1 | $3.9158$ |
| 2 | Unbounded |
| 3 | $0.0196$ |
| 4 | $3.8078$ |
| 5 | $0.0043$ |
| 6 | Unbounded |
| 7 | Unbounded |
| 8 | Unbounded |
| 9 | $0.1942$ |
| 10 | $0.029$ |
| 11 | $1.7305$ |
| 12 | $1.0766$ |
| 13 | Unbounded |
| 14 | Unbounded |

## Appendix B Further Experimental Details

Experiments were run on an i7-1165G7 CPU with 16GB of RAM. Table 6 lists the time taken by each experiment. Given that our experiments do not include training on large datasets, the experiments are not particularly expensive from the perspective of memory usage, and all the code can be run on a laptop. The detail provided in the paper corresponds roughly to the amount of computational resources that were used for this work, omitting trial and testing runs.

The code used to run the experiments, including the Julia library forming a part of our symbolic contribution, can be found in the following repository:
[https://github.com/Paul-Lez/tropicalnn](https://github.com/Paul-Lez/tropicalnn)

**Table 6: Compute details.**
| Experiment | Compute time |
| --- | --- |
| Characterizing the width–depth separation | $65.2$ minutes |
| Redundant monomials | $1.84$ minutes |
| At the MNIST scale | $2.68$ minutes |
| Table 3, symbolic calculations | $29.06$ minutes |
| Table 3, numerical calculations | $6.13$ minutes |
| Linear regions of invariant neural networks, Figure 6 | $24.63$ minutes |

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: See Weakness.
soundness: 3
strengths: **Clarity:** The paper is well-organized, exhibiting a clear and logical progression from the theoretical background to the main results and their implications. Each section is thoughtfully introduced with specific motivations that enhance the reader's understanding. Notably, the three contributions are effectively aligned with their corresponding sections, reinforcing the connections among the presented ideas.

**Novelty and Significance:** The innovative application of tropical geometry to evaluate the expressivity of neural networks introduces valuable insights. By translating neural networks into tropical representations, the authors utilize tools from an underexplored area of deep learning theory. Their approach, which provides an exact count of linear regions and introduces monomial complexity as a measure of expressivity, has the potential to inspire future research on model architecture and optimization.


**Practical Implementation:** The integration into OSCAR allows for symbolic manipulation of neural networks, which has practical implications for further research and applications.
summary: This paper presents a novel approach to investigating the expressivity of neural networks through the framework of tropical geometry, a branch of algebraic geometry that employs combinatorial and polyhedral methods, with key contributions including a new framework for selecting bounded sampling domains using the Hoffman constant, a method for enhancing computational efficiency through symmetry in network architecture, and a Julia library integrated into the OSCAR system for symbolic representation and analysis of neural networks using tropical techniques. The paper builds on foundational work that connects tropical rational maps with feedforward neural networks, providing theoretical insights supported by experiments that demonstrate its applicability across various network architectures. Overall, I believe this paper makes a significant contribution to the theoretical foundations of deep learning.
weaknesses: **Limited Empirical Validation:** The experimental demonstrations, while useful as proofs of concept, are mainly limited to small-scale networks.

**Context within Existing Methods:** A more in-depth discussion on how this tropical approach compares to or enhances traditional methods of region counting and expressivity analysis would provide valuable context.

**Notation Clarity:** Some notations in the main paper are not defined in a timely manner. For example, $P(A,b)$ is defined in Line 673 of the appendix but is used in Line 146 of Section 2 without prior explanation.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: In terms of questions:

- Early in the introduction the authors mention that expressivity is one of the most important approaches to measure performance. Are the authors aware of any references to support that claim? Usually overly complex networks (i.e., very expressive ones) tend to overfit the data and lead to poor performance, exactly the opposite of what the authors are arguing.
- Given that the purpose of the paper is to aid our understanding of deep networks, there seems to be a limited intuitive explanation of the methods that are used. For example, what is an intuitive explanation of the Hoffman constant? Section 2.1 makes an attempt at explaining, but actually describes the distance $d(u, P(A, B))$ and not the constant, and does so by restating the equation instead of an intuitive explanation.
- About the fundamental domain:
    - It seems that things only work for discrete groups, if so that should be a concrete discussion.
    - There is mention of groups acting on vector spaces, but no discussion about group representations (or at least how these groups act on the vector spaces) is presented.
    - The authors state that in the specific example of 3.2, a factorial improvement is made. However, clearly, $\Delta$ is an infinite set. There is no asymptotic analysis as to how many samples we need from $\Delta$, so how are you claiming an improvement without a sampling statement when sampling from an infinite set?
- Line 395 is very imprecise. What does information mean here? The expression and the function both encode the same function.
- On 423, the authors argue their use of small networks saying that they help highlight intuitive insights that can aid understanding. What are the insights that are gained in doing so? Of the three presented experiments, the first one has no comparison on depth vs width (which is the titular motivation for the section), the second one shows a marginal change which is unclear if it would persist when the layers/nodes increase, and the final one has no takeaways listed.
soundness: 3
strengths: The paper tackles important problems that can aid our understanding of deep networks. Tropical geometry has been getting increasingly popular in recent years, and has been the tool of choice for geometric analyses using polyhedral geometry. The introduction of the manuscript is crisp and easy to follow, introducing the main subject areas and discussing the contributions clearly. Finally, there is a significant number of contributions.
summary: This paper studies the expressivity of neural networks through a tropical lens. Through a suite of algebraic tools, the authors characterize the linear regions of a neural network using the Hoffman constant, discuss sampling improvements for invariant neural networks through the fundamental domain, and provide a symbolic framework for computing linear regions of neural networks.
weaknesses: The weaknesses of the work can be summarized in the following axes:

- a severe lack of polish after the introduction,
- confusing results, mainly due to the number of contributions,
- it is unclear what the benefits of the contributions are, either at a theoretical or a empirical level.

**Lack of polish**

All main sections of the paper are introduced very abruptly, and the defining concepts of each of them are delegated to the appendices. This makes the paper extremely difficult to read, and is currently not self-contained without the appendices. Examples of this is the complete omission of a discussion on tropical polynomials, the discussion of Lemma A.19 or Equation 9 without their exposition, and all algorithms being discussed, but never presented, to name a few.

There are many typos and there is a lack of explanations at multiple points in the paper. An example of this lack are Figures 2 and 3, where, beyond the typos, Figure 2 lacks any real caption and what is portrayed in these figures, what the colors mean, or why there is a different number of lines on Fig 2(a) and Fig 2(b) is not clear.

Overall while the three different contributions are connected, the connection is not emphasized and the presentation really hinders the readability and the flow of the work. By trying to include all of them in the same work, it becomes extremely difficult to present each contribution in a clear and rigorous manner, especially at such a page limit. I believe the work could greatly benefit from either splitting the contributions, or investing a significant effort in crafting a coherent thread that connects the contributions, most likely at a venue with a much higher page limit.

**Confusing results**

In terms of the Hoffman constant, it seems that the authors compute the constant, then use it to find the radius of a ball that is needed to intersect all the linear regions. However, if I’m understanding things correctly, this gives no estimate on the number of linear regions. Essentially we have to compute the Hoffman constant (which is NP-hard), and then have to sample many points in that radius to get a probabilistic statement about the number of regions given a sampling size, and even then I don’t see any statements of that effect. Most works I’m aware of on counting the number of linear regions do it without having access to a trained network, and are statements about the architecture, not the specific network, so I’m unsure exactly what the main contribution is here.

Section 4.1 is also confusing and the contribution is again unclear. For example, in line 359 it is stated that we can detect when some intersections may be empty. The way this is stated implies that we have a way of checking if intersections are empty, but not a way to find such intersections. That seems to actually be the case, since on 377 a set of indices I is assumed instead of being computed. A similar comment as above can be made, that this works for specific networks and does not characterize the network class. Also, how are we computing these regions? Are we combinatorially testing all combinations?

**Experimental results**

Simply put, the experimental section is very rushed and the results are not convincing (more in the next section). Starting of with the characterization of width versus depth, what exactly is Figure 4 conveying? There is no comparison between depth versus width, for the same number of neurons. The fact that expressivity increases when we increase the number of nodes is not surprising. A minor comment is also that the range of $k$ doesn’t correctly correspond to Figure 4.

For Figure 5, the trained and untrained networks seem to hardly have any difference in their pruning rate, and the size of the network is so small where no trends could be observed.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: - What is the benefit of relating the Hoffman constant to the radius of the ball? Are there any approximations for the Hoffman constant of a rational Puiseux function? Has the Hoffman constant been applied to Puiseux polynomials (and/or rational functions) in prior work?

- Assuming we know the Hoffman constant, are there theoretical guarantees that using it would lead to better sampling to estimate the number of linear regions?

- Is the definition of the Hoffman constant for a Puiseux rational map well-defined (Definition 2.2)? How do you deal with the fact that there can be infinitely many quotients?

- In the introduction, the paper mentions, “Our library opens the door for the extensive theory and existing software on symbolic computation and computational tropical geometry to be used to study neural networks." Could you provide an example of a property of a function computed by a neural network that is now accessible through symbolic computation but was previously inaccessible? A more detailed explanation of these advantages would be helpful.

- Why is the native tropical representation for neural networks useful for measuring complexity? Can you comment on how this representation compares to the best representation as a tropical rational function in terms of monomial complexity?
soundness: 3
strengths: The number of linear regions is a standard measure of complexity for neural networks with piecewise linear activation functions, and the authors provide new insights into computing this count for a given network. Specifically, they relate the minimal effective radius to the Hoffman constant of a tropical Puiseux rational map. Additionally, for invariant neural networks, their observation allows a significant reduction in the number of samples required to estimate the number of linear regions.
summary: The paper investigates counting the linear regions of neural networks through tropical geometry. The authors relate the Hoffman constant of a tropical rational map to the minimal effective radius, which is the smallest radius $r$ such that a ball of radius $r$ intersects all linear regions. They further show that for an invariant network (with respect to a group $G$), one can sample from the fundamental domain of $G$ to obtain an upper bound on the number of linear regions. Lastly, the authors introduce an algorithm using symbolic representation to compute the number of linear regions and propose a new measure of complexity for ReLU neural networks, termed the “monomial count.”
weaknesses: Overall, the contributions of the paper do not appear substantial enough, leading me to recommend rejection. The theoretical depth is limited, and I see few immediate practical benefits from the results, see also the questions below.
-  While relating the Hoffman constant to the radius of the ball may have theoretical appeal, I do not see its practical benefit, as it is NP-hard to compute the Hoffman constant. The appendix discusses computing the Hoffman constant of a matrix, but there is no discussion about the Hoffman constant for a rational Puiseux function, which is what relates to the radius of the ball. 
- The result concerning sampling from the fundamental domain of the group action for an invariant network appears to be a straightforward observation. 
- The algorithm for determining linear regions using Puiseux polynomials does not seem to offer clear advantages over existing methods. The paper states, “Our tools consider the full input domain of these neural networks and provide an exact geometric characterization of the linear regions. This now makes previously inaccessible avenues available for analyzing the geometry of linear regions of networks (see Appendix I)." However, algorithms for obtaining the entire polyhedral complex of neural networks already exist (e.g., Masden, 2022, https://arxiv.org/abs/2207.07696).

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1) In Theorem 3.3, what happens if the group is infinite? Shouldn't your theorem imply that the number of linear regions is infinite in this case? Or will it also be true that the set U_c is empty such that your lower bound becomes trivially equal to 0?

2) A priory, more monomials does not necessarily mean more expressivity, since the monomials could satisfy some internal (algebraic) relations/constraints. For instance, in classical algebra, the polynomials that are large powers of linear terms (i.e., that are of the form (a*x+b)^N for some fixed large N) have many monomials but they can only express a small portion (namely, a 2-dimensional subset) of the function space. Does this behavior happen for the tropical representations of ReLU neural networks? If yes, then a more accurate measure of expressivity would be the dimension of the semi-algebraic set that consists of all tropical rational functions that a fixed network architectures parametrizes, as studied in the article "Functional dimension of feedforward ReLU neural networks" by Grigsby, Lindsey, Meyerhoff, Wu. 

3) I don't understand what is meant with the number of monomials in Figure 9, since both the numerator and denominator have monomials. Do you plot the sum of the number of monomials of both numerator and denominator? Wouldn't in be better to also plot the product to get an idea of how far the upper bound in Example E.2 is?
soundness: 3
strengths: Originality: The definition of the Hoffman constant and its usage for sampling linear regions is novel, to the best of my knowledge. Also, I believe that the monomial count expressivity measure has not been studied before.

Significance: I think it will be very helpful for future research that the authors made their software available within the open-source OSCAR library. The proposed ideas of the Hoffman constant and the fundamental region might play a significant role in the future understanding of finding all linear regions of a piecewise linear network.

Quality and clarity: The paper is well-written. The mathematical statements are sound and the experiments make sense.
summary: The authors study some theoretical and computational aspects of neural networks with piecewise linear activation functions. In Section 2, they are interested in the number of linear regions of such a network. They define the minimal effective radius around an input point as the smallest radius such that a ball of that radius intersects all the linear regions. They bound that radius from above by a Hoffman constant associated with the network. The main advertised application of that is that one can in principle enumerate all linear regions by sampling dense enough inside a ball of their estimated radius.

In Section 3, the authors consider networks that are invariant under a given group action. They provide lower and upper bounds on the number of linear regions by making use of the fundamental domain of the group action. Since the fundamental domain gives a tiling of the input space, the authors further explain that sampling inside the fundamental domain suffices to enumerate all linear regions.

In Section 4, the authors explain their software contribution. They provide a symbolic algorithm that finds all linear regions of a network once one has a representation of the network as a tropical rational function. The authors also suggest to measure the expressivity of a network by the number of monomial required in a tropical rational function representation. They provide an algorithm that reduces unnecessary monomials in a given representation. 

The authors conclude with some experiments and discussion, but their main contributions are the theoretical contributions in Sections 2 and 3, and their software contribution described in Section 4.
weaknesses: My main concern is whether the paper's contributions are strong enough, which consist mainly of the author's software and their idea of the Hoffman constant to find a bounded region in the input space that intersects all linear regions. Making use of the fundamental domain of a given group action is a rather folklore idea, and regarding the monomial count expressivity measure I have some questions (see below). Moreover, and also very important: The paper oversells its contributions. I strongly suggest to tone down the description of the contributions and focus on describing what exactly is done instead.

1) For instance, the last sentence of the abstract is way too bold. The authors claim to provide "the foundations" but it is rather a small piece of the puzzle.

2)  Another example is the sentence "We study more than simply the number of linear regions, we provide further insight on their geometry". The only new geometric aspect I can see is the definition of the minimal effective radius. But that does not really give us new insights about the geometric properties of the regions, such as their size/volume, their number of facets or vertices, or any other information about the combinatorial type of the polytopes. I suggest to remove the sentence in question completely.

3) Similarly, in line 088, the authors write that the Hoffman constant "effectively gives a geometric characterization". I do not agree with that half-sentence, since the constant does not tell us (almost) anything about the geometric properties of the linear regions; it only tells us how "far away" the regions are at most located. If the authors have something else in mind, I suggest to replace the vague and way too broad statement "geometric characterization" by the exact properties the Hoffman constant tells us.

4) I also think that the phrase "guarantee for the linear regions" in line 088 is too strong. Please be more specific on what that guarantee means. The authors provide a largest region for where one has to sample. But if the sample is not dense enough, one will still miss linear regions (as the authors note in the appendix).

5) It is always hard to claim to have the "first work" as in line 531. Symbolic experiments on other deep learning architectures have for instance been done in "Pure and Spurious Critical Points: a Geometric Study of Linear Networks" by Trager, Kohn, Bruna or in "Geometry of Linear Convolutional Networks" by Kohn, Merkh, Montúfar, Trager.

Finally, here some smaller comments:

- Please add "piecewise" before "linear" in the first line of the abstract.

- I think it is inaccurate to call tropical geometry a "reinterpretation" of algebraic geometry. It is rather a "discrete version" of algebraic geometry.

- In line 139.5, remove one of the 2 words "its the"

- In lines 176 and 177, the row vectors a and a' should have an index i. That is, they should be a_i resp. a'_i.

- In line 191, it would be better to spell out "for all" before "U" to increase clarity.

- In line 205, should m_p and m_q be equal?

- In line 212, insert "in" after "x"

- typo in caption of Figure 3

Meta-review: The authors studied characterizations of a neural network's piecewise linear regions via tropical geometry. In particular, the authors found a ball that intersects all linear regions, and characterized the radius in terms of the Hoffman constant. Furthermore, the authors introduced a software library for the computational aspects of this research. 

There are several concerns, and many reviewers asked about the Hoffman constant and how it is NP-hard to compute. Broadly speaking, there are questions about how will this characterization be useful. For example, reviewer 5XwZ raised the concern about how the number of linear regions is related to complexity measures of neural networks. 

Given the discussion and the current scores, I will recommend reject.

Decision: Reject