Semialgebraic Neural Networks: From roots to representations
Authors: S David Mis
Matti Lassas
Maarten V. de Hoop
Venue: ICLR 2025 Poster (2025)
Keywords: deep learning
semialgebraic functions
homotopy continuation
real algebraic geometry
recurrent neural networks
Primary area: learning theory
TL;DR: We present a neural network architecture, grounded in classical homotopy continuation methods for root-finding, that can exactly represent any bounded semialgebraic function.

Abstract: Many numerical algorithms in scientific computing—particularly in areas like numerical linear algebra, PDE simulation, and inverse problems—produce outputs that can be represented by semialgebraic functions; that is, the graph of the computed function can be described by finitely many polynomial equalities and inequalities. In this work, we introduce Semialgebraic Neural Networks (SANNs), a neural network architecture capable of representing any bounded semialgebraic function, and computing such functions up to the accuracy of a numerical ODE solver chosen by the programmer. Conceptually, we encode the graph of the learned function as the kernel of a piecewise polynomial selected from a class of functions whose roots can be evaluated using a particular homotopy continuation method. We show by construction that the SANN architecture is able to execute this continuation method, thus evaluating the learned semialgebraic function. Furthermore, the architecture can exactly represent even discontinuous semialgebraic functions by executing a continuation method on each connected component of the target function. Lastly, we provide example applications of these networks and show they can be trained with traditional deep-learning techniques.

outputs Published as a conference paper at ICLR 2025
SEMIALGEBRAIC NEURAL NETWORKS: FROM ROOTS TO REPRESENTATIONS
S. David Mis Rice University dmis@r aniisriien priiceee edu
Matti Lassas
Maarten V. de Hoop
University of Helsinki matti waw.saasssssssssssseeeseese sinkai
Rice University
mdehoope edu
ABSTRACT
Many numerical algorithms in scientific computing-particlarry in areas like nu- merical linear algebra, PDE simulation, and inverse that can be represented by semialgebraic functions; that is, the graph of the com- puted function can be described by finitely many polynomial equalities and in- equalities. In this work, we introduce Semialgebraic Neural Networks (SANNs), a neural network architecture capable of representing any bounded semialgebraic function, and computing such functions up the accuracy of numerical ODE solver chosen by the programmer. Conceptually, we encode the graph of the learned function the kernel of piecewise polynomial selected from class of functions whose roots can be evaluated using a particular homotopy continuation method. We show by construction that the SANN architecture is able to execute this continuation method, thus evaluating the learned semialgebraic function. Fur- thermore, the architecture can exactly represent even discontinuous semialgebraic functions by executing continuation method on each connected component of the target function. Lastly, we provide example applications of these networks and show they can be trained with traditional deep-learning techniques.
INTRODUCTION
Many classical numerical algorithms compute semialgebraic functions-functiion whose graphs are defined by finitely many polynomial equalities and inequalities. Such functions include anything computable using finitely many real variables and finitely many operations addition, subtraction, multiplication, division, extraction of roots, and branching if statements with polynomial deci- sion boundaries. Familiar primitives from numerical linear algebra, such as solving linear systems, Schur complements, and extraction of real eigenvalues are also semialgebraic, as are the solution op- erators of optimization problems with polynomial objective functions and constraints (Press et al., 2007). Polynomial functions of re-th roots v are widely used in computation eigenvalues non- symmetric matrices and in the perturbation theory of eigenvalues of linear operators (Kato, 1995). Also, Finite Element approximations partial differential equations lead to solving linear systems whose solutions are semialgebraic functions (Beltzer, 1990). Due to their ubiquity, it is likely that the space of semialgebraic functions provides good inductive bias for operator learning with neu- ral networks. This ansatz leads to our central question: Is possible design a neural network architecture capable of exactly representing any semialgebraic function?
In this paper, we combine techniques from classical numerical analysis, namely polynomial homo- topy continuation methods for root finding, with ReLU activation functions to create neural networks capable of exactly representing any bounded semialgebraic function. The starting point for our idea is the observation that, under mild conditions, the graph of semialgebraic function F' given by the relation F(x) = y can be encoded as the kernel of a continuous piecewise polynomial G, i.e. the set of (I, y) where G(r,, y) = 0 (Section 2). Therefore, in principle, we can use a neural network com- bining polynomials and ReLU activations to learn G, then append a root-finding procedure such as in manner similar to Bai et al. (2019). However, this straightforward approach has numerous practical difficulties: there is no guarantee such a neural network would have root y for every x, roots may not be unique, the root-finding procedure may never converge, etc. To remedy these issues, we take inspiration from homotopy con- tinuation methods for root finding. We construct function H (x, y, 8) that continuously deforms
Newton's method to compute F(x)= root (oot(G(rr))) :)

---

Published as a conference paper at ICLR 2025
from simple function Go to the target function G:
(1) We use H to find a root of G by starting at a root of the simpler function Go at 8 = 0, then slowly increasing and tracking the motion of the root. In classical homotopy continuation methods, this procedure is carried out by numerically solving an ODE initial value problem describing the motion of y as a function of s. With a properly constructed H, this procedure is powerful enough to compute the roots of G, even if Gn bears little resemblance to G (Theorem 37).
(rr y, 0) = Go(z,y)
H ((). G(x
Instead of using a neural network to compute G directly, our Semialgebraic Neural Networks (SANNs) compute the vector field of an ODE system arising from homotopy continuation method to find a root of G (Section 3). We then integrate across the interval & E [0. 1] using an off-the-shelf ODE solver. This approach is powerful enough to represent all bounded semialgebraic functions in the sense that F(x) is the exact solution to the ODE initial value problem (Section 4). This ap- proach always has a well-defined output, avoids costly explicit root-finding procedures, and has fixed evaluation time when using a non-adaptive ODE solver. To our knowledge, we present the first neu- ral networks capable of computing arbitrary bounded semialgebraic functions on high-dimensional data.
1.1 RELATED WORK
Implicit deep learning. SANNS fall within the general framework of "implicit deep learning" (El Ghaoui et al., 2021; Kolter et al., 2020), particularly as popularized by Neural ODEs (Chen al., 2019) and Deep Equilibrium Models (Bai et al., 2019). In particular, SANNs can be trained using the adjoint sensitivity method (Pontryagin et al., 1962) in manner similar to Neural ODEs. Unlike Neural ODEs, where the ODE is fixed (based on network weights) and the initial value is based on the network input SANNS instead define a family of ODEs parameterized by x and the initial value is fixed. Importantly, Neural ODEs compute diffeomorphisms (Dupont et al., 2019), while SANNs compute bounded semialgebraic functions, which may not be continuous or differen- tiable everywhere. Compared to Deep Equilibrium Models, the SANN architecture does not include an explicit root- not-finding or fixed-point computation step; instead SANNs dircetly parameterize ho- motopy continuation method for root-finding
Semialgebraic machine learning. There are many neural network architectures designed repre- sent important subsets of semialgebraic functions. For example, polynomials and piecewise poly- nomials are computed by de Hoop et al. (2022); Chrysos et al. (2021); Oh et al. (2003), and certain rational functions are computed by Boullé et al. (2020). We are unaware of prior neural networks designed to represent the entire class of bounded semialgebraic functions as whole. An exciting complementary approach to semialgebraic approximation has been developed by Marx et al. (2021), where they encode semialgebraic functions as the optima of functions constructed from Christoffel- Darboux polynomials. Their approach is developed within the framework of classical approximation theory and data analysis rather than neural networks.
1.2 OUR CONTRIBUTION
We introduce the SANN architecture and provide an exact characterization of the functions it repre- sents. Our key contributions are as follows:
We present the SANN architecture (Algorithm 1), new object grounded in classical homotopy continuation methods for root-finding, that is capable of exactly representing any bounded semialgebraic function.
Definition of SANNs:
Exact characterization of expressivity: We rigorously characterize the expressivity of SANNs (Section 4), proving their ability represent all continuous bounded semialgebraic functions via homotopy continuation argument (Section 4.1).
Extension to discontinuous functions:
Building on the homotopy continuation framework, extend our results to show that SANNs can also represent discontinuous bounded semialgebraic functions through constructive proofs (Section 4.2).
We also argue SANNs are naturally suited to a wide variety of difficult problems, with applications to solving linear systems (Section 5), nonlinear inverse problems (Section F), general optimization
2

---

Published as a conference paper at ICLR 2025
t=0
t=0.2 t=0.4 t=0.6 t=0.8
t=1.0
Figure I: Computing the Hcaviside step function F (plotted in red) using homotopy method. The graph of F subset of the kernel of higher-dimensional piecewise polynomial G. In the upper row, we plot the surface of a homotopy H such that H (xx, y. 0) = O is trivial to solve (upper left), and (a. y, 1) = (upper right). The kernel of H shown with a green line (red points are also on top of the green line). The bottom row shows the projection of H onto to zy-plane. We compute from time kernel of G' contains points outside the graph of F (the visible parts of the green lines), these points are never encountered when computing by following the homotopy. This process captures the discontinuity exactly, including the isolated point at (0,0).
F(x) = y by following the kernel
to / 1, keeping æ fixed. Although the
problems (Section G.1), and transformers (Section G.3). We also demonstrate through numerical experiments that SANNs can be trained using standard techniques (Sections 5.2 and F.1),, and discuss future research directions (Section 6).
2 BACKGROUND
2.1 INF-SUP DEFINABLE PIRCEWISE POLYNOMIALS
Our networks are constructed from the piecewise polynomials formed by combining polynomials with ReLU activations. Using these components, maximum of any finite collection of polynomials. In mathematical literature, such structures are referred to lattices. Instead of "min" and "max," the terms "inf" and "sup" are traditionally used in lattice theory; since our constructions rely heavily on lattice theory, we adopt this terminology here. Notably, do a set of functions that is closed under the "min" and "max" operations.
represent the pointwise minimum and
the word "lattice" refer grid-like structure (e.g., 2d), but rather
We begin by defining the class of functions that form the backbone R[21.... mm)] refers to the set of polynomials of variables æ Zm with coefficients from R.
constructions. The notation
Definition 1 (Inf-sup definable piecewise polynomials). Let C Th. ISD(D) is the lattice generated by the polynomials R[21, Fm.. viewed as functions D - IR. together with the min and max operations. The vectors of n TSD(D) D) functions are denoted TSD Ih²). For any non- negative integer kt (DD are the k-times differentiable functions in / (DD,D,)))
The shorthand "f is ISD" means f ISD(D, IR" for some appropriate D and Our nomencla- ture is taken from Mahé (1984) and Mahé (2007).
Summarizing, the components Sa of function f ISD(D, RS), D C R can be written
fx(x)
min 1=1 i=l...!! j=l....
max
21 02
2
Om
I
(2), L2 Im).
Later, when we consider fa as a layer of a neural network, the coefficients Cg it.ij.. are used the parameters which are optimized in training process.
3

---

Published as a conference paper at ICLR 2025
Since the min and max operations can be written using the ReLU function, all ISD functions be written as feed forward neural network where the first hidden layer one has several different polynomial activation functions followed by fully connected ReLU layers. Furthermore, Henriksen & Isbell (1962) showed TSD( D, IR*) forms ring, so the sum and product of any ISD function is itself ISD (see Theorem 22 in Appendix A). Thus TSD(D) D, IR&)) precisely the functions D I that can be represented using finitely many, arbitrarily interleaved vector additions, Hadamard products, scalar multiplications and ReLU activations on variables from D.
We focus our attention on ISD functions since these are the piecewise polynomials computable using neural networks that combine polynomials and ReLU activations. There are many ways construct such networks; we provide an example based on Operator Recurrent Neural Networks (de Hoop al., 2022) in Appendix B, along with proofs of the expressivity of that architecture. Our approach can be adapted to analyze the expressivity of other polynomial networks with ReLU activations as well, such as those proposed by Chrysos al. (2021).
It is currently unknown whether every continuous real piecewise polynomial is ISD; this is the fa- mous Pierce-Birkhoff conjecture (Bochnak & Efroymson, 1980; Madden, 2011). ISD functions suf- fice for our purpose to build semialgebraic neural networks, regardless whether the Pierce-Birkhoff conjecture ultimately holds or not.
Definition 2 (Locally ISD functions). A function f R + R is locally ISD, denoted f IS 11o [R,,, if for every bounded C RT, fID ISD(D,R").
Appendix A contains additional background information on lattice theory.
2.2 SEMIALGEBRAIC GEOMETRY
We present the basic properties of semialgebraic introduction to semialgebraic geometry can be found in the first chapters of Bochnak et al. (1998).
relevant SANNs. A more thorough
Definition 3 (Basic semialgebraic set). A set D C R is basic semialgebraic set if there exists J2 N and finite sets of polynomials P {p. 3 Q {1)) C. R[ 2m) such that
= fa E IR p2x) = 0, ( < for all p E P, q Q}.
Definition 4 (Semialgebraic set). A set D R m is semialgebraic set if it is the union of finitely many basic semialgebraic sets.
Finite unions, finite intersections, complements, projections, closures, and interiors of semialgebraic sets are all semialgebraic themselves, a result the famous Tarski-Seidenberg theorem (Tarski, 1951; Seidenberg, 1954) (on the formulation of the Tarski-Seidenberg theorem we use in this paper, see Appendix E.9). Furthermore, every closed semialgebraic set can be defined using only non-strict inequalities (Lojasiewicz, 1964).
Definition (Semialgebraic function). f Rm + Rn is semialgebraic function if its graph is semialgebraic subset of I x R".
Special cases of semialgebraic functions include (piecewise) polynomials and (piecewise) rational functions, among others. For example, the graph of x + 1/2 is the set { 2) E R² zy = 1}.
Example 6. Consider the semialgebraic function F' IR + R below.
(a + 1)²
2 2 < -1
F(x) =
vI - x²
E [0.1]
0
1 -
x> 1.
2
3
F is polynomial when 1, rational function when 1, and neither when æ E [0, 1]. It has a single discontinuity at x = -1, and its graph is not closed there. It is unbounded as x - -0, but becomes bounded whenever the domain is restricted from below.
4

---

