Algebraic Expressivity Certificates for Shallow Polynomial Neural Networks

Sepehr Akbari; Shahrzad Jamshidi

Source-linked AI summary

Algebraic Expressivity Certificates for Shallow Polynomial Neural Networks

Sepehr Akbari, Shahrzad Jamshidi

arXiv:2609.28500v1Sep 11, 2026math.ACcs.LGmath.AG

TL;DR

A fixed-width polynomial network has an exact function class that universal-approximation statements do not characterize, and residual error alone cannot distinguish architectural obstruction from optimization or data effects. The paper models these networks using Veronese secant geometry and eliminates parameters to construct nonmembership certificates. It reports exact quadratic descriptions, higher-degree equations, a finite architecture sweep, and a sphere loss floor.

Problem
Universal-approximation statements do not characterize the exact class represented by a fixed-width network, and residuals may reflect architecture, optimization, or finite data.
Source: §1 · p. 1
Method
The paper models network outputs as sums of powers of linear forms and eliminates weights from a graph ideal to obtain equations for their Zariski closure.
Source: §2 · p. 2, §1 · p. 2
Results
The pipeline recovers the quadratic determinantal description and classical higher-degree ideals, while its 33 completed sweep runs agree with the theoretical zero-versus-nonzero ideal prediction.
Source: §1 · p. 2, §4 · pp. 4–5, §3 · p. 4
Takeaways & Limitations
A violated invariant provides an exact diagnostic that a target is outside the polynomial architecture, independently of weight optimization.
Source: §1 · p. 1, §6 · p. 7
For d ≥ 3, closure equations certify nonmembership when violated, but their simultaneous vanishing need not establish exact Waring rank.
Source: §2 · p. 2, §4 · p. 5

Abstract

from arXiv · show

We study exact representability by bias-free shallow polynomial neural networks using algebraic geometry. Over $\mathbb{C}$, a width-$r$ network with activation $z\mapsto z^d$ computes a sum of $r$ $d$-th powers of linear forms, whose Zariski closure is a Veronese secant variety. Ideal elimination therefore yields polynomial certificates of nonrepresentability. We implement this construction as a generic architecture-to-certificate pipeline. For quadratics, we recover the exact symmetric determinantal description and explain its dimension through orthogonal symmetry. In higher degree, the implementation recovers classical catalecticant and secant equations and maps the practical reach of direct elimination across a finite architecture sweep. We also derive the exact population loss floor for a rank-two quadratic network on the sphere, illustrating how an algebraic obstruction induces irreducible approximation error.

1 Introduction

A fixed-width, bias-free polynomial network represents a specific class of forms that universal-approximation statements do not characterize. The paper uses algebraic geometry to distinguish exact representability from its closure and to construct certificates of nonrepresentability.

1 Introduction

A violated polynomial invariant can prove that a target lies outside a fixed-width architecture, independently of optimization, while residuals may also reflect optimization or finite data.The certificate is a precise diagnostic for the polynomial model, not a reduction of general learning to polynomial membership.Source: §1 · p. 1
Equations obtained by elimination describe the border-rank locus: violation proves nonrepresentability, but simultaneous vanishing generally does not establish exact Waring rank.The paper makes the image–closure distinction explicit because it determines what polynomial equations can certify.Source: §1 · pp. 1–2
For quadratics, bounded rank is closed, and the determinantal characterization connects its dimension to the network’s orthogonal-symmetry parameter redundancy.The symmetry is V → QV with Q ∈ O(r, C).Source: §1 · p. 2
A general architecture-to-certificate pipeline eliminates parameters and evaluates targets; it recovers classical higher-degree ideals and derives the sphere experiment’s exact population loss floor.Examples include the binary-quartic catalecticant determinant and the (3, 3, 2) ternary-cubic maximal-minor ideal, whose equality is checked over Q.Source: §1 · p. 2

2 Algebraic formulation

The algebraic formulation represents a bias-free polynomial network by a polynomial map from weights to coefficients, then separates its exact image from the Zariski closure that equations describe.

2 Algebraic formulation

Over C, a width-r network with activation z^d computes a sum of r d-th powers of linear forms, giving the exact complex class of forms of symmetric Waring rank at most r.Its Zariski closure is the affine cone over the r-th Veronese secant variety, whose points have symmetric border rank at most r.Source: §2 · p. 2
For d ≥ 3, bounded-rank symmetric tensors need not form a closed set, so equations of the closure certify nonmembership but their vanishing need not give an exact width-r decomposition.The closure corresponds to border rank, while the network image corresponds to exact rank.Source: §2 · p. 2
Eliminating weight variables from the graph ideal yields generators for the vanishing ideal of the Zariski closure of the polynomial map’s image.A Gröbner basis in an elimination order provides the generators.Source: §2 · pp. 2–3
If a closure equation evaluates nonzero at a target, the target is outside the closure and therefore outside the exact network class; the converse need not hold.The certificate is sufficient for nonrepresentability, not a general test of exact representability.Source: §2 · p. 3
The generic implementation constructs the coefficient equations for supplied (n, r, d), forms the graph ideal over Q, and eliminates all rn weight variables.A target evaluator turns a violated equation into a certificate; fixed quadratic scripts check the same construction.Source: §2 · p. 3
When the closure has full dimension N, it is the whole homogeneous-form space and has zero vanishing ideal, but this does not imply exact width-r representability.For d ≥ 3, the Alexander–Hirschowitz theorem identifies four listed tuples where affine dimension is one below the expected value.Source: §2 · p. 3
Over R, absorbing scalar output weights into linear forms fails for even d with negative weights, and closure membership need not imply representability by a chosen real architecture.Complete real descriptions can require polynomial inequalities as well as equalities.Source: §2 · p. 3

3 Quadratic networks

For quadratics, width-r representability over C is exactly the locus of symmetric matrices with rank at most min(r, n), yielding a closed determinantal certificate. The section connects dimension loss to orthogonal redundancy and illustrates the certificate for ternary quadratics.

3 Quadratic networks

For s = min(r, n), a quadratic is representable exactly when its symmetric matrix has rank at most s, and for s < n the defining ideal is generated by the (s + 1) × (s + 1) minors.When s = n, the ideal is zero.Source: §3 · p. 3
The quadratic image is closed, so its rank characterization gives exact complex representability rather than only a certificate for nonmembership in a closure.Every complex symmetric matrix of rank q ≤ s can be factored as B⊤B and padded with zero rows when needed.Source: §3 · p. 3
The dimension loss reflects orthogonal redundancy: V → QV leaves V⊤V unchanged, and the generic fiber loses the orthogonal-orbit dimensions.For full-row-rank V with r ≤ n, the stabilizer is trivial; the rank-s stratum dimension is counted by choosing its kernel and a nondegenerate symmetric form on the quotient.Source: §3 · pp. 3–4
For (n, r) = (3, 2), a ternary quadratic belongs to F3,2,2 exactly when its symmetric-matrix determinant vanishes, and generic elimination recovers that determinant equation.The identity matrix violates the equation and is not representable by a complex width-two quadratic network.Source: §3 · p. 4
With signed real output weights the same rank characterization holds, while the absorbed real model is narrower, containing only positive-semidefinite matrices of rank at most two.Source: §3 · p. 4

4 Higher-degree certificates

In higher degrees, catalecticant equations provide closure certificates, and the implementation recovers classical binary-quartic and ternary-cubic equations. An atlas tests direct elimination across 100 architectures, while some runs time out and explicit generators can become unwieldy.

Catalecticant certificates

Catalecticant rank bounds yield minors that vanish on the closure, but catalecticant minors do not define every Veronese secant variety.In the cited cases, classical results establish that they generate the full ideal.Source: §4 · p. 4

Certificate atlas

Of 33 completed runs in the 100-architecture sweep, 21 returned zero ideals and 12 nonzero ideals, matching dimension predictions in every completed case.The recorded comparison uses zero versus nonzero because ideal dimensions were not logged uniformly.Source: §4 · p. 4, Table 1 · p. 5

Practical reach

The direct implementation timed out on 67 cases, while (3, 4, 2) returned 148 cubics; these outcomes are not impossibility results for other algorithms.The 67 timeouts apply only to this implementation under its stated cutoff.Source: §4 · p. 5

Binary quartics

The binary-quartic closure is the hypersurface det Cat2,2(P) = 0, and the generic pipeline returns its cubic equation.Classical results identify this equation with the second secant variety.Source: §4 · p. 5

Ternary cubics

For (3, 3, 2), 20 maximal catalecticant minors generate the full ternary-cubic secant ideal, and the pipeline returns the same ideal.The two cubic spans both have dimension 20; the variety has codimension four.Source: §4 · p. 6

Target certificates

For an exact rational target, the evaluator reports nonmembership when a returned generator is violated, while vanishing leaves exact rank undecided for d ≥ 3.For d = 2, the evaluator can conclude exact membership because the image equals its closure.Source: §4 · p. 6

5 Sphere loss floor

The section formulates rank-two quadratic fitting on the sphere as a distribution-dependent low-rank approximation problem and derives its exact population loss floor. A single-seed experiment has an empirical plateau consistent with that analytic optimum.

5 Sphere loss floor

The fitting metric is induced by input-distribution moments, so coefficient-space Frobenius distance is not generally population MSE.The calculation is presented as a concrete specialization of low-rank tensor approximation in this moment-determined metric [8].Source: §5 · p. 6
The model output is x^T M x with M=V^T V positive semidefinite and rank at most 2, fitted to the target x^T I3 x.This casts the real network as a constrained quadratic-form approximation.Source: §5 · p. 6
1/6 is the exact minimum population MSE for the rank-two quadratic model on the sphere, attained when the matrix eigenvalues are (5/4, 5/4, 0).The minimizing eigenvalues are feasible for the positive-semidefinite rank-at-most-two constraint.Source: §5 · pp. 6–7
Approximately 0.16 empirical MSE was reached in the recorded single-seed run, consistent with the population value 1/6 ≈ 0.1667.The experiment used 104 normalized Gaussian samples, seed 49, and 60,000 full-batch SGD iterations; it is not evidence of generic global convergence.Source: §5 · p. 7, Figure 1 · p. 7

6 Conclusion

The conclusion presents algebraic certificates as a hierarchy: elimination gives border-rank equations, while quadratic networks admit an exact closed bounded-rank description. It also states real-versus-complex and architecture-scope limitations.

6 Conclusion

Complex-closure equations certify real nonmembership when violated, but real exact rank may exceed complex rank and vanishing need not establish exact Waring rank.A full real description may require inequalities.Source: §6 · p. 7
The model omits biases and depth, and recorded benchmark timings are specific to one run rather than portable performance claims.Adding biases or depth changes the parameterization and ambient polynomial class, so the Veronese secant description does not transfer without modification.Source: §6 · p. 7
The graph-ideal pipeline constructs border-rank equations, and a violated equation gives an exact architectural nonmembership certificate.Quadratics are exceptional because the bounded-rank image is closed; the higher-degree binary-quartic and ternary-cubic catalecticant ideals agree with known geometry.Source: §6 · p. 7

A Reproducibility

The reproducibility appendix records the implementation and derived data behind the computational claims. It documents the elimination pipeline, atlas processing, cutoff comparison, and single-seed sphere experiment.

A Reproducibility

The Macaulay2 pipeline builds the graph ideal for supplied (n, r, d), eliminates weight variables, and returns coefficient-space generators.The appendix identifies the implementation and target-evaluation scripts and records benchmark metadata when available.Source: A Reproducibility · p. 8
Table 3 lists completed 3600-second architectures with nonzero returned ideals; the recorded generator count does not establish minimality.The companion CSV also includes 21 successful zero-ideal cases and 67 timeouts.Source: A Reproducibility · p. 9, Table 3 · p. 9
58 of 60 shared architectures had the same completion status across the 120-second and one-hour grids.The longer log additionally completed (5, 2, 4) in 202.66 seconds and (6, 2, 3) in 1303.97 seconds; missing environment metadata prevents a controlled hardware-level timing comparison.Source: A Reproducibility · p. 9
The sphere experiment used one seed, and its empirical training loss is distinct from Proposition 13's population loss.The appendix reports that no multi-seed output is present in the available source code.Source: A Reproducibility · p. 9