Research map / Learning theory and algorithms / Sample complexity

Semialgebraic Neural Networks: From roots to representations

ICLR 2025 · Learning theory and algorithms › Sample complexity · approach: Neural network approximation theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces Semialgebraic Neural Networks (SANNs), which evaluate bounded semialgebraic functions by numerically integrating an ODE derived from a homotopy continuation method, built on ReLU-plus-polynomial matrix-recurrent networks.

Problem

Neural networks with ReLU activations represent only piecewise-linear functions and cannot exactly represent many semialgebraic functions produced by numerical algorithms (e.g., linear solvers, eigenvalues, inverse problems).

Approach

Encode the graph of a semialgebraic function as the kernel of an inf-sup definable piecewise polynomial, and define the network as the vector field of an ODE that tracks a root via homotopy continuation; integrating this ODE from s=0 to 1 yields the exact function value, including discontinuous cases.

Key results

• A hand-configured SANN reproduces 100 Jacobi iterations and solves 50x50 linear systems to machine precision, which standard piecewise-linear feed-forward nets cannot do.
• On 10x10 linear systems, a SANN with 291,720 parameters reaches validation residual 0.101 versus 0.166 for a feed-forward net with 306,140 parameters.

Measured effects reported in the paper

Surprising findings

• The SANN is capable of exactly representing discontinuous semialgebraic functions, including isolated points, by gluing homotopies on each connected component.

Limitations

• Expressivity of ISD networks depends on the open Pierce-Birkhoff conjecture; the MRNN construction is non-constructive and Hadamard products may require exponentially many parameters.
• Training SANNs remains an open challenge; the trained SANN only modestly outperforms a feed-forward baseline and does not reach machine precision.
• Hand-crafted exact construction is shown only for a specific Jacobi iteration example.

Experimental setup

Datasets: synthetic linear systems (strictly diagonally dominant 10x10 matrices)

Benchmarks: 10x10 linear system solving (validation residual)

Metrics: validation residual norm ||Xy-g||_2 parameter count

Baselines: feed-forward neural network

Builds on: Neural ODEs Deep Equilibrium Models Operator Recurrent Neural Networks Pierce-Birkhoff conjecture

Closest papers by meaning

• Position: Algebra Unveils Deep Learning - An Invitation to Neuroalgebraic Geometry (ICML 2025 · similarity 0.86)
• Semi-Implicit Neural Ordinary Differential Equations (AAAI 2025 · similarity 0.86)
• Composing Global Solutions to Reasoning Tasks via Algebraic Objects in Neural Nets (NeurIPS 2025 · similarity 0.84)
• Revisiting Orbital Minimization Method for Neural Operator Decomposition (NeurIPS 2025 · similarity 0.84)
• Hyperbolic-PDE GNN: Spectral Graph Neural Networks in the Perspective of A System of Hyperbolic Partial Differential Equations (ICML 2025 · similarity 0.84)
• Riemann Tensor Neural Networks: Learning Conservative Systems with Physics-Constrained Networks (ICML 2025 · similarity 0.84)