Published as a conference paper at ICLR 2025
2.3 SEMIALGEBRAIC FUNCTIONS AS KERNELS OF ISD FUNCTIONS
In this subsection, we show how to represent semialgebraic sets as the kernel of ISD functions. This is a semialgebraic analogue to the standard technique differential geometry of constructing smooth manifolds from the level sets of smooth functions (Lee, 2013). Proofs for Proposition 7 and Corollary as well as additional commentary and an illustration can be found in Appendix C.
Proposition 7. S C. IT is closed semialgebraic set if and only if there exists ISD-(RRm Rgo) such that ker(f) = S, where ker(s) == {z E R f(x) 0}.
We extend the above theorem to graphs of vector-valued semialgebraic functions with closed graphs. Corollary 8. F Rm + R is a semialgebraic function with closed graph if and only if there exists G E ISD' (IRTh IR", 20)) such that ker(G) gr(F), where gr(F) = {(z, F(x)) 12th x is the graph of F.
Corollary makes it computationally possible to find points of the graph of the semialgebraic func- tion F by using SANN related to ISD function G, as we will in Section 4.
SEMIALGEBRAIC NEURAL NETWORKS
3.1 ISD NETWORKS
SANNs are built from auxiliary networks capable computing ISD functions; we call such net- works "ISD networks". As discussed in Section 2, there are various ways to design such networks. An example architecture and its expressivity theorems are provided in Appendix B.
To streamline notation, we define a class of ISD functions that will be used frequently:
Definition 9. IS Dnett(mm, n, k) IS Bath x R, ((nt))((++)) Ra**)
A function in ISDnel(m, k) accepts three parameters x E RT E Ra+k and IR, and it returns a matrix M ((*+t)x(*+k) and vector b E R(++)), We further decompose where y E R" the output the computed semialgebraic function and E IR* are auxiliary "time" variables needed for the homotopy continuation constructions in Section 4. Including these auxiliary variables is analogous to "lifting" (i.e. increasing the width) common in many architectures. Such lifting is required for narrow ReLU networks to be universal approximators in the infinite- layer limit (Lu et al., 2017). A similar strategy is used in Dupont et al. (2019) to augment Neural ODEs.
(y, t).
We require only & = 1 in constructions, but it is easy extend the arguments to k > 1. Larger values of l may have practical benefits not captured by the characterization of the range of SANNS presented here, and we leave that investigation for future work.
3.2 SANN ARCHITECTURE
We define SANNs be functions of the form fN : : 1l2N. where A 1SDnet(m, k),
N E N, Cmax > 0, x E RT and nN is obtained by an approximation of the solution of an ordinary differential equation, that is, by setting 2g 0 and defining for j 0, I....,N
Zj+1 = ODE-step (أ)) N) = 23 + 2
where
M (M( zj b) x ))
1 clamp-sol
33)
Matrix M (2,, 2, and vector b(x, z, 8) are the output of an ISD network N Va,,,,8) The function clamp-sol is defined
clamp-sol(M, clammp(M -1b, -Cmaxs Cmax) if M is invertible
(4)
otherwise.
5

---

Published as a conference paper at ICLR 2025
Mo bo
clamp-sol
ODE-step
Mx-1
clamp-sol
ODE-sten
Z1
4-1
by-1
žN-1
20
y
Figure 2: Architecture diagram for SANN. The SANN outputs y semialgebraic function of input I. Vectors are the current values of an ODE at timestep j. The time-derivative & is computed using neural network N capable of computing ISD piecewise polynomials. N accepts the current ODE state (zj, vector b, from which 2ÿ is computed using clamp-sol M, b) (& = M-1b in the common case). ODE-step is single update of numerical ODE solver. Finally, II is projection operation such that y is the first n components of z.
well as recurrent input z. The output of W is matrix M and
The function "clamp" operates womponent-wise each element of a vector, and is defined
a,
a E [low, high]
clamp(u, low, high) = low,
low
(5)
high
a high.
These functions guarantee the iteration (3) is well-defined even when A produces singular or nearly- singular output matrices .. Lastly, IT projects onto the first components of its input.
The iteration (3) is the Euler -ifie-difference scheme that approximates the solution of the ODE
{(s) clamp-sol(M b(r, z)s) x0) = 0.
(7)
As N + oc, the output of the finite difference scheme converges to the solution of the ODE. These limit functions are of the form fkmm... /Coms x + (1=(1) that are defined by the ODE (6)-(7). We call these functions the limit functions of SANNs and denote those by SAN A (N, Cmax). We note that the forward -uller definition for ODE step used in (2) can be replaced with other numerical solvers, such as Runge- Kutta methods.
3.3 SANN ARCHITECTURE: ALGORITHMIC PRESENTATION
The above definition the SANN architecture is amenable to mathematical analysis. Algorithm an alternative presentation that elosely reflects how SANN may be implemented in functional programming style. It is completely equivalent to the description above.
Algorithm Evaluating SANN
Require: NEIS IISDnet(m,
&ER Cmax RR20 1: function SANN(N, I. Cmax)
2: function á(z, s)
3:
(M. b) + (xx 8)
4: if M singular then
5:
return 0
6:
else
7:
return clamp(M-a)) -Cmaxx Cmax) (y.t) ODESolve (0,0)
8:
9:
return y

---

Published as a conference paper at ICLR 2025
In Algorithm 1, ODESolve(3.2(0) outputs 2N according the finite difference scheme in for- mulas (2), or another numerical solver chosen by the programmer. This interface reflects popular libraries for numerically solving ODEs, e.g. Malengier et al. (2018); Kidger (2021).
Remark. Our expressivity proofs below refer to the true solution x(1) the ODE (6)-(7) rather than the numerical solution 2N. The numerical ODE solver may introduce approximation error into SANNs, even for semialgebraic functions, but this approximation error is of fundamentally different character than that which normally arises in neural networks, and the mitigation strategies will be different for SANNs. For example, increasing the number of steps N will decrease the approximation error without increasing the number of parameters in the network. On the other hand, increasing the number of parameters in N does not decrease the approximation error, as it generally would for other architectures. Furthermore, SANNs may be constructed using other numerical strategies besides the fiite-differenee scheme (2). Changing this scheme does not affect our expressivity proofs in this paper, but there may be other implications in practice.
3.4 TRAINING
In the supervised learning regime, we are given training data ((a(0,100)
= 1, L..
y F(x(0) where the target semialgebraic function. The output of SANN with input
(I) = 2 In our (N(x) == Il and the intermediate update directions given in equation (3) are üز experiments, we found it helpful to include a "direction loss" term to train each yj for j 1, N:
N
1
y( - (1)( + (1 (1-2) 1
Ldirection (z(1)) =
Σ
( N
Us (x
(z()
(8)
N
Lncouracy (z(00) = uN(o!())
Liotal
Laccuracy (z(1))
Adirrection
(2(1)
where À is small, suitably chosen parameter, e.g. X 10-2, Ldirection reflects the accuracy loss if the direction vector úU were held constant for the remainder of the numerical integration.
4 EXPRESSIVITY OF SANNS
In this section, we show that SANNS are capable of exactly representing any bounded semialgebraic function. We start by showing that every continuous semialgebraic function can be evaluated by particular homotopy continuation method that computable by iteratively solving the ODE (6)-(7) with different parameter functions N. We then extend this result to cover discontinuous semial- gebraic functions by first separating each connected component of the graph, applying results for the continuous case to obtain homotopies that represent each piece, then glucing these homotopies together in a manner consistent with ODE (6)-(7 to obtain the SANN. Additional details, includ- ing background in semialgebraic geometry and full proofs of the theorems present here, are in Appendices D and E.
4.1 CONTINUOUS SEMIALGEBRAIC FUNCTIONS
This section introduces family of homotopies Hr,a from which we can construct continuation method to evaluate the roots of ISD functions.
Let up uH be positive real numbers and Up (-uP, up)". Consider the family of homotopies
Hg : R x R + R", parameterized by (z, a) E R. x Ur, defined
Hz,a(y,t) = t) a) + + (g(z, y) + G(x,y))
(10)
where g E ISDI
loc m x R", RS)) and G E ISD! (IR' x R", R"). Each Hz,a is constructed from ring operations locally ISD functions, it is locally ISD itself.
We always evaluate Hz keeping x fixed; to simplify notation, let gu = g(x, .) and G2 == G(x,
For construction to work, we require 9u to be 0 on UF and grow quickly outside Up. Specifically, for every x E Rmm, we require GN o(gx) and id, o(gz), where we have used Landau "little-o" notation; e.g. G2 o(gx) means lim p
Gzlu) 0.
9. (*)

---

Published as a conference paper at ICLR 2025
The next lemma shows how to construct 9x based only on UF-
Lemma 10. There exists 9 DSD (IR R", ,,,," ..") such that gr on Up and for every G ISD x R", ).
, we have G2= = o(gx).
Proof. Let un = up, " - = (-uj; for E N. Notice R Uド=1 Uj. Define piecewise as follows:
VEUF
g(z = EE=
(1I)
U U,-1, for each J E EN denotes repeated component multiplication.) This g is not ISD since it is defined over infimitely many regions, but is locally ISD. Furthermore, the local degree of increases without bound ||yll oo, so g eventually dominates any polynomial. Thus G2 = o(gz) for any ISD G. Finally, it is straightforward to verify g is continuously differentiable.
-
(The exponent
The next theorem shows the family of homotopies in equation (10) is capable of representing any continuous bounded semialgebraic function F' for almost every choice of a; more precisely every except possibly on a semialgebraic set of dimension less than n (c.f. the Transversality theorem in D.I). The requirement that F' be bounded is always satisfied when the domain of continuous F compact, which is common and reasonable assumption in the context of machine learning with finite training data. The proof of Theorem 11 is in appendix E.
Theorem 11. Let F I - Up be a given continuous semialgebraic function. For every x T there exists Hz,a with the form (10) such that for almost every a E Ur, the following hold:
1. There exists y E ISD( 1]. R"), ISD((O, 1J, R), such that t(0) 0, t(1) = 1, and (18) E ker(Hz,a) for all E 10.
2. The kernel of (=) the singleton {F(x)).
Theorem 11 is used as follows: When t = 0 the function y + H (y, 0) has the root a. We apply the curve-tracing algorithm by solving the ODE (30)-(33) (see Appendix D.3) for the function Hz to find roots of the functions Hz,a( (-, (-,t) with t E [0, 1]. The root of Hz,a( 1) gives y = Fxx)
Conclusion 1 guarantees the homotopy Hz,a (v. t) can be solved to time t 1 for almost every choice of a; SANNs correspond to the choice a = O. Conclusion guarantees this solution is indeed the desired value ((r)..
To prove that SANNS can represent any continuous semialgebraic function, we need only show that the ODE (7) defining SANNs can recapitulate the ODE (30)-(33) defining the H homotopy continuation method. A full proof is in Appendix E.
Theorem 12. Let F T > Up be given continuous semialgebruic Then there exists N TSDnet(m, n, 1) and Cmax > such that SANN (N, ,,,, Cmax) F.
4.2 DISCONTINCOUS GEBIALGEBRAIC FUNCTIONS
Discontinuities can arise in the ODE (6)-() since the value of = M- can be discontinuous across a boundary where M singular. Consider the simple example
(-1 x <0
M Jabs (x)]
[xr] á Maamp-so((M,,
(12)
x x>0, 0,
where the sla operation is defined with Coaz = 2. We exploit this behavior to show via construction that SANNs can exactly represent even discontinuous semialgebraic functions.
Theorem 13. Let F R + R" be a (possibly discontinuous) bounded semialgebraic function. Then there exists N E ISDnet(m, n, 1) and Cmax E R2 such that SANNlim (N, Cmax)
Every semialgebraic set has finitely many semialgebraic connected components, so every semialge- braic function is piecewise continuous finitely many pieces. Our approach is to first show how we are able to represent the characteristic function of semialgebraic sets using the ODE (6)-(7). From these, represent semialgebraic decomposition of the domain R. and apply the continuous homotopy arguments above on each continuous region. We finally glue everything together in a way consistent with solving the ODE (7). The full proof is in Appendix E.
8

---

Published as a conference paper at ICLR 2025
5 NUMERICAL EXAMPLE: SOLVING LINEAR SYSTEMS
In this section, we give an example of a numerical algorithm that can be exactly represented by SANN, Specifically, we construct SANN that exactly computes (to machine precision) the solution to linear system Xy b, something that is not possible for standard neural network architectures. The parameters for this exact reconstruction are chosen by hand; we also show that SANNs can be trained from data using traditional techniques to perform comparably to feed-forward networks.
We focus on the Jacobi iteration method for solving dense linear systems Xy y = 9- Split X into its diagonal part D, upper-triangular part U, and lower-triangular part T..
d1
U
X
=
D = diag d1,
(13)
dn
From any initial guess yo. the Jacobi iteration method computes the iteration yj using
M/41 (g (L U)2,).
(14)
Adding yj Mj to the right side and simplifying yields
Øi+1 y! + D Xy,)
(15)
The sequence of iterates (y1, 32. computed in this way converges to the exact solution y" = X- when the spectral radius of D (L + U' is less than 1. is exactly of the form (2), and thus computable by a SANN with an appropriate ISD network N.
An additional numerical example addressing nonlinear inverse problem for electrical resistor net- works is in Appendix F. The problem to find the values an unknown resistivity function on a graph from the voltage-to-current measurements is encountered Electrical Impedance Tomography (Borcea, 2002), a medical imaging modality, and its mathematical treatment based on Finite Element approximation partial differential equation (Lassas et al., 2015).
subset of the nodes of the graph. This problem
5.1 EXACT INVERSION USING A HAND-CRAFTED NETWORK
To demonstrate the new possibilities afforded by the expressive power of SANNs, we manually configured the parameters of SANN to replicate the classical Jacobi iteration for solving linear systems, With this setup, the SANN is able to solve the system to machine precision-something standard feed-forward networks, which compute only piecewise-linear functions, cannot achieve. Figure shows the error of Hz decrease to machine precision for several inputs (X,9)
10-1
Trajectories of a SANN that solves linear systems to machine precision. Given matrix X E 500 and vector E TR500 the network produces vector y R550 such that Xy = 6. Each line shows the trajectory of the output y for a given input pair (X, g) as the SANN's ODE is iteratively solved. At each timestep, the network performs single Jacobi iteration update. The output of the network ex- actly matches the output of 100 steps of Jacobi iteration.
Figure 3:
Accuracy (xxy, gl1))
10-3
10
10-7
0
20
40
60
80
100
Timestep
5.2
RESULTS OF TRAINING
To demonstrate the feasibility of training SANNs, we trained a SANN to solve 10 x 10 linear systems; given matrix X R10010 and vector g TR10 find vector y R such that Xy g-

---

Published as a conference paper at ICLR 2025
The SANN uses 2-layer network N. We used Adam optimizer to minimize the loss Lital from equation (8).
Neural Network (see appendix B) as the underlying ISD
To benchmark SANNs against standard techniques, trained two-layer feed-forward neural net- work with comparable number of parameters on the same task. Table 1 summarizes the results. In this experiment, the SANN achieved marginally better accuracy with slightly fewer parameters.
# parameters 306, 140
Validation accuracy |Xy gll2
Feed forward network SANN
0.166
291, 720
0.101
Table 1: Results of training SANN and ford-forward neural network to solve linear systems. Given a 10 x 10 matrix and and vector g, the networks output y such that Xy y = g.
While we refrain from claiming significant numerical advantages for SANNs at this stage, the results underscore the feasibility of training these architectures.
The input matrices X were sampled from distribution of strictly diagonally dominant matrices, ensuring that a SANN theoretically exists that can solve for y to machine precision (as in the hand- crafted example from the previous subsection). However, further research is needed determine how to effectively optimize network parameters to achieve such precision.
6 DISCUSSION AND FUTURE WORK
We consider the SANN architecture presented in this paper be the most general form of new family of neural networks designed to compute semialgebraic functions. In practice, this architecture can be restricted in various ways to improve performance on specific tasks. This is analogous to convolutional neural networks (CNNs), which are a subset of standard feed-forward neural networks. While CNNs have far fewer parameters and cannot compute arbitrary piecewise-linen functions, they excel at tasks involving translational symmetry (e.g.. image classification). Similarly, in future work, we aim to identify and develop specialized variants of the SANN architecture that compute subsets of semialgebraic functions tailored to particular tasks.
One interesting modification is to change line 3 of Algorithm to have the ISD network A output an LU factorization of M rather than M itself. This change would increase the speed of the networks since solving two triangular systems LUz = is significantly faster than solving a general linear system Mz b. Furthermore, we could create continuous variant of SANNS by requiring the diagonal elements of T. and to be positive and bounded away from O. Such changes likely have many practical advantages; however, our expressivity proofs would no longer directly apply. Not every ISD matrix M has an LU decomposition in terms of ISD L and U, and it is not clear whether this would be sufficient apply our homotopy continuation arguments. Regardless, these modified SANNs compute a large class of semialgebraic functions not possible for most other architectures.
Efficient training of SANNs remains an open challenge. is currently feasible to train SANNs using established techniques such as backpropagation when explicit time-stepping is used to evaluate the network's ODE (as we have done here). The adjoint sensitivity method (Pontryagin et al., 1962) can be used when other ODE solvers are employed, as in Neural ODEs (Chen et al., 2019). However, the unique structure of the SANN architecture offers opportunities for novel training strategies. New approaches are needed to take full advantage of the expressive power of SANNs.
7 CONCLUSION
We have presented new representation theorems for semialgebraic functions along with novel neu- ral network architecture capable of representing all bounded semialgebraic functions. Our methods are inspired by homotopy continuation methods for root finding, and the architecture is simple to im- plement using existing machine learning tools. We believe our SANNs build new bridge between semialgebraic geometry (also called "real algebraic geometry") and machine learning, opening new avenues for both theoretical exploration and practical applications.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The authors thank the anonymous ICLR reviewers for helpful comments on an ealier version of this manuscript. M. V. de Hoop and S. D. Mis acknowledge the support of the Simons Foundation under the MATH X Program, the Department of Energy under grant DE-SC0020345, the Occidental Petroleum Corporation and the corporate members of the Geo-Mathematical Imaging Group at Rice University. M. Lassas was partially supported by a AdG project 101097199 198 of the European Re- search Council, Centre of Excellence of Research Council of Finland and the FAME flagship of the Research Council of Finland (grant 359186). Views and opinions expressed are those of the authors only and do not necessarily reflect those of the funding agencies or the EU, Neither the European Union nor the granting authority can be held responsible for them.
REFERENCES
Ralph Abraham and Joel Robbin. Transversal Mappings and Flows. W. A. Benjamin, Inc., 1967.
Shaojie Bai, Zico Kolter, and Vladlen Koltun. Deep Equilibrium Models. Advances in neural information processing systems, Oct 2019.
Randall Balestriero and Richard G. Baraniuk. Mad Max: Affine Spline Insights Into Deep Learning. Proceedings of the IEEE, 109(5):704-722 2021. doi: 10110//poo.2220.342110000
A. I. Beltzer. Variational and finite element methods. Springer-Vetie Berlin, 1990. ISBN 3-540- 51598-4. doi: 10. 10.10077978-34444-8994446 A symbolic computation approach.
Garrett Birkhoff. Lattice Theory. Number 25 in Colloquium Publications / American Mathematical Society. American Mathematical Society, Providence, RI, 2 edition, 1948.
Garrett Birkhoff and R.S. Pierce. Lattice-ordered Rings. Anais da Academia Brasileira de Ciencias., 28:41-69, 1956.
Jacek Bochnak and Gustave Efroymson. Real algebraic geometry and the 17th Hilbert problem. Mathematische Annalen, 23133221, Oct 1980. ISSN 0025-5831, 1432-1807. doi: 10.1007/ bf01428942.
Jacek Bochnak, Michel Coste, and edition, 1998. ISBN 3-540-64663-9.
Roy. Real Algebraic Geometry. Springer,
Helmut Bölcskei, Philipp Grohs, Gitta Kutyniok, and Philipp Petersen. Optimal Approximation with Sparsely Connected Deep Neural Networks, may 2018.
Liliana Borcea. Electrical impedance tomography. Inverse Problems, 18(6)R99-r136, 2002. ISSN 0266-5611. 1. doi: 10.1088/0266-5611 1/18/////////11111/111111//
Nicolas Boullé, Yuji Nakatsukasa, and Alex Townsend. Rational neural networks, Sep 2020.
Iacopo Cappellini, Laura Campiglia, Lucia Zamidei, and Guglielmo Consales, Electrical impedance tomography (eit) to optimize ventilatory management in critically ill patients: A report of two cases. Anesthesia Research. 1(1):3-7, 2024. ISSN 2813-5806. doi: 10.3390/anesthres 1010002.
Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural Ordinary Dif-
ferential Equations, Dec 2019.
Tianran Chen and Tien-Yien Li. Homotopy continuation method for solving systems of nonlinear and polynomial equations. Communications in Information and Systems, 15(2):119-307, 2015.
Grigorios Chrysos, Stylianos Moschoglou, Giorgos Bouritsas, Jiankang Deng, Yannis Panagakis, and Stefanos Zafeiriou. Deep Polynomial Neural Networks. IEEE Transactions on Pattern Anal- ysis and Machine Intelligence,
40344, 2021. doi: 10.1 00.10999mmm222211335889999
Edward Curtis and James Morrow. Inverse Problems for Electrical Nenworks. World Scientific Publishing Company, 2000.
11

---

Published as a conference paper at ICLR 2025
Maarten V de Hoop, Matti Lassas, and Christopher A Wong. Deep learning architectures for non- linear operator functions and nonlinear inverse problems. Mathematical Statistics and Learning, 4(1):1-86, 2022.
Stanislas Ducotterd, Alexis Goujon, Pakshal Bohra, Dimitris Perdios, Sebastian Neumayer, and Michael Unser. Improving lipschitz-constrainedd neural networks by learning activation functions. Journal of Machine Learning Research, 25(65):1-30, 2024.
Emilien Dupont, Arnaud Doucet, and Yee Whye Teh. Augmented Neural ODEs, Oct 2019.
Laurent EI Ghaoui, Fangda Gu, Bertrand Travacca, Armin Askari, and Alicia Tsai. Implicit Deep Learning. SIAM Journal on Mathematics of Data Science, 3(3):930-95) 99889, Jan 2021. ISSN 2577- 0187. doi: 10. 00.1137/20m1388111
Feng-Lei Fan, Jinjun Xiong, Mengzhou Li, and Ge Wang. On Interpretability of Artificial Neural Networks: Survey. IEEE Transactions on Radiation and Plasma Medical Sciences, 5(6):741- 760, Nov 2021. ISSN 2469-7311, 2469-7303. doi: 10. 10.110990 109/trpms 20....22.....0.. .33666288.
Stefan Forcey. Circular planar electrical networks, Split systems, and Phylogenetic networks. SIAM Journal on Applied Algebra and Geometry, 7(1):49-76, 76, 2023.
Takashi Furuya, Maarten V. de Hoop, and Gabriel Peyré. Transformers are Universal In-context Learners, Oct 2024.
A. W. Hager and D. G. Johnson. Some comments and examples on generation of (hyper- Jarchimedean l-groups and f-rings. Annales de la Faculté des sciences de Toulouse Mathématiques, 1:55 Aug 2010. ISSN 2258-7519. doi: 10.5802/afst.1276.
Melvin Henriksen and John Isbell. Lattice-ordered rings and function rings. Pacific Journal of Mathematics, 12(2):533-565, Jun 1962. ISSN 0030-8730, 0030-8730. doi: 10.2144/ppm..962. 12.533.
Tosio Kato. Perturbation theory for linear operators. Classics in Mathematics. Springer- Verlag, Berlin, 1995. ISBN 3-540-58661-x. Reprint of the 1980 edition.
Patrick Kidger. On Neural Differential Equations. PhD thesis, University of Oxford, 2021.
Zico Kolter, David Duvenaud, and Matt Johnson. Deep Implicit Layers Neural ODEs, Deep Equilibirum Models, and Beyond. http://implici-llyeesstttoooiii orooialll.,,.tttrooorrrrggg 2020.
Steven G. Krantz and Harold R. Parks. The Implicit Function Theorem. Birkhäuser Boston, Boston, doi: 10. 1007/997--1-441--00009
MA, 2003. ISBN 978-1 1-8-1-1611-005---
K. Kurdyka, P. Orro, and S. Simon. Semialgebraic Sard Theorem for Generalized Critical Val- ues. Journal of Differential Geometry, 56(1), Sep 2000. ISSN 0022-040x. doi: 10.4310/jdg/ 1090347525.
Matti Lassas, Mikko Salo, and Leo Tzou. Inverse problems and invisibility cloaking for FEM models and resistor networks. Math. Models Methods Appl. Sci., 25(2):309-33) 342, 2015. ISSN 0218-2025. doi: 10. 10.11422021820055550001
Jean Bernard Lasserre, An Introduction to Polynomial and Semi-Aleebriic Optimization, Cambridge University Press, 1 edition, Feb 2015. ISBN 910---11777-3300--77---------000 977-777-44472-----------77 978-1-107- 06057-9. doi: 10.1017/cbo9781 107447226.
John M. Lee. Introduction to Smooth Manifolds. Number 218 in Graduate Texts in Mathematics. Springer, New York: ; London, 2nd ed edition, 2013. ISBN 9777 5.
Stanislaw Lojasiewicz. Ensembles Semi-analytiques, 1964.
Zhou Lu, Hongming Pu, Feicheng Wang. Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. Advances in neural information processing systems, 30, 2017.
12

---

Published as a conference paper at ICLR 2025
James J. Madden. Henriksen and Isbell on f-rings. Topology and its Applications. 158(14):1768-
1773, Sep 2011. ISSN 01668641. doi:
Louis Mahé. On the Merce-Birkkooff conjecture three variables. Journal of Pure and Applied Algebra, 21 211(2):459-44 470, Nov 2007. ISSN 00224049. doi: 10.1016/j.jpaa.2000 watpa..0007011111 01..0011112...
Louis Mahé. On the Pierce-Birkhoff conjecture. Rocky Mountain Journal of Mathematics, 14(4), Dec 1984. ISSN 0035-7596. doi: 10. 10.1216/mi--1984-144444
Benny Malengier, Pavol Kišon, James Tocknell, Claas Abert, Florian Bruckner, and Marc-Antonis Bisotti. ODES: A high level interface to ODE and DAE solvers. The Journal of Open Source Software, 3(22);165, Feb 2018. doi: 10.21105//oss.00165.
Swann Marx, Edouard Pauwels, Tillmann Weisser, Didier Henrion, and Jean Bernard Lasserre. Semi-algebraic approximation using Sristoffel-Darboutt kernel. Constructive Approximation, pp. 1-39, 2021.
Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the Number of Linear Regions of Deep Neural Networks, Jun 2014.
Sung-Kwun Oh, Witold Pedryez, and Byoung-Jun Park. Polynomial neural networks architecture: Analysis and design. Computers & Electrical Engineering, 29(6)7003-725, Aug 2003. ISSN 00457906. doi: 10.1016660045-7000000005555
Philipp Petersen, Mones Raslan, and Felix Voigtlaender. Topological properties the set of func- tions generated by neural networks of fixed size. Found. Comput. Math., 21(2):375-444 4444, 2021. ISSN 1615-3375. doi: 10. 10007//00000-2220 000-0096000-000
Lev Semenovich Pontryagin, EF Mishchenko, VG Boltyanskii, and RV Gamkrelidze. The Mathe- matical Theory of Optimal Processes. John Wiley & Sons, 1962.
William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical recipes. Cambridge University Press, Cambridge, third edition, 2007. ISBN 978-0-521-88068-88 The art of scientific computing.
A. Seidenberg. A New Decision Method for Elementary Algebra. The Annals of Mathematics, 60 (2):365, Sep 1954. ISSN 0003486x. doi: 10.2307/1969640.
Endre Süli and D. F. Mayers. An Introduction to Numerical Analysis. Cambridge University Press, Cambridge: New York, 2003. ISBN 978-0-521-810265 978-0-521-00794488
Alfred Tarski, Decision Method for Elementary Algebra and Geometry. University of California Press, 1951.
Dinesh Valluri and Rory Campbell. On the Space of Coefficients of Feedforward Neural Net- work. In 2023 International Joint Conference on Neural Networks (IJCNN) pp. 1-7, Gold Coast, Australia, Jun 2023. Ieee. ISBN 188-1666548-888
doi: 10. 111199/cem55444.222...000
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention Is All You Need, Aug 2023.
Zichao Wang, Randall Balestriero, and Richard Baraniuk. A Max-affine Spline Perspective Of Recurrent Neural Networks. In International Conference Learning Representations, 2019.
A LATTICE-ORDERED RINGS OF PIECEWISE POLYNOMIALS
This appendix introduces the classical theory of "lattice-ordered" and "function" rings, culminating in statement of Henricksen's and Isbell's 's theorem for generating f-rings from subrings. This is the key lemma in our proof that the space of functions computable by MRNNs is closed under ring and lattice operations--vceee addition, Hadamard product, min and max.
We use the following standard conventions: Group operations are denoted "+", and ring multipli- cation operations are denoted "*". When there is ambiguity, the ring multiplication operation
13

---

Published as a conference paper at ICLR 2025
f * may be written fg. If R is given ring, the polynomial ring in variables with coefficients in R is denoted R
Direct products are denoted "x", , and we reserve @ for Kronecker products of matrices. Lattice operations are denoted A for "inf" ("meet") and V for "sup" ("join"). We use the shorthand /+ = / v 0, f = (-f) V O, and |s| == f (-f).. In this paper,
VV = max(f.g), and f = min(f.g).
although in general there are other choices for the lattice operations. Observe also that
fVg= ReLU(g- f), and fAg= ReLU(f - g).
Furthermore, f S means f A = f and f Vg = 9. while the obvious dual statement holds for g.
In the terminology of neural networks, f+ is precisely ReLU(f) when the lattice is built over IR and the meet/join operations are component-wer min/max.
Definition 14 (e-rings), An l-ring (short for "lattice-orders ring") is tuple (R, + V) that is ring with operations +, *, a lattice with operations A, V, and the following compatibility conditions satisfied:
f h+ S s sh+g for all f.g. R,
(16)
f 0 and g 2 = fg 0.
(17)
We will often refer to an E-ring (R, +, ,, A, V) simply by its underlying set R.
An f-ring homomorphism preserves both ring an lattice operations.
Remark. The original masters did not require f-rings to have commutative addition (i.e. be an Abelian groups) or have multiplicative identities. These generalizations are not important to us here, and what call "é-ring" is often called "É-ring with unity" in the literature. All our f-rings abelian groups and have multiplicative identity.
Every f-ring is a distributive lattice' (Birkhoff, 1948); that is,
( = (f and f =
hold for all f.g. E R. In particular, every lattice polynomial can be written in the form
A VVa Jj VEl JEJ,
with J, C N and f, E R.
Garrett Birkhoff demonstrated é-rings can have surprising pathologies; for example, he constructed an é-ring whose multiplicative identity was both negative and square (Birkhoff & Pierce, 1956). The following definition introduces an additional compatibility condition that prevents the most troublesome pathologies.
Definition 15.
f-ing (short for "function ring") is l-ring where
If f. g, h 2 0 and g A h O, then fg h 0 and gf h
(18)
Condition (18) can be equivalently stated (Madden, 2011)
rtg* PTAS=S = and g =0 for all f,g E R.
Lemma 16. IfR is an E-ring (resp. f-ring) and D is any set, then functions F= [ R) form an E-ring (resp. [-ring) using the operations defined to turn every evaluation map &z (J) := (xx), D. into an E-ring homomorphism (stated simply, these are the "component-wise" operations).
Proof. For brevity, we forego the verification of the ring and lattice axioms and focus on the com- patibility conditions. The first will be treated in detail for illustration, the other two will be more succinet. Let f.g, h
Only compatihility condition (16) required, in fact every so-called g-group distributive lattice.
14

---

Published as a conference paper at ICLR 2025
Condition (16): Suppose f S 9, which means f(x) S g(z) for all D: f(z) (f) ( = .x( (x(1) A
Since is E-ring, a+1(x)== v a+g(2) for all a E Rand E D. In particular, h(x))1(2) h(x)) + g(x), and thus
Φz + f) h(x) f(z) (M(x) + f())) ^ (h(x) x(x)) =
0₂ ( +
@2 g) d2 ((h - f) (h + +9)
Since A in F is defined precisely to turn every o₂ into homomorphism, we conclude h + f= (h + f) A (h g).
Condition (17): Suppose 1,9 2 O. meaning (())g(()) for all D. Then [(x))(<)) 2 0 since R is an (-ring.
For the last condition, we now suppose R is an an f-ring.
Condition (18): Suppose f.g.h 2 and f f(x) A h(x) 0 for all x E D. Then
meaning g()). 2 0 and A ( = f(x)((()) Ah(x) =
since R is an f-ring, and we conclude fg ^ = O. Likewise gf A h = 0.
Example 17. Continuous real-valued functions with component-wise +/>/min/max operations form an f-ring.
Lemma 18. The direct product of E-rings (resp. f-rings) is an E-ring (resp. f-ring).
Proof. The direct product of two E-rings or f-rings clearly both a ring and lattice, and the relevant compatibility conditions hold in the product since they hold in each component.
In particular, vector-valued functions D R. form an f-ring when each component forms an f-ring.
Lemma 19. If R is an E-ring (resp. f-ring) and R1 S R both a subring and sublattice, then Rı is also an E-ring (resp. f-ring).
Proof. We need only verify the compatibility conditions (16), (17) and (18). But since these condi- tions hold in R, they clearly hold in Ri as well.
The requirement that RS R form sublattice in addition to subring (rather than just a subring) is a small oversight in (Birkhofff & Pierce, 1956). For example, polynomials form subring of the f-ring of continuous real functions, but they are not lattice (x and - are both polynomials, but V - = |x| is not), so polynomials do not themselves form an f-ring. Indeed, this fact will be relevant below to us below.
Definition 20 (Totally ordered ring). An é-ring R is totally ordered both f A g and fVV g are in {f.g gf for all f.g E R.
In other words, the lattice totally ordered ring induces a total order relation.
Lemma 21. Every totally ordered ring R is an f-ring-
Proof. Given f.g. h e R such that f.g. 2 and g A h 0, we need to show fg 0 and gf A h = O. Since R is totally ordered, ^ h = 0 implies either = 0 or h = 0.
Case g = We have fg = gf = and fg A h = 0 A = since h 2 Identical logic
shows gf A h 0.
15

---

Published as a conference paper at ICLR 2025
Case h 0: From the E-ring compatibility condition (17), fg 0 and of 2 0. Thus fg A h = fg fg 0, likewise of h of =
We can now state the key theorem of this section, which will allow us to generate f-rings of neural networks by bootstrapping from subring.
Theorem 22 (Henricksen and Isbell). If R is an s-ring and Ra C R is subring (not necessarily sublattice), then the lattice generated by R1 is subring of R.
This theorem first appeared in Henriksen & Isbell (1962). The proof surprisingly non-trivial, and while the key insights were provided by Henricksen and Isbell, they left the proof an exercise to the reader. The first full proof appears to have been recorded in Hager & Johnson (2010).
A.1 INF-SUP DEFINABLE PIECEWISE POLYNOMIALS AND THE SARRCE-BIRKKOFF CONJECTURE
Definition 23 (Piecewise polynomial). Let k. n, J N, and D C R", Then f + R is piecewise polynomial, or f PDD( if there exists collection of semialgebraic sets {S such that
D c U 1= Si, and a collection of polynomials {ps C R[X,,..... Xa) such that fls, = ps for all J.
vector-valued function f D + R is piecewise polynomial, or E PWP(D, Rt), if every component function is piecewise polynomial.
piecewise polynomial is continuous if and only there exists a collection closed semialgebraic sets {S,) ) satisfying Definition 23.
Lemma 24. Let N, and D R". Then PW P(D) equipped with component-wise operations is an f-iing.
Proof. We need only show PW P(D) is both a subring and sublattice of the f-ring of functions D) + TR, then the conclusion follows from Lemma 16. But it is elementary verify the pointwise sum, product, min and max of two piecewise polynomials is also a pointwise polynomial.
Corollary 25. Let ki n E N, and C R". Then PW P(D, R*) is an f-ring.
Proof. PW PWD(DR RR) is direct product of PW W(D,(D, IR,, the conclusion follows from Lemma 18.
We apply Theorem 22 to the subring of PWP(P 1 consisting of the polynomials D R
We obtain the following important theorem: Theorem 26. IRD( is an f-ring for any N.
Both PW ((R") and ISD(R") are f-rings, and clearly ISD(R") C PWP(R"). Whether opposite inclusion holds is the famous Pierce-Birkhoff conjecture. Conjecture 27 Seerce-Birkkoff)) ISD(R*) PW P(R*).
the Pierce-Birkhoff conjecture holds, then every piecewise polynomial can be written
g = min max Sij vE/ JEJ.
for polynomials fy and finite indexing sets I, J4.
The case n = was proved by Jacek Bochnak and Gustave Efroymson (Bochnak et al., 1998), and then again by Louis Mahé (Mahé, 1984). Mahé has also shown that the conjecture holds when n = up to arbitrarily small neighborhoods of finitely many points. See Madden (2011) for further discussion of the Borree-irrkooff conjecture and related problems.
Later, we will show that the neural network architecture introduced in the next section can exactly compute any continuous piecewise polynomial if and only if the Pierce- Birkhoff conjecture holds.
16

---

Published as a conference paper at ICLR 2025
B MATRIX-RECURRENT NEURAL NETWORKS
Semialgebraic Neural Networks (SANNs) are built on top of a related architecture called Matrix- Recurrent Neural Networks (MRNNs), type of polynomial network with ReLU activations. This chapter introduces MRNNs and exactly characterize their range as inf-sup definable (ISD) piecewise polynomials. Our analysis of the expressivity of MRNNs inspired by Balestriero & Baraniuk (2021).
B. ARCHITECTURE
standard feed-forward neural network function R" - IR defined as an alternating composition of affine transformations and nonlinear activation functions
ho he (be + Aghe-1)
(19)
for l L-
(20)
f(x) by + Arh1-1
(21)
Perhaps the most popular activation functions used in practice are variations of the rectified linear unit (ReLJU (a:) = max(0, ar). This activation results in networks whose ranges are conceptually simple; they are multivariate linear splines. Although such networks can uniformly approximate any continuous function, they are extremely limited in the types of functions that can be represented exactly. For example, the product of two linear splines is in general not a linear spline itself, so computing such function by neural network will require number of weights proportional to the desired accuracy of the approximation.
In this work, we study type of Operator Recurrent Neural Network (ORNN) (de Hoop al., 2022)
where the input to the network is a matrix X E Raxm and the output a vector f(X) E TR kmr. To emphasize that our results hold specifically for matrix inputs rather than general operators, we call this subset of ORNN's the Matrix Recurrent Neural Networks (MRNNs). The architecture of an L-layer MRNN defined
ho 0
(22)
he = br,o + Ar.ohe-1 + Br. 8 X (bc.1 Ag,1he-1 Br,1 (1 @ X)he-1)
for l = L...,,L
(23)
S(X) hr where (I & X) denotes Kronecker product with an identity matrix I whose size may vary in each
(24)
layer. Notice in particular that the input matrix X is inserted multiplicatively into each layer. Our definition of MRNN matches the original definition of a width-expanded ORNN with matrix input presented in de Hoop et al. (2022). As noted in that paper, the restriction on hy does not affect the range of since h1 will invariably equal b1.0. which is learned.
We formally define the space of functions representable by an MRNN.
Definition 28 (MRNN), Let k, L E N, and be a subset of RR Then f D + R in M MRNN, (D, k if f can be computed via equations (22-24).
When the number of layers a network is not specified, we define
(D. U (D, L=
In contrast to standard ReLU networks, we will show that MRNNs form ring of piecewise poly- nomial functions. The kernels of these functions-ttat is, the set of points X such that ((X) vanishes- form semialgebraic sets in Rmxn
B.2 RANGE
Numerous authors have observed that linear ReLU networks compute multivariate linear splines, where each linear region polyhedron defined by the combination of active neurons- is,
17

---

Published as a conference paper at ICLR 2025
where by + Aghe-1 0 (see, for example, Montúfar al. (2014) and Wang al. (2019)). Like- wise, de Hoop et al. (2022) showed that MRNNs (or rather ORNNS in general) compute piecewise polynomials, where the semialgebraic decomposition of the domain is similarly defined by the com- bination of active neurons
1 + A + Bt,1 (1 @ X 2 0,
each point. Thus M M IR isomorphic to a subset of PW P(R )R.. The con- verse question, whether every piecewise polynomial is computable by an MRNN, was not addressed. In this subsection, we refine their observation to show that MRNNs compute precisely the ISD func- tions.
Let vec : R - Ram be the column- oojomn-major matrix vectorization operator. It is clearly bijective, and its inverse is the matrixization operator denoted vec-1, We first show every ISD function can be computed by and MRNN.
Lemma 29, Let m.n, N. For every f =SD(("""), there exists N (P"N)("XX))) such that f = N vec
Proof. By definition of ISD(R""), is a lattice polynomial of some {pi..... ps} C R[X1...... Xmp). An easy construction shows there exists networks N1.....NN computing the polynomials N₁ = Pj vec-1. Another easy construction shows that M (RR is closed
under the lattice operations, so the lattice polynomial / can be computed by network. In particular,
N = (Ni....,NN is the desired network.
We now generalize the previous lemma to vector-valued functions.
Lemma 30. Let m, n, k E N. For every f E ISD(R ,R), there exists N E MRNN RR*) such that o
x... fo for some fi...., fr E (SD(R (m.).. By the previous lemma, there exist N NI....,,G E MRNN (R such that Ng o vec for j 1,...,k k. Since M R.N. N N mR R$) is the k-times direct product of M MRNN MR))) M x ... x M& is the desired network.
Proof. ISD(R R$) ) is the k-times direct product of [SD(R
The next two lemmas prove the dual inclusion -vvery MRNN indeed ISD.
Lemma 31. Let m,n N. For every N E MRRN (RRMx)) there exists E ISD(R"") such that N f
vec. vec.
Proof. Fix a network computing N, and use induction on the number of layers L. The base case = 0 trivial since layer network is constant. Assume the condition holds for layers, and consider the final layer in the network computing (XX):
hy P'.0 AL + BI, @ X)hL-1t
(25)
a (br., + AL, + Br, (1 @ X)hL-1).
Notice h is vector-valued function of X and can be decomposed into its component functions
h 91 X gN
for some N E N corresponding to the width of this layer. For every j = 1,...,, N. gj (X) is
computed by an 1 network, so the inductive hypothesis states there exists Sj I ISD ( such that 9 fj vec. We now rewrite each term of equation (25) using these fy. Let i (0,1) 1}.
The constant terms by, E IR are clearly isomorphic to constant functions in (RD()
The linear terms h linear combinations of f1...., fN E IR"". Since ISD is an f-ring (Theorem 26), there exists fA. E ISD(R.") such that fA. = (Ar,)hr-1)
18

---

Published as a conference paper at ICLR 2025
For the quadratic terms, note (I @ X) E R The k'th component of (I X)h1-1 equals
122
(1 vec(X)
(26)
where % denotes modular division, [-] is the floor operation, and ((a entry 6 of matrix X. In particular, each term in the sum on the right-hand-side is the product of a monomial and an ISD function, so
fBA.k
ISD(R mT for & L...., m.. The full quadratic terms (1 are thus isomorphic to linear combinations of ISD functions f so there exists fB,i (TS(RRmM)) such that fB,: = (B (T & 1)) o vec.
We can thus rewrite (25) in the equivalent form
hr. = [br.o + SA,0 + Jn. + o(br,1 SA.1 + [n,1)] o vec.
(27)
The term in square brackets constructed from elements of the f-ring ISD(R using only addition and the lattice operation a = max +) so it is itself in ISD(R mn) and the lemma is proved.
Lemma 32. Let m. n, E N. For every N MRNN(RRXXN) R there exists f (RR, RR such that N = vec.
vec.
Proof. We pass through the direct products in an identical manner to the proof of Lemma 30.
Combining Lemmas Lemma 30 and Lemma 32 lets us conclude M MRNN RR)) is isomorphic to ISD IR;;; that is, there exists bijective ringhhmmomorphimm between them. Informally, the rings are identical up to relabeling of the elements.
Theorem 33. For all m, k N. the rings MRNN N (Ru Rt) and ISD(RaM RR) are home- omorphic, that is,
MRNN(R"XX)) TR ISD R*).
Theorems 33 and 22 allow us to conclude that (RNN(R"XM) R²) forms unital, associative algebra over I; that is, every scalar multiple, sum, and Hadamard product a MRNNs com- putable by MRNN. Associativity and existence of multiplicative identity, well as the ability to compute scalar multiples and sums are obvious and hold for linear ReLU networks as well. What distinguishes MRNNs from linear ReLU networks is the ability compute Hadamard products. We require this property to build SANNs capable of computing any semialgebraic function.
While the proofs above are explicitly constructive, they be made constructive using the identities in Henriksen & Isbell (1962) or Hager & Johnson (2010). Unfortunately. representing the Hadamard product of two MRNNs as an MRNN requires exponentially many parameters, which limits the practical usefulness of direct application of these constructions in code.
In their original paper introducing the architecture, de Hoop et al. (2022) note that the range of an MRNN is multivariate piecewise polynomial; we have refined this result to show that MRNNs are ISD. We now ask the natural question, is every piecewise polynomial representable by an MRNN? As noted previously, this question is the famous Pierce-Birkhoff conjecture, a long-standing open problem in real algebraic geometry. MRNNs can represent every piecewise polynomials and only if the Pierce-Bae Birkhoff conjecture is true.
C SEMIALGEBRAIC FUNCTIONS AS KERNELS OF ISD FUNCTIONS
This appendix contains proofs of Proposition 7 and Corollary 8 from the main text.
Proposition 7. S C Rm is a closed semialgebraic set if and only if there exists e TSD Rzo) such that ker(s) = S.
19

---

Published as a conference paper at ICLR 2025
Figure 4: Encoding the graph of semialgebraic function (red line) F(x) |ax| as the kernel of continuously differentiable piecewise polynomial (purple and yellow surface)
G y) ((x + g) v))² max(00- 2
Proof. Clearly the kernel of a piecewise polynomial is closed semialgebraic set, focus the converse.
First, suppose S is closed basic semialgebraic set described the system pi (1 -. pJ₁ (1) 0 and (2)),...; 0.
The desired ISD piecewise polynomial is
f(z) = Σ pl (x)
max(0, -Q(()))
Each term (x) (resp. max (x))) is zero precisely when the corresponding condition Pı(x) = 0 (resp. (x) 2 0) is satisfied. Also, the function g -> max(0, 9) in C* and has the continuous derivative g + 2 max q). Moreover, each term is non-negative, so the is non-negative and zero and only if every term is zero, meaning every condition is satisfied simulta- neously. Finally, is ISD since it is constructed using the ISD lattice-ring operations on polynomials (see Appendix A), and it is C since each term in the sum is C
Now let S be an arbitrary closed semialgebraic set; i.e., the union of basic semialgebraic sets. We may take the basic sets to be closed, since
cl U 81
U cls(s) 1=1
for finitely many sets .1.....6 Sn Since, ker (fg) = kcr (ff ker(g) for any real-valued functions and g. the desired ISD function can be constructed as the product of piecewise polynomials corre- sponding to each closed basic semialgebraic set.
Corollary 8. F:Rm - R" is semialgebraic function with closed graph if and only if there exists a G E ISD' (R x IR" "RR,,E Rg0) such that ker(G) = gr(F), where gr(F) = ((x)) C Rm xR" the graph of F.
Proof. If F is semialgebraic and has a closed graph, then Proposition 7 guarantees there exists a C ISD piecewise polynomial g T. I + E>0 such that gr( ker ker(g). An -vauud function G can be obtained by defining each component function to be
Now suppose for given F", there exists an ISD G such that ker(G) gr (F). Then gr grFF) is closed since kernlss of continuous functions are closed, and F is semialgebraic function since ker(G) is clearly semialgebraic set.
20

---

Published as a conference paper at ICLR 2025
Remark. The hypothesis in Corollary 8 that F has closed graph covers all continuous semialge- braic functions, as well as some unbounded discontinuous functions like
00 11/2,
y -
(28)
x 0.
For example of semialgebraic function whose graph is not closed, consider the characteristic function of (0, +o0);
x 500 0 x x> 0. 1,
0,
(29)
The graph does not contain the limit point (0, 1).
D HOMOTOPY CONTINUATION METHODS
This appendix contains additional background material on homotopy continuation methods for root finding. Subsection states semialgebraic variants of two important theorems from geometry that are the foundation for our proofs. Subsection D.2 gives sufficient conditions for the existence of homotopy H whose kernel can traced from time to time 1 in order evaluate the roots of a given function. Finally. D.3 builds the system of ODEs that is solved in order to execute the homotopy continuation method, and we prove this ODE system can be represented by a SANN.
D.1 SEMIALGEBRAIC SARD'S AND TRANSVERSALITY THEOREMS
We present semialgebraic variations two classic theorems from differential topology.
Theorem 34 (Semialgebraic Sard's theorem). The set of critical values of continuously differen- tiable semialgebraic function has measure zero.
In the "textbook" Sard's s theorem, the smoothness requirements on the function depend on the dimen- sion of the range (Abraham & Robbin, 1967). In contrast, for semialgebraic functions continuous differentiability is sufficient for the theorem to hold. A proof can be found in Kurdyka et al. (2000).
Next, we use the previous theorem to adapt the Thom transversality theorem to C semialgebraic functions.
Theorem 35 (Semialgebraic transversality theorem). FfF: : x A - Y is continuously differen- tiable semialgebraic function functioon and 0 regular value F, then 0 is regular value of F(:, a) for almost every E A.
proof can be found in (Abraham Robbin, 1967), substituting the semialgebraic Sard's theorem for Smale's theorem as required.
D.2 HOMOTOPY EXISTENCE
We now state a standard result in the theory of homotopy continuation for solving nonlinear equa- tions. Theorem 37 is adapted from Krantz & Parks (2003) with small modifications using the theo- rems from Appendix D. to specialize to TSD1 and avoid any C assumptions. It provides suffi- cient conditions under which t
guaranteed to be able to evaluate a homotopy from t = 0 until
Definition 36 (Regular value). Let C R.m be open. Given f: U - R., y E R.. regular value of f if the Jacobian matrix Df(z) has rank for all x E (y).
In particular, 0 is a regular value of f R - Rn if and only if the Jacobian matrix is nonsingular for every ker(f).
Theorem 37. Let Un be a bounded open subset of R", and H E TS" x R. RR Further suppose
A.I H(: has unique solution yo in Un. That is, ker ((.,0) -[o)-
A.2 The connected component ker H containing (yo, 0) does not intersect 0UH [0. 1).
21

---

Published as a conference paper at ICLR 2025
A.3 0 is regular value of H.
A.4 0₂ H yo. 0) nonsingular. (yo.
Then there exists E [S, 11, y [8, such that ((0) 0, ((1) 1, and (((s),(()) E ker(H).oo for all E 10.
D.3 CURVE TRACING
Let =()) = (()), and E ISD* x IR, R") satisfy the hypotheses of Theorem 37. Then (y, E ker H can be computed by solving the ODE -nitial-value problem defined by the "arc-length parameterization" (Chen & Li, 2015):
DH(2) 2
(30)
sgn det DH)2)
aO
(31)
|| = 3
(32)
x0) (yo, 0).
(33)
where do is the sign of the determinant of that matrix at (0) and 5 > 0 is a constant chosen so that t(1) =
With proper choice of N and Cuax. the curve-tracing ODE system (30)(33) can be written in the form of the ODE system (6)-(7) that define SANNs. At time write
DH (yo. 0)
M
b
(34)
That M is the n X n submatrix of DH (yo. 0) that does contain the rightmost columns b. By assumption A.4, M invertible. Thus a vector satisfying (33)((3) can obtained by solving
M
0 a
b
Má =
=: b
(35)
0
where a is constant chosen to satisfy (31) and (32). The M and defined above appear in the ODE (6)-(7). Thus we have shown for H satisfying the hypotheses of Theorem 37, No = 0, and large enough Cmax, there an N E DSenet (m, n, k) such that the integral curve traced in solving the ODE (6)-(7 is "correct" at time 0; i.e. is tangent to the integral curve defined by & solving the IVP (33)
For time O, submatrix. However, by assumption A.3, DH always has rank n, so every belongs to some interval where we can choose column of DH to be b, and the remaining columns to be M. The computations in each of these intervals can glued together (6)-(7) used to compute the entire integral curve. The details can be found in the proof of Theorem 12 in Appendix E.
longer guaranteed that the first columns of DH form invertible
way consistent with the ODE
E SANN EXPRESSIVITY PROOFS
In this appendix, we prove via construction that SANNs are able to represent both continuous and discontinuous bounded semialgebraic functions F.
E. NOTATION
The theorems in this section require us to show the existence of ISD N generating certain initial value problems for (6)-(7) In Algorithm
implicitly depends on the inputs N, Cmax, and ær and ODESolve ve always runs from time s = 0 to = 1. For this section, we make the dependence on all variables explicit by using the signature
ODESol ve (N, Cmaxx xr, (yo, lo, Sn), Stiua)
22

---

Published as a conference paper at ICLR 2025
where N (m, n, 1) is the trainable ISD network, Cmax R20 bounds the output of the SANN, I E Rn is the imput to the SANN, (yo, to. su) E IR" x R x R is the initial condition, and Stinal E R is the final time. We assume that ODESolve exactly solves the ODE system defined by in Algorithm I from time 8 = 80 to time & = 8fnal- To avoid repetition, .N, Cmax. 3, yo, lo. $p, and Stinal will always be in their respective spaces above. Furthermore, for N₂ with any subscript a, use Ma and bæ to be the associated projections as in line 3 of Algorithm 1.
We 11 to denote the projection operator selecting lour from (Nouts lout).
E.2 GLUEING
We require two different ways to combine ISD networks M₁ and N2. For "s-glueing," we build Nç that first imitates N₁ on interval [80, $1/2], then behaves N₁. when [51/2, [tial]- We require an additional lemma that modifies N and N2 to guarantee ÿ), f can be forced to be 0 in an open set around $1/2 without affecting the output of ODESolve We accomplish this with an ISD change of variables.
For "t-glueing," we build N/3 to interpolate between Mi and N2 in disjoint closed intervals [to, f1 and [t2, ta]. We use t-glueing when we can guarantee the integral curve traced by ODESolve will never enter the region (f1, so the value of Ng may be arbitrary here. We are free to use this interval to interpolate between N1 and N2-
Our first lemma allows particular change of variables for s-glueing.
N2, C2 such that for all x, Given Ni, eb yo. to and 8o 81 82 Sfnaa there exists
Lemma 38
ODESolve(Ni, (yo, to, so), 8fmmat = www.olveeNa 02, (yo, to s0), 8fima)
(36)
and
bz(x, when s & [$1,
(37)
Proof. Let ; R + IR be defined
Su
$ < $1
(s)) = u(s)
s E [$1, s2]
(38)
Stinal
82
where u is the Hermite interpolant (Süli & Mayers, 2003) such that
u(s1) =
ú(s1) 0 ú(s2) 0.
(39)
u(82) 8 final
(40)
is continuously differentiable and i E ISD(R). 0(s) 0 for all & [2]. Since + (())b(z, =(s)) is the product of ISD functions, itself ISD. Likewise the composition of ISD function with polynomial is ISD. Thus we can define
M2(2, t, M1 (z, v(((s)), t(v(s)() (((())) u(s) (2 v, o()),, (z, t(oss))
(41)
(42)
Simple calculus verifies conclusion (36). and conclusion (37) holds since ú(s) = 0 outside [s1, s2).
Lemma 39 (s-glueing). Given Ni, Nr. C₁ lo. so < 81 < Sfmaii let (x)a(x), ton (x)) CDESolve(NG, C1, (Vo, to. su), 81).
(43)
There exists Na. C3 such that for all x,
ODESolve(Ng, Cg. x, (yo, to. so), $jmat) = ODESolve(N2. 02, v, (2), tz 81), Spmna).
(44)
23

---

Published as a conference paper at ICLR 2025
Proof. Choose > 0 such that So S1 - 81 + Stinal, and apply Lemma 38 to .M and W2 so that both by and by are identically 0 in the region ($1 $1 c). No matter the value of M1 and M2, both ' and i are identically 0 here. Let A(s) = (s - (81 (2)) Define
(x. s)
8 85 81 -
M3(3, s,
(1- M( (,, (5)M2(22,,tt M2(x,,,t,s)
E (1 8, +c)
(45)
s 2 81 +e
and
(1, 8 $ 81
b, U. (,
(46)
(b,
81
M3 is clearly continuous, and by is continuous since b and by are both when s 81- The con- structed Ng is ISD and satisfies conclusion (44).
Remark. Strictly speaking, we have not written M3 and by in ISD form in the proof above, but this not difficult remedy. For example, we could use
X(s) == min(maxx(s -(10--111-11111 (2)=e))(26),,)), 1),
(47)
then define
Ma (1 (s))M + A(5)
(48)
4g = (1 ((5))b, + A(5)b2
(49)
over the entire domain.
Lemma 40 (l-glueing). Given Ni, N2. et, c2. yı, y/2 (1 12,80. Symaa let
Ts (1l++1DESSlvveellt ej. H. (yi, ty so). s) E [so, Spmai) x E IR")
(50)
Suppose Ti i T2 = 0. Then there exists N3. c3 such that ODESolve(Ng, c3, (yj, f so), Spmal) = ODESolvee Cj, (1j, t0, Sfmat)
(51)
for j = 1,2 and x E R...
Proof. Sets T; contain the integral curves for the output of ODESolve, so they are connected and closed. Since they disjoint, we can assume WLOG max Tı < min Tz. Then there exists Emid e E R such that
max Ti < bmid
miid min Tz.
(52)
The integral curves traced by ODESolve do not enter the t-region (fmid Eia + c), so are free to define N/ to interpolate between Mi and N2 there. Let A(t) = (1 (Imid <) e)) Define
M1
t Emid
M3-
X(t) + (1- A2
t (tmid
C, famid + c)
(53)
M2
t 2 tmid E
bi
I tmid
by
X(t)b + A(t))62
E (fmid
C, tmid + c)
(54)
be
2 fiid C
C3 = max max(cr.02) 02).
(55)
E.3 PROOF OF THEOREM 11
Theorem 11. Let F: Rm - Up be a given continuous semialgebraic function. For every x R there exists Hz with the form (10) such that for almost every a E UF, the following hold:
1. There exists E ISD 1]. R"), E ISD( 1], R). such that t(0) = O, t(1) = 1, and (u(s), (()) E ker ker(Hz,a a for all E [0, 1].
24

---

Published as a conference paper at ICLR 2025
2. The kernel of (=) is the singleton {F(x))
Proof. To specify Hz,a, we need to choose g and G. Let be constructed according to Lemma 10.
Let G be constructed such that ker G gr(F) using Corollary 8.
For conclusion 1, we will use Theorem 37. We first specify a bounded, open Un C R" containing UF with an additional property that is relevant for A.2. Let C denote the connected component of ker( (a.,) containing (vo, 0) (i.e. the curve to be traced), and assume for the moment A.3 (which does not depend on choice of Uz) 1)) has been verified. Then for almost every a, there exists t0 E (0, 1) such that C n (R" [0, tul) C n (Up x tol);;; in other words, the curve remains in UF until at least time ty- Now, using Lemma 10, we conclude there exists bounded open UH containing Up such that (t, y) > 0 for all (y, E U3 x [to, 1].
We now consider each hypothesis of Theorem 37 in turn:
A.1 The unique solution to Hz, 0) = y is yo a.
A.2 From the construction UH above, the curve does not intersect ØUn during the interval [0, fo], and the entire kernel of Hz is disjoint from ØUH for t to.
A.3 We will show that 0 is a regular value of Hz for almost every a using the Semialgebraic Transversality Theorem (see Theorem 35 in appendix D.I). Consider H3 IR" x R x R2"
IR" obtained from Hz,a by treating a as a variable: Hz, L, a) = H Hz,a t). Then
Hg = -1 (1-t)In.
which is invertible for i * 1, is regular value of Å. Apply the Theorem 35 to H, to conclude 0 is regular value of Hz,a for almost every a.
A.4 (Vo, 0) is in the region Ur x Ur, so 01 H (yo, 0) In. which is nonsingular.
For conclusion 2, we have shown in A.2 that y1) E UF where vanishes, so Hz,a (1(1,,) G(x, (11).. The conclusion follows since ker G gr(F).
E.4 PROOF OF THEOREM 12
Theorem 12. Let F : R + UF be a given continuous semialgebraic funnicttobruiccannioonn function. Then there exists A ISDnet(m, 1) and Cmax O such that SANN (N, Cmax) F.
Proof. In Section D.3, we showed how to construct No E T Dmet 1) to compute the required integral curve using Algorithm time s 0. No can be chosen this manner to compute the integral curve until some time 81 > O, when M (81). ), the first n columns of DH (y(s)) ((s)), no longer form an invertible submatrix. However, by assumption A.3, invertible submatrix and left-over column, say M, and b,. By the continuity of DH, M, invertible over some interval E (21/2.82) with 0 < $1/2
choose different
$2. Using the same approach, we can construct M₁ E ISDnet(m, n. 1) to compute the integral curve over E ($1/2, 82). We can now s-glue No and N₁ (Lemma 39) to construct N computing the integral curve across E s2).
All that remains it to prove this procedure can be repeated until time the clamping in line 7 of Algorithm I, z remains in [-Cmax Cmax] |n-1 for time E [0, 1]. Since N E ISDnet(m, n, 1) piecewise polynomial, [-Cmax: Cmax], which means there exists > 0 such that for each step of the s-glueing procedure above, we can choose 87+1 such that s, + 87+1, and the conclusion follows.
is reached. Due to
Lipschitz on the compact domain {a} x
E.5 DISCONTINUOUS FUNCTIONS
We are now ready to directly tackle discontinuous semialgebraic functions. Our strategy is to split the computation into two distinct phases.
25

---

Published as a conference paper at ICLR 2025
1. First, utilize the fact that can be discontinuous across a boundary where M is singular to separate the domain R" into the connected components of the graph of F. Every point in the j j'th connected component is mapped to (Noms toun) (0.
2. Then, using the homotopy continuation arguments from Section 4. construct continu- ous ISD phase vector fields that map from (0,j) to (F(r), tout) which was desired.
Furthermore, we carefully construct each piece of the computation to lie in disjoint (t, s)-pace, so they can be glued together way consistent with single continuous ISD network N. This W computes F' while solving the ODE (6)-(7). Ensuring that the required N is indeed an ISD network (rather than an arbitrary continuous one) one of the primary challenges these constructions.
E.6 CHARACTERISTIC FUNCTIONS
Given S R" a function Xs : I' > is the characteristic of a set S if xs(x) = 1 for S, and (x) = 0 otherwise. We now show that SANNs represent characteristic functions on semialgebraic sets.
Lemma 41 (Scalar multiplication). Given N,, Cmax yo. to. so. Symal and a E R. there exists Ni e TS DSenet(m, n. 1) such that for all x,
ODESo veevolvee,,,,,,,, 2r, (yo, to, so), Sfmaa) aODESolve Cmax, 3. (yo, Lo, 80), 8fima)
(56)
where 0j CCmaxx
Proof. When O, we simply use M1 = M, bi 0. Otherwise, we dilate and scale the phase vector field by a, which we accomplish by setting
M1 y, t,8) = M(x, a y, (t,s) 6 b1 = ab(æ, a y, a,,,)) t,
(57)
(58)
Lemma 42 (Changing 8 bounds Stimal). Given Ni, C1, you to 8n, %y. Symat knaa there exists N and 02 such that for all x,
GDESo 1 Vee 02, (yo, lo 8))s s/mat) = ODEsolve(Ni.oo cI, (yo, lo, 80), 88mna))
(59)
Proof. Let A(s) = (mmal (5/( - s6) and a (S - su)/ (s/maal - s/). Dilate, scale, and translate the phase vector field:
Mr(r, y, t, = M1 y, t, s0 ((s)nalinal - -00)
(60)
b2(x,,,,,8) odly (ar, W. 1, 80 + (()) 80))-
(61)
Set C2 OC1-
Lemma 43 (Shifting initial conditions). Given N1. e1, you wh. to ty su, and Spmat, there exists N such that for all x,
ODESolve(N2.e1, x, (16. ty s0); Spmaa) = (V6r (6) + ODEsolve(N x, (yo, to 80), 8 8pmal)
(62)
Proof. Let 8y = 3/6 Yo and 81 = 10 - -u-
M2 y s) [0)]=M(r, Ky. 5t, s) be (x,,,,1,,8) b1 8y. 8t, s).
MM
(63)
(64)
The next lemma allows for limited form of addition in the output.
26

---

Published as a conference paper at ICLR 2025
Lemma 44 (Addition in t). Given N1, N2, en cz. yo. to. s0, Symals suppose the image of
ve( c1, (yo, to, 8o), 8fimal)
(65)
has only finitely many points (fo (u))) Further suppose
02, (vo, to. 80), 8) (50, Sfmai) } < min 1 - Haul-
(66)
2
Then there exists N3, 03 such that
Il ODESol c3, v, (yo, to: so), Syimal) Th+1 (ODESolve(Ni, C1, (Vo, to su), 8finat) + ODESolleeNe) C22 n. (yo: to, so), 8pmal)
(67)
(68)
Proof. Let $1/22 = 30 + (Stnnal s0)/2. From Lemma 42, there exists N2 and ci such that ODESolVe (Ni, <1, x (yo, lo 8n), 81/2) = oDEsol ve c1, (yo, lo, 80), 8tmal) Likewise, from Lemmas 42 and 43, for each j = 1...., J, there exists N3 and cf such that ODE velooveee c2, (Wout: Him 81/2); Stima)
(69)
(70)
(Nom (um) + ODE.ooveeW2, 02, x, (Yo, lo, so), Stinal).
(71)
Hypothesis 66 guarantees the are pairwise disjoint for each j. so the Ná can be t-glued (Lemma 40) into a single N3 such that
(Jn+1OODSLLveeNG c22, (yam tam $1/2), 8) I [$1/2, Shnal]
(72)
ODESolve(Ng, cg. x, (Nowr tom 11/2), stma) (vim & CODESolveNN C2 (Wo, to. su), 8fial
(73)
for j 1, I. Finally, using Lemma 39, s- s-glue Ni and N3 at $1/2 to obtain the desired Ng--
We now ready construct SANNs that represent characteristic functions of arbitrary semialge- braic sets.
Proposition 45, Let S C Rm be semialgebraic set. Then there exists N and C' E N such that for all 2 C.
ODESolve(N, (0,0,0), (0,)N,,,,,,,00,),,, = =0, (0)x)
(74)
Proof. First, suppose S open. Then is a closed semialgebraic set, and from Proposition 7 we conclude there exists g E ISD(R". Rz0) such that ker(g) S Define
((r,,.4,))=91) b(x, y. t, = (0,
(75)
(76)
M is singular iff x E ker(g), so å always returns 0 in this case. Otherwise, (ú.t) = M- = (0,1). Integrating from time su = 0 to Stinal
yields
(0, 1), x き ker (0. otherwise,
(77)
which proves the proposition for open S.
For closed S, recall S is open and Xs = 1 - xS. so Lemmas 41 and 44 yield the result.
Next, assume we can represent the characteristic function for S and S2. We will show how to represent the characteristic function of their intersection; equivalently, we show how to represent nsy Let be such that
(0, (0,xs;(1)
(78)
27

---

Published as a conference paper at ICLR 2025
for j 1,2. Using Lemma 42, there exists Mj such that
ODESoLve(N] z, (0, 0, 0), 1/2) (0,xs;
(79)
Using Lemmas 42, 43, and 41, there exists N3 such that
CDESolve 2, (0, 1, 122,, 1) = (0 (0, (x)).
(80)
Now I-glue N2 with trivial ISD network so that
ODESolve(Ng, c, 0,, (0)
(81)
and s-glue N1 with N2 at s = 1/2 to obtain the desired network.
We now handle the case of arbitrary semialgebraic set S. The key is to exploit the "cylindrical decomposition" of S: every semialgebraic set in R is the union of finitely many disjoint sets homeomorphic to (-,,1)². d many disjoint locally closed sets. Since locally closed sets are the intersection of an open and a closed set, we have already shown how to represent their characteristic functions with SANNs. Furthermore, since these locally compact sets are disjoint, the characteristic function of their union can be represented by summing the individual characteristic functions with s-glucing.
m (Bochnak et al., 1998). In particular, is the union of finitely
Remark. Note that, although M = g(x) is in some sense "nearly singular" close to the kernel of g. is still in fact an orthogonal matrix. No numerical instabilities arise from the conditioning of M when solving M = b.
E.7 PROOF THEOREM 13
Theorem 13. Let F Th" - Rh be (possibly discontinuous) bounded semialgebraic function. Then there exists N E ISDnet((m, and Gmax E T220 such that SANNlim (N, Cmax)==
Proof. Every semialgebraic function has finitely many connected components (Bochnak et al., 1998), so let {8 be semialgebraic decomposition of 1m such that F is continuous on each S.
Using Proposition 45, we can construct scaled characteristic functions on each connected compo- nent, and using Lemmas 41 and 44, we scale and add these functions to obtain No, co such that
ODESolve(No, co, x, (0, 1/2) = (0, where x E Sy.
(82)
Using Theorem 12, let Net,N be such that
SAN ci)ls, = Fls,
(83)
for each j = 1, I....,K. K. Furthermore, by the construction in the proof of that theorem, Mr can be chosen such that t(0)= 0 and {(1) 1. In particular,
CDESolve(N, cy, (0. (0. = (Fls, (z), when Sz.
(84)
Using Lemma 42, modify each NV. c,. that integration occurs in the interval [1/2, 1]. Fur- thermore, using Lemma 43, modify each N₁, e to begin integration at (0, 3j). Finally, t-glue these modified N,, and s s-glue the result to No at 1/2.
E.8 SEMIALGEBRAIC FUNCTIONS WITH UNBOUNDED IMAGE
Parameter Cuax provides upper bound the Lo norm of the output of SANN, the image of every -AANN-reprssentable function bounded. However, the same not true for all semialgebraic functions, even those with compact domain, such as F(x): [-1, 1] R defined by
11/x,
x + 0,
F(x)
(85)
0
I = 0.
Such functions not be represented by SANNs.
28

---

Published as a conference paper at ICLR 2025
E.9 SANNS ALWAYS COMPUTE SEMIALGEBRAIC FUNCTIONS
In our considerations, we use the Tanski-Seidenberg theorem, which has several equivalent formu- lations. We use the following:
Theorem 46 R" the projection map x ((,, x²) x', then the set (X) ) is a semialgebraic set in R"
When X C R" R is semialgebraic set and π R R$
So far, we have shown that SANNs are able to represent any bounded semialgebraic function. For completeness, we now prove a partial converse; that is, SANNs always compute semialgebraic functions provided the numerical ODE solver is semialgebraic. Common ODE solvers, such as Euler and Runge-Kutte Kutta methods, are semialgebraic. The proposition below focuses specifically the case of Forward Euler timestepper given in Section 3.2, but it can be easily modified for other methods.
Proposition 47. For all N 1SDnet(m, k), E IR" and Cmax >> the function fN Staes I1N where nn is given by the iteration (2), is semialgebraic.
Proof. The operation iteration steps (z H> 2,+1 are composition of ISD-function and the function (M, b) + (det (M), Mc, b), where Me is the co-factor matrix of M, the function
(det (M), Me b) der) det (M) (det (M))-*
that implements Cramer's rule, and another ISD-function given by the time-step formula
(2) 2g) + + N 5
This makes the function > nN semialgebraic; including the projection II, results in semialge- braic function due to the Tarski-Seidenberg theorem.
F NUMERICAL EXAMPLE: INVERSE PROBLEM FOR ELECTRICAL RESISTOR NETWORKS
This section demonstrates the feasibility of training SANNs solve a difficult non-linear inverse problem.
Suppose we are given an electrical network Physically, an electrical network is a system of connected resistors, and it is modeled by graph where every edge resistor. graphs and resistors on the edges when the outcome of all possible voltage and current measurements in some of vertices of the graph (called the boundary nodes) are given, see Figure 5.
EV with vertices and edges E C V V.
inverse problem for an electrical network is to find one or all
We partition V into boundary nodes Vn and interior nodes V,. Let E - Rz0 be the edge conductiviries. The network response matrix (i.c. Dirichlet-to-Nemmaan map) A E V computes the current at the boundary nodes resulting from applying voltages on VB. Our task is to recover the conductivites from measurements A of voltage-response the boundary. See Curtis & Morrow (2000) for a thorough treatment of this inverse problem, and Forcey (2023) for recent developments.
Equivalently, we wish to recover the Kirchhoff matrix K E IR VIXIVI where
(1,5) (1,
(i, E if = otherwise.
Ki
(86)
K is a symmetric matrix with conductivities on off-diagonals and that satisfies Kirchhoff's s Law the sum of entries in each row is O. Curtis & Morrow (2000) showed that A is the Schur complement of particular submatrix of the Kirchhoff matrix. Precisely, we write
A BT
B
K =
(87)
D
29

---

Published as a conference paper at ICLR 2025
where A corresponds boundary nodes VB and D corresponds to interior nodes I. If we let K(T) C R | denote the set of valid Kirchhoff matrices I' (a semialgebraic set), then the forward map (mapping graph and the values of the resistors to the values of the measurements) is the semialgebraic function F K(T) + RRlv//>/Vee /Vell defined
F(K) = A BD
(88)
The inverse problem is to recover an element the preimage ({A)), Since preimages of semi- algebraic sets (in this case the single point {A]) of semialgebraic functions (F) are themselves semialgebraic (Bochnak al., 1998), we conclude ((A(( is a semialgebraic set.
In certain special network topologies, such as for rectangular networks (Figure 5), the preimage of ({A)) is a singleton, that is, the values ji, (i.j) E E' of the resistors on the graph (V, E)) uniquely determined by the voltage-to-currett map A (Curtis & Morrow, 2000).
Figure 5: A x 3 rectangular electrical network. Each edge in the graph represents a resistor with unknown conductance.
This inverse problem has had a wide impact in several fields. In medical imaging it has led to new imaging modalities, for example, in monitoring lung function. Recently, EIT is used in monitoring the lungs of the COVID-19 patients, see Cappellini et al. (2024).
F.1 NUMERICAL RESULTS FROM TRAINING.
We demonstrate the feasibility of training SANNs to perform non-trivial tasks using the network EIT problem as an example. Specifically, given voltage-responss map A for a 2 x 2 rectangular electrical network, the task is to recover the non-zero, off-diagonal entries of the Kirchhoff matrix K. We trained 4-layer SANN to minimize the loss Liotal from equation (9). We compare this against a feed-forward neural network trained to minimize Laccuracy from equation (9) on the same data. Both networks were trained using the Adam optimizer. We also compare against known reconstruction algorithm from Curtis & Morrow (2000) that is exact for noiseless data. The results shown in Table 2 below. Let shortly discuss these results: The Curtis and Morrow (C&M) algorithm is an analytical method that solves the problem using the theory of planar graphs, and therefore it is provably correct for all inputs, including inputs outside the training data used for the other algorithms, such as exceptional resistor networks with very small or large resistors. However, the algorithm is very sensitive to noise. The algorithm based on a feed forward network is used in our tests as a black-box algorithm and it works well with noisy data. The SANN is between these two algorithms--i is explainable in the sense that SANN can represent the rational matrix functions, and it works moderately well with noisy data. We note that in the numerical tests the training of SANNs was not fine tuned and by improving the training methods, it possible that the results could be improved.
As in the linear inverse problem example from Section 5.2, a trained SANN performs comparably to standard feed-forwart neural network of the same size, demonstrating the feasibility of training these networks. We do not claim to demonstrate numerical advantages of SANNs at this stage; further research is necessary to develop new techniques that fully leverage their expressive power.
Both networks outperform the C&M algorithm on noisy input data. The C&M algorithm recon- structs conductances edge-by-edge, starting from the boundary and working inward; this causes
30

---

Published as a conference paper at ICLR 2025
parameters 17, 712
Relative error (noiseless)
Relative error (1% noise))
Feed forward network
0.0157
0.0180
SANN
17, 17,640 640
0.0234
0.0273
C&M
2.49e 07
0.0469
Table 2: Results of training neural networks from data solve the network EIT problem 2 rectangular electrical networks. The last row (C&M) shows the reconstruction algorithm from Curtis & Morrow (2000).
errors to accumulate rapidly for interior edges. In contrast, neural networks incorporate learned prior knowledge of the expected distribution of conductances, making them more robust to noisy measurements within the data distribution.
F.2 CONTINUOUS EIT PROBLEM (PDES)
The inverse problem for electrical networks described above is a discrete version of the medical imaging problem encountered in Electrical Impedance Tomography (Borcea, 2002), inverse prob- lem for finite element models for the (anisotropic) conductivity equation. If f C R² is the interior of simple polygon, and if one is given triangulation of 92, then the Finite Element Method (FEM) model for the Dirichlet problem for an elliptic partial differential equation,
V (a 2 Vu(z)) O,
x E S2 u|an = F,
for given matrix scalar valued conductivity function (x),, is the matrix equation
[e L" u (
where (11 uf corresponds values of the FEM solution at the vertices of the triangula- tion, f = (fi ... fB)' corresponds to the boundary value f at the boundary vertices, and the matrix (L' L") depends
and the triangulation and has rows whose elements add up zero
If one considers the triangulation of Ω graph, and if each edge of the graph assigns resistor with given conductivity, then the Dirichlet problem for this resistor network is to find a solution (ui.-. uN)* corresponding to voltages each vertex, of the matrix equation
( Ig K" K"
(90)
where f (f....
..- fB) corresponds to voltages at the boundary vertices. Also here, the rows of the matrix (K' K"), which depends on the resistors, add up to zero.
Thus, formally, the FEM model for elliptic partial differential equation and resistor networks lead to the same kind of equation, see Lassas et al. (2015) for details.
Electrical Impedance Tomography (EIT) is a method proposed for medical and industrial imaging, where the objective is to determine the electrical conductivity or impedance in a medium by making voltage to current measurements on its boundary (Borcea, 2002). has led new imaging modal- ities, for example the Pulmovista500 device by Draeger AG & Co. used to monitor lung function. Recently, EIT is being used to monitor the lungs of COVID-19 patients (Cappellini al., 2024).
The boundary measurements are modeled by the Bhichlet-to-Neumaan map A₃, which maps the boundary value / of the electric voltage to the electric current through the boundary (i.e., the conor- mal derivative) (J) v oulass
In FEM, let Ω be the interior of a simple polygon, and fix triangulation of T with vertices (Zi...., } of which { ØB} lie on On. Let A(2)) be the set continuous functions > R which are affine on each triangle. If vy the unique function in A(2) which is at ay and at all the other vertices, then A(2) = ( c Cp E C).
There is a voltage-to-curren map A FEM related to the FEM model that is a discrete version of the Dirichlet-to-Neumann map. To define this map, let consider the space A(3R) A(L))aa
31

---

Published as a conference paper at ICLR 2025
EE Guylontc E RR,, and quadratic form Qo A(a that is given for f A(00)) by
Qo(fff) = -min / ((x)V Vu(r) dr,
where the minimum is taken voltage-to- curreet map A FFM is a symmetric matrix A APÉM R I determined by the formula
A(22) satisfying the boundary condition ulan = f. The
J. Qolf.))
where f Ef Vyle is the boundary current corresponding to a vector f (f))
The solution of the matrix equation (90) can be found using Cramer's formula as meromorphic function. This implies that there is a SANN that solves the FEM approximation problem (90) for the partial differential equation (89) and another SANN that represents the voltage-to-current map.
G ADDITIONAL APPLICATIONS
G.1 SEMIALGEBRAIE OPTIMIZATION
Consider the general class of optimization problems
f(0) arginf 9(0", subject to the condition H" E S(0) C R"
(91)
0"
where 0 E RRm and both g Rn R and S: RT PRR) are semialgebraic functions. Here, P(RR") ;= &" x C ] that is allowed vary based on O. Using the Tarski Parski-Seidenberg theorem, we can show that f is (possibly set- set-valued) semialgebraic function. Indeed, the graph of f
is the power set of R2 and S(0) is semialgebraic constraint set
{( I1, (L, n (8(0) x 1TTh x B))) E RT
(92)
where II, projects onto the first coordinates, is the boundary operation, and cpi(g) the closure of the epigraph cpi(g) = { f) (R" x R x R) 2 g(0", 0)} of g. Since this is semialgebraic set, f semialgebraic function. If we impose the additional assumption that is bounded (which holds if S is bounded, for example), then by Theorem 13 it can be represented by SANN.
Remark. Optimization problem (91) includes as special cases polynomial optimization and pandraaic/linear/mxxed-eeeee programming. It is at least NP-hard; there is no general polynomial- time algorithm to compute f from a description of g and S (Lasserre, 2015).
Many interesting problems can be formulated in terms of (91). Below, we give a new potential application using SANNs hypernetwokk to sparsify ReLU networks.
G.2 SANNs HYPERNETWORKS
In this section, we demonstrate how SANNs can be used as hypernetworks to optimize various properties of target ReLU networks.
To connect the general class of optimization problems (91) to hypernetworks, suppose we have fixed target architecture Nunget with trained weights 0 E RT Let S(0) ITm be the of all weights generating equivalent networks (Petersen et al., 2021); ie. every choice of weights from S(0) produces the same onput-output pairs as 9 when used in architecture Ni When A farger is feed-forward ReLU network, S(0) is semialgebraic set (Valluri & Campbell, 2023).
Now, different choices of objective function g optimize various properties of the target network. For example, when g counts the number of non-zero elements of 6* (the "7 norm"), f returns the pparsest-possible equivalent network. Using sparse 0* is both more memory-efficient (Böleskei et al., 2018) and interpretable (Fan et al., 2021) than using 0. Likewise, f can return a "nearly- equivalent" network with small Lipschitz constant by relaxing and using g that computes the Lipschitz constant of Wunget with weights 6* Reducing the Lipschitz constant of the target network improves its robustness, interpretability, and generalization performance (see Ducotterd et al. (2024) and references therein).
32

---

Published as a conference paper at ICLR 2025
G.3 SEMIALGEBRAIE TRANSFORMER
In this section, we demonstrate how variation of the transformer architecture (Vaswani et al., 2023) expressible SANN. Our presentation of the transformer architecture is inspired by Furuya et al. (2024).
We start with the SoftMax attention mechanism the heart of the transformer architecture. SoftMax _ + 12 operates row-wise on its input matrix:
exp(X..)
SoftMax(X)
(93)
E exp(
SoltMax is continuous approximation to the row-wise function arg max R R"
11/8 if o4 2 zij for all 1...n
(arg maxgaaxaa 2);,
(94)
0 otherwise.
where s is the number of indices j such that Ij = max It is not semialgebraic function since exp: IR + R is not semialgebraic; however, for our purposes we can use the following piecewise- rational function saxp R + R instead:
saxp(x) = sx² +x+1
* x20 0
(95)
11/(x² -
< O.
saxp shares the following properties with exp:
Im (saxp) = Im (exp) +00)
saxp(0) exp(O) and saxp' (0) exp' (0)
lim saxp(x) = 0, and lim saxp(x) = +00.
8
6
saxp
exP
2
2
Figure 6: saxp (black) is a semialgebraic approximation to exp (red). It is simple, accurate near O, and has the correct asymptotic behavior
+
saxp is good approximation of exp near 0, but saxp = o(exp) as -> oo. In fact this is true for every semialgebraic function since every semialgebraic function is bounded above by polynomial (Bochnak & Efroymson, 1980). This not a concern for our transformers since layer normalization will keep the input saxp near 0.
By using saxp in place of exp in equation (93), we define SArgMax ("Semialgebraic ArgMax"):
saxp(X
SArgMax(X),, := Σ (X,))XX,))
(96)
Like MoftMax, every entry of SArgMax(X) X) lies the interval (0, 1), and every row sums to 1.
This yields the semialgebraic attention mechanism
Attgr (X) == VX SArgMax X XTQT
(97)
where 0h = (K,Q, V) kxd x kx,, Xd ("Key", "Query", and "Value") are learnable parameters. A multi-head attention mechanism with a skip connection is simply a linear combination of attention blocks:
H
MX) = X +
W Att (X)
(98)
h=1
33

---

Published as a conference paper at ICLR 2025
where 0 = (W*, )²), 1.... H are the learnable parameters specific to each attention head.
Transformers are constructed by composing multi-head attention, MLP, and layer normalization blocks. MLP blocks with ReLU activation simply
(XP := ReLU(WXX + B)
(99)
with parameters == (W, B). Row-wise layer normalization is
LayerNorm(X)1, Xi.i
pi
where
(100)
di
14 = Xi.t
(101)
7 1=1
01
(Xi,e n:)2.
(102)
Recall that every function defined piecewise on semialgebraic decomposition R using only addition, subtraction, multiplication, division, and extraction of roots is semialgebraic function. From this, is clear that MAt,, MLP, and LayerNorm in equations (98), (99), and (100) are semialgebraic. Furthermore, they are all continuous, they bounded when their domain is restricted to be compact, such as after a tokenization step. Finally, note that the composition of semialgebraic functions is itself semialgebraic function.
Transformers with semialgebraic attention are built as compositions of equations (98), (99), and (100), they are bounded semialgebraic functions and thus representable by SANN by Theorem 13.
We emphasize that our only change the transformer was to replace exp with the semialgebraic approximation saxp. This modified transformer is naturally expressible as SANN without further modification of our architecture.
34


Reviews:
[{"review_id": "MYBVex1v6N", "reviewer": "Reviewer_LTgJ", "summary": "Authors proposed an architecture that is capable to approximate an arbitrary semialgebraic function. The main ingredients making the construction possible are two facts (i) it is possible to efficiently generate functions from ISD by neural networks with ReLU activations, (ii) any closed semialgebraic set (defining semialgebraic function) is a kernel of some ISD. Authors exploit these facts by combining a neural network with a homotopy method that deforms a simple semialgebraic set into a target semialgebraic set. The role of homotopy is to replace rootfinder that can be also used to find kernel of ISD. The resulting architecture resembles neural ODE, and requires adjoint for training. Authors demonstrated several theoretical results showing that with the proposed architecture it is possible to approximate continuous and discontinuous semialgebraic function.", "questions": "1. In the introduction authors made an analogy with deep equilibrium model and write (line 46) \"Therefore, in principle, we can use a neural network combining polynomials and ReLU activations to learn G, then append a root-finding procedure such as Newton’s method to compute $F (x) = \\text{root}(G(x, \\cdot)) = y$ in a manner similar to Bai et al. (2019).\" Given that it seems that deep equilibrium models are already capable of computing arbitrary bounded semialgebraic function, and the claim that authors present first such method (line 59, \"To our knowledge, we present the first neural networks capable of computing arbitrary bounded semialgebraic functions on high-dimensional data\") is misleading. Can the authors please clarify this?\n2. In line 270 and equation (2), (3) that jointly define SANN there is an operation defined as $M^{-1}b$ if $M$ is invertible and $0$ otherwise. This operation is not convenient from the numerical perspective, since it requires the inversion of potentially large matrices, besides it is not cheap to test numerically that $M$ is invertible. Is it possible to generate $M^{-1}$ right away from $ISD_{\\text{net}}$ in place of $M$? Is it important that $M$ can be not invertible? Can the authors please clarify this part?\n3. In line 332 authors write \"In our experiments, we found it insufficient to train using only the accuracy of the final output $\\left\\|y^{\\star} − y(1)\\right\\|$.\" No numerical experiments can be found in the article. Can the authors please describe numerical experiments they tried and show the results?\n4. As I understand, training procedures include differentiation through the ODE solver. For that one needs to solve the adjoint ODE equation, and this is going to incur additional numerical costs. In a similar way, a deep equilibrium model defines an adjoint equation to obtain a derivative. Given that it is not clear what advantages the proposed method has over the deep equilibrium model (as discussed in the introduction) in terms of computations required. I kindly ask authors to discuss this issue.\n5. In G2 authors provide interesting applications of SANNs. The idea, as I understand it, is to apply SANN to the space of equivalent feed-forward ReLU networks (which form a semialgebraic set). It is not entirely clear to me how this set can be constructed and manipulated with SANN. Can the authors provide more details, preferably, with some simple examples? It seems to me that this set is hard to work with, because practically indistinguishable networks can have weights arbitrarily distant in the $L_2$ norm https://arxiv.org/abs/1806.08459. It is also not clear to me how precisely SANNs can be used in the context of Lipschitz networks and for sparsifications.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The article introduces an interesting original idea that can be potentially used for many problems laying on the intersection of scientific computing and machine learning. Authors provide many details, examples and clarifications that help the reader with little background in semialgebraic approximation to better understand theory authors develop. Theoretical results seem to indicate that the proposed class of models represents a rather general set of functions. I also find particularly stimulating a discussion of relation between SANNs and deep equilibrium models solved with numerical continuation.", "weaknesses": "The article is theoretical, so the weak side is, naturally, a discussion of practical matters: computational complexity, how networks should be trained, how it compares with different related models, and questions alike. I put some of these questions in the section below, but overall I do not find this is a significant disadvantage, given that the goal of authors is to provide a certain \"universal approximation\" result for novel architecture they propose.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Zl0vMGlvje", "reviewer": "Reviewer_fqV6", "summary": "This paper proposes the use of polynomial homotopy continuation methods to design a novel neural network achitecture. Homotopy continuation methods consider a function $H$ which continuously deforms a target function $G_0$ until it reaches a target function $G$. This method uses neural networks with RELU activations to compute the vector field of an ODE corresponding to this process of continuous deformation.\n\nThe authors show formally that this method can compute all bounded semialgebraic functions and that their method can be extended to discontinuous functions. \n\nFinally, a general class of optimization problems is specified, and the authors give example applications of their method.", "questions": "* \"To our knowledge, we present the first neural networks capable of computing arbitrary bounded semialgebraic functions on high-dimensional data.\" What advantage does such an architecture have compared to SoTA neural networks which are already widely used and easy to train?\n* \"In our experiments...\" what experiments are you referring to? Would it be possible to include the discussed experiments in the final manuscript? If not please remove any references to experimental results\n* You provide theoretical guarantees (Theorems 14 to 16) that your model can represent any bounded semialgebraic function. Do you have any intuition on learnability? Could your model learn a function exactly given a finite amount of samples?\n* Can you give examples of how representing discontinuous functions exactly might be useful in practice?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The theoretical contributions of this paper seem strong. Capacity to compute all bounded semialgebraic functions (and extension to discontinuous functions) seem to be solid theoretical guarantees.\n2. The proposed method seems, in principal, easy to implement and computationally efficient.\n3. The method seems, in theory, to be applicable to a large range of optimization problems.", "weaknesses": "1. The subject matter presented in this paper is quite difficult, and I believe most ML researchers are probably quite unfamiliar with these mathematics. That being said, I found the exposition to be quite hard to read. Here are some more precise points/considerations I believe would improve the readability\n    * Given this paper is presented to a machine learning (ML) conference, there should be more emphasis on the underlying learning problem. It might be interesting to motivate your architecture through a regression framework, for instance.\n    *  You include many proofs in the main text and do not give much intuition on your mathematical results. I believe it would improve readability to put proofs in the appendix and spend more time developing intuition in the main text. You could for instance add more examples throughout the text such as the one presented in \"Example 6\".\n    * I believe the algorithmic description of the architecture should be included in the main paper as it explains clearly the forward pass of your algorithm. It might be interesting to include \n\n2. The paper offers no experimental results on the proposed architecture. Given the main contribution of this paper is a novel architecture, empirical validation demonstrating the trainability of the model is crucial. I believe adding simple experiments with synthetic data would increase the value of the paper. You could, for instance, define a simple regression problem with synthetic data generated by a semialgebraic function, and show your model can exactly recover the correct mapping.\n\n3. \"We give a few remarks on training SANNs, and leave a more thorough investigation for future work.\" Although you do define a loss objective to train the model, you provide no empirical or theoretical justification that this loss objective works.  As with point 2, I believe it would strengthen the paper to give a thorough investigation (either theoretical or empirical) of the training procedure. For notes on doing this empirically see point 2. This could also be done theoretically by analyzing the training dynamics for example.\n\n4. I find the structure of the paper to be confusing. I will list my comments about paper structure below:\n    * There is no discussion or conclusion: it would be nice to add a conclusion section in which you discuss limitations and address future directions of research. \n    * The section which presents example applications does not contain any actual examples, only the general class of problems. It might help readability to use one of the example applications given in the appendix as a motivating example. \n    * Most of the paper seems to be an introduction to semialgebraic geometry and homotopy continuation methods (section 2 and first half of section 4). Maybe it would help readability to give a less detailed/rigorous introduction to the field and focus on explaining how the architecture works/why this method is useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9w7rosABdR", "reviewer": "Reviewer_MHwZ", "summary": "This paper introduces a new class of neural network models, SANNs. The model is built on the basis of semialgebraic theory. The fead-forward network is defined using ODE and polynomial homotopy continuation method is used to ‘universality’ of the expressiveness of the neural networks. The paper focuses on theoretical aspects of the neural networks and contains abundant theoretical claims.", "questions": "- Why should semialgebraic function F not be simply modelled by ‘standard’ MLPs/NNs? In other words, why should F be encoded to the kernel of a piecewise polynomial? \n- Do the authors have a (rough) estimation and/or observation about the computational complexity of fead forward and training of SANNs?\n- What would be a concrete example and task in PDE simulation to which SANNs are expected to perform better than existing methods? What would be the advantage of using SANNs in this case?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Building a neural network based on semialgebraic geometry is very refreshing and definitely new class of ML models.  \n- Using (the idea of neural)ODE as a computational graph of SANN also makes a quite sense assuming polynomial homology continuation method is used. \n- Visualization of the homotopy continuation method is really helpful to foster the readers’ understanding.\n- Appendix covers exhuastive theoretical contents of the paper. Some applications are also discussed.", "weaknesses": "**Theoretical aspect:** In general, the paper assumes readers to be very familiar with semialgebraic geometry, which is (at least at this point in time) not a main stream of ML communities. I would presume the paper would be very hard to follow especially for those who are not familiar with this topic. I strongly encourage the authors to revise the paper so that the contents of the paper could be more accessible to even those unfamiliar with this topic. The followings are some concerns I found:\n- The introduction of the paper is very hard to understand. Authors’ claims in the first paragraph of the introduction ‘’Semi algebraic functions include anything computable using …” and/or “Due to their ubiquity” would be unconvincing for those unfamiliar with this topic. It would be very helpful if the authors include references and/or brief explanation on the representative “classical numerical algorithms” that compute semialgebraic functions.\n- The definition of lattice should be mentioned before Definition 1 or referring to Appendix A -- I would say that at least in ML-community a lattice typically means $ \\mathbb{Z}^{d}$.\n- ‘ker(f)’ in Proposition 7 should be also introduced. I would also say, the first sentence of the proof might be a bit rough -- It would be better to mention the continuity of $f$. Need to clarify the definition of $C^1$, since $\\max ( 0, -q(x) )$ is generally not differentiable.\n- The proof of Proposition 10 is hard to understand. Especially, ‘another ISD-function’ at line 311 is vague. Tarsi-Seidenberg theorem should be also stated somewhere in Appendix.\n- What the authors mean by Training is somewhat unclear. When SANNs are trained, what parameters of SANNs are going to be trained? Does that mean the coefficients $a$ of $f_{k}(x)$ at line 154 are the trainable parameters? \n- The claim in the lines 42-43 ‘neural networks capable of exactly computing any bounded semialgebraic function’ sounds vague since it is not clear what the authors mean by ‘exactly compute’. Does it mean, the proposed neural network can solve any root finding problems for semialgebraic functions?\n\n**Experimental aspect:**\n- The application that benefits from the proposed network is not clear and it is hard to evaluate numerical advantages of the method. Key advantages of the networks in numerical experiments are stated as that the computational complexity is low and the evaluation time is fixed when using (non-adaptive) ODE solver, either of which are not evaluated in experiments or important classes of applications. While the paper rather has a technical sound and supports the theoretical validity of those two aspects, having numerical experiments that support authors’ claim would add stronger experimental support of the method's advantage. \n- I managed to find in line 332 ‘In our experiments, we found it insufficient to train using only the accuracy…’, but I cannot find results of any experiments. \n- The example applications in Appendix G should be discussed in the main text.  \n\n**Minor:**\n- ‘compute’ feels abused frequently. In some sentences, ‘represent’ instead of ‘compute’ sounds more convincing for me.\n- L.20 or 21, “is able execute…”\n\n\n**Overall comment (and meddling suggestion):**\n\nThe theoretical results of this paper are very intriguing and I believe this work would shed a light on the new usage of semialgebraic geometry in ML domain. On the other hand, I cannot overlook the major drawbacks that the paper lacks experiments which support theoretical finding and does not clarify numerical advantages against existing methods, as well as the lack of the readability of the paper. Therefore, I will give the paper the score ‘6’. However, I would be very comfortable to raise the score once those issues are addressed satisfactorily. \n\nThis may be none of my business, but I also cannot refuse wondering if this paper might also have more appropriate venue to be submitted given the abundance of theoretical contents. It might be very interesting if the authors could look for venues with more theoretical sound, such as (computational) mathematics journal. While the work of this paper definitely falls down into some category of machine learning domain, I also feel the paper would make a greater impact in the different communities;)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "U5rIpWTJ3M", "reviewer": "Reviewer_3yC9", "summary": "This paper introduces Semialgebraic Neural Networks (SANNs), a novel neural architecture designed to exactly compute bounded semialgebraic functions through homotopy continuation methods. The key idea is to encode the graph of a learned function as the kernel of a piecewise polynomial and then use numerical ODE solvers to evaluate it. The authors provide theoretical guarantees for the expressivity of SANNs, showing they can represent both continuous and discontinuous bounded semialgebraic functions. The work bridges classical numerical analysis techniques with modern neural network architectures.", "questions": "Questions:\nThe questions are in no particular order.\n1. Fig 1 caption: Why does homotopy not give parts in kernel of G that are not part of F but somehow also correctly gives isolated point (0,0)? \n2. What does \"defined in pieces\" mean?\n3. In corollary 8, \"gr\" is not defined.\n4. Why not learn the kernel directly? (As in, learn the predictive model F(x)= y as is standard in ML) What is the benefit of learning G?\n5. Why do we expect (7) to be small when s < 1? \n6. Above Thm 16 you say \"exactly compute\" but in remark earlier you mentioned that this will still have discretization error due to ODE solve. Should this be changed? \n7. Why does Theorem 14 only succeed with \"probability 1\"?\n\nSuggestions:\n1. Define acronym SANNS in main text.\n2. Clarity of Definition 1 can be improved. Perhaps the free lattice should be defined? C^k(D, R^n) is not defined (I'm assuming this is just k times differentiable functions on R^n?) \n**3. I do not understand the definition of SANNs in equations 2-5. How does little n affect Z(N) and what is the product over? What is M and what does the the tuple equation (M, b) = N mean? (I'm guessing but can't be certain it's like the clamp-sol argument.) I suggest clarifying the notation here more carefully. \n4. The distinction between existing work and new contributions is not clear in 4.2. Can you write your results as a proposition?\n5. Does Section 4.1 really belong in Section 2?\n6. In your summary of Section 4, perhaps include the subsection numbers to help navigate the relationships between the proofs.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "Overall interesting application of homotopy methods to learn semi-algebraic functions. The work includes nice background on semi-algebraic geometry. Overall the high level idea is potentially interesting.", "weaknesses": "The biggest weakness of the paper (and major reason for the score) is the lack of clarity in the definition of SANN's and Section 4. I mention some suggestions in the questions below.\nThe introduction hints at a potential answer, but I don't understand why one would want to use this framework. Is this better than using the traditional learning framework (of learning F directly?)\nHere is a list of other weaknesses:\nThere is no implementation or numerical work. (This isn't necessary, but I think the claim that you \"demonstrate on applications\" isn't accurate.)\nIt isn't clear which results are classical, or almost classical with a few notational differences. For example, is Proposition 7 a new result? What is new in Section 4.2?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